16197번 - 두 동전

문제요약

1. 입력으로 보드의 크기와 동전 2개의 위치가 주어진다.
2. 상, 하, 좌, 우 4개의 버튼이 있으며 버튼을 1개 누르면 동전 2개가 모두 같은 방향으로 이동한다.
3. 동전이 움직일 때 벽이 있으면 해당 동전은 움직이지 않고 다른 동전은 움직인다.
4. 2개의 동전중 1개의 동전만을 보드 밖으로 떨어뜨리기 위해 최소 몇번의 버튼을 눌러야 하는지 출력하시오

원본 문제 보러가기

접근법

문제를 그림으로 해석해보겠다.

..        ..        ..        ..
..        ..        ..        ..
..        o.        .o        ..
o#   ->   o#   ->   o#   ->   o#
o#   U    .#   L    .#   L    .#        
##        ##        ##        ##

상 -> 좌 -> 좌 총 3번의 버튼을 누르면 동전 1개를 떨어뜨릴 수 있다.

재귀함수를 이용한 완전탐색법으로 문제를 풀었다. 현재 위치를 기준으로 4개의 버튼을 눌렀을 때 변화된 위치를 재귀함수의 파라미터로 넣었다. 재귀함수의 시작부분에는 동전이 떨어졌는지, 몇 개의 동전이 떨어졌는지를 체크하는 함수를 두었다.

버튼에 따라서 2개의 동전을 움직일 때는 각각의 동전이 벽에 부딪히는지를 체크해야 한다. A동전이 있고 B동전이 있고, 위 버튼을 눌렀을 때 A동전은 벽에 부딪히고 B동전은 벽에 부딪히지 않는다면 B동전만 움직일 수 있도록 코드를 짜줘야 한다.

재귀함수의 시작부분에 넣을 동전이 떨어지는지 체크하는 코드는 떨어진 동전의 개수도 알려줄 수 있어야한다. 만약 동전 2개가 모두 떨어졌다면 유효한 방법이 아니기 때문에 고려 대상에서 제외해야 한다. 동전이 1개만 떨어진 경우를 고려해야한다.

이 방법을 사용했을 때의 문제점은 시간복잡도가 굉장히 높다는 것이다. 정확하지는 않지만 약 $O(n^4)$ 이다. 여기서 n은 .의 개수이다. 굉장히 가파르게 상승하는 것을 알 수 있다. 문제를 풀때는 파이썬을 이용하여 추가 시간을 받았기 때문에 시간초과가 발생하지 않았지만 만약 C로 작성하였을 때 시간초과가 발생할 수 있다고 생각한다. 분명 이보다 시간을 줄일 수 있는 방법이 있다고 생각한다.

pseudocode

def dropCheck(coin1Coordinate, coin2Coordinate, boxSize, coinIdx):
  if coinIdx is 1:
    if coin1Coordinate is outside of boxSize:
      return True
  if coinIdx is 2:
    if coin2Coordinate is outside of boxSize:
      return True

  return False

def moving(board, coin1Coordinate, coin2Coordinate, boardSize, count):
  if dropCheck(coin1Coordinate, coin2Coordinate, boardSize, 1) and dropCheck(coin1Coordinate, coin2Coordinate, boardSize, 2):
    return INF
  if count is greater than 10:
    return INT
  if dropCheck(coin1Coordinate, coin2Coordinate, boardSize, 1) or dropCheck(coin1Coordinate, coin2Coordinate, boardSize, 2):
    return 0

  for button in [Up, Down, Left, Right]:
    if coin1Coordinate + button is in boardSize and coin2Coordinate + button is in boardSize:
      pushCount = min(pushCount, moving(board, coin1Coordinate + button, coin2Coordinate + button, boardSize, count + 1))

    elif coin1Coordinate + button is not in boardSize and coin2Coordinate + button is in boardSize:
      pushCount = min(pushCount, moving(board, coin1Coordinate, coin2Coordinate + button, boardSize, count + 1))

    elif coin1Coordinate + button is in boardSize and coin2Coordinate + button is not in boardSize:
      pushCount = min(pushCount, moving(board, coin1Coordinate + button, coin2Coordinate, boardSize, count + 1))

    return pushCount