[ 백준 16197 해설 ] ( python ) 두 동전

 

📚 두 동전

 

문제

N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, 두 동전의 위치는 다르다.

버튼은 "왼쪽", "오른쪽", "위", "아래"와 같이 4가지가 있다. 버튼을 누르면 두 동전이 버튼에 쓰여 있는 방향으로 동시에 이동하게 된다.

• 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
• 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
• 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다.이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.

두 동전 중 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 20)

둘째 줄부터 N개의 줄에는 보드의 상태가 주어진다.

• o: 동전
• .: 빈 칸
• #: 벽

동전의 개수는 항상 2개이다.

 

출력

첫째 줄에 두 동전 중 하나만 보드에서 떨어뜨리기 위해 눌러야 하는 버튼의 최소 횟수를 출력한다. 만약, 두 동전을 떨어뜨릴 수 없거나, 버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다.

 

예제 입력 1 복사

1 2
oo

예제 출력 1 복사

1

예제 입력 2 복사

6 2
.#
.#
.#
o#
o#
##

예제 출력 2 복사

4

예제 입력 3 복사

6 2
..
..
..
o#
o#
##

예제 출력 3 복사

3

예제 입력 4 복사

5 3
###
.o.
###
.o.
###

예제 출력 4 복사

-1

예제 입력 5 복사

5 3
###
.o.
#.#
.o.
###

예제 출력 5 복사

3

 

 

 

 

 

✍ 접근

• 재귀를 돌리면서 조건을 만족시켰을 때의 값을 res에 넣자.
• 재귀를 돌리면서 조건을 만족하지 못할 것들은 빨리 return시키자

 

 

 

 

 

정답코드 

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N,M = map(int,input().split())
board = [list(input().rstrip()) for _ in range(N)]
visited = []
coinpos = []

dx = [-1,0,1,0]
dy = [0,-1,0,1]

res = 2147000000

def DFS(coin1, coin2, cnt):
    global res
    x1,y1 = coin1
    x2,y2 = coin2
    if cnt>=res or cnt>10:
        return
    if x1 == x2 and y1 == y2:
        return
    if (0 > x1 or N <= x1 or 0 > y1 or M <= y1) and (0 > x2 or N <= x2 or 0 > y2 or M <= y2):
        return
    if (0 > x1 or N <= x1 or 0 > y1 or M <= y1) or (0 > x2 or N <= x2 or 0 > y2 or M <= y2):
        res = min(res,cnt)
        return
    for i in range(4):
        nx1 = x1 + dx[i]
        ny1 = y1 + dy[i]
        nx2 = x2 + dx[i]
        ny2 = y2 + dy[i]
        if 0<=nx1<N and 0<=ny1<M and 0<=nx2<N and 0<=ny2<M:
            if board[nx1][ny1] != '#' and board[nx2][ny2] != '#' and (nx1,ny1,nx2,ny2) not in visited:
                visited.append((nx1,ny1,nx2,ny2))
                DFS((nx1,ny1),(nx2,ny2), cnt+1)
                visited.pop()
            elif board[nx1][ny1] == '#' and board[nx2][ny2] != '#' and (x1,y1,nx2,ny2) not in visited:
                visited.append((x1,y1,nx2,ny2))
                DFS((x1,y1),(nx2,ny2),cnt+1)
                visited.pop()
            elif board[nx1][ny1] != '#' and board[nx2][ny2] == '#' and (nx1,ny1,x2,y2) not in visited:
                visited.append((nx1,ny1,x2,y2))
                DFS((nx1,ny1),(x2,y2),cnt+1)
                visited.pop()
        else:
            visited.append((nx1,ny1,nx2,ny2))
            DFS((nx1,ny1),(nx2,ny2), cnt+1)
            visited.pop()


for i in range(N):
    for j in range(M):
        if board[i][j] == 'o':
            coinpos.append((i,j))

DFS(coinpos[0],coinpos[1],0)
print(res) if res<=10 else print(-1)

해설

아주 길죠?

DFS가 아니라 BFS로도 가능할 것 같습니다.

DFS에서의 예외처리가 중요한 문제였습니다

 

 

 

 

 

⭐ 배움

• DFS의 예외처리는 중요하다!