[BOJ] 16197. 두 동전(Python) / BFS

16197번: 두 동전

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

어렵지 않은 BFS 문제였다.

# 1시간 17분 소요

• 사용 알고리즘 : BFS 최단 시간 알고리즘
• input 받으며 두 동전의 위치 좌표를 받는다.(ar, ac, br, bc)
• bfs 함수에서 두 동전 좌표를 인자로 받는다.
• 함수 시작하며 check 라는 두 동전의 위치를 확인하기 위한 4차원 배열을 만든다.
• 그리고 두 동전의 첫 위치를 0으로 표시하고 큐에 담는다.
• 큐에 값이 있는 동안 큐에서 값을 하나씩 꺼내며 너비우선탐색으로 갈 수 있는 곳을 퍼트린다.
• 큐에서 꺼낸 위치 값이 이미 10번 이상이면 실패이므로 while문을 빠져나가 -1을 리턴한다.
• 그렇지 않다면 4방향 이동할 위치를 탐색한다.
• 고려해줄 경우는 다음과 같다.
  • 두 동전 모두 이동할 위치가 격자 밖이면 continue
  • 위에서 걸러지므로 둘 중 한 동전만 격자 밖이면 현재 위치값 + 1한 값을 리턴한다.
  • 이동할 곳이 벽이면 이동하지 않으므로 원 위치 시킨다.
  •  이동할 곳이 첫 방문일 경우에만 새 위치에 현 위치 + 1한 값으로 표시하고 큐에 담는다.

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline
from collections import deque

dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)

def bfs(ar, ac, br, bc):
    check = [[[[-1] * M for _ in range(N)] for _ in range(M)] for _ in range(N)]
    check[ar][ac][br][bc] = 0
    Q = deque([(ar, ac, br, bc)])
    while Q:
        ar, ac, br, bc = Q.popleft()
        # 10번보다 많이 눌러야 한다면 실패
        if check[ar][ac][br][bc] >= 10:
            break

	# 4방향 이동할 위치 좌표
        for d in range(4):
            nar = ar + dr[d]
            nac = ac + dc[d]
            nbr = br + dr[d]
            nbc = bc + dc[d]

            # 두 동전 모두 밖으로 떨어지면
            if not (0 <= nar < N and 0 <= nac < M) and not (0 <= nbr < N and 0 <= nbc < M):
                continue

            # 동전 a, b 중에 하나만 밖으로 떨어지면
            if not (0 <= nar < N and 0 <= nac < M):
                return check[ar][ac][br][bc] + 1
            if not (0 <= nbr < N and 0 <= nbc < M):
                return check[ar][ac][br][bc] + 1

            # 이동할 곳이 벽이면 제자리
            if board[nar][nac] == "#":
                nar -= dr[d]
                nac -= dc[d]
            if board[nbr][nbc] == "#":
                nbr -= dr[d]
                nbc -= dc[d]

            # check 배열의 이동할 위치에 현 횟수 + 1한 횟수 표시, 이동할 위치 큐에 담기
            if check[nar][nac][nbr][nbc] == -1:
                check[nar][nac][nbr][nbc] = check[ar][ac][br][bc] + 1
                Q.append((nar, nac, nbr, nbc))
    return -1

# main
N, M = map(int, input().split())
ar, ac, br, bc = 0, 0, 0, 0
board = []
flag = True
for i in range(N):
    board.append(list(input().rstrip()))
    for j in range(M):
        if board[i][j] == "o":
            if flag:
                ar, ac = i, j
                flag = False
            else:
                br, bc = i, j
print(bfs(ar, ac, br, bc))

---

• 시간 : 140ms / 메모리 : 125252kb
• 고찰 : 예전에 풀었던 백준 구슬탈출 문제의 순한 맛 버전이었다. BFS 함수의 큰 틀은 비슷하다. 첫 제출 때 틀렸는데, 큐에서 꺼낸 좌표의 값이 10을 포함하지 않아서였다. 나는 초기값을 -1로 하여 있는 그대로 check 배열에 표시했기 때문에 뽑은 값이 이미 10이라면 바로 -1을 출력하도록 고치니 바로 pass했다. 이런 사소한 부분에서 실수가 나온다. 문제를 잘 읽고 하라는 대로 잘 짜자!