[BOJ] 17836. 공주님을 구해라!(Python) / BFS

17836번: 공주님을 구해라!

재미있는 BFS 너비우선탐색 문제였다.

# 45분 소요

처음에 풀 때 한 번에 답이 나왔지만, 세세한 케이스들을 미처 다 생각하지 못해서 여러 번 제출하며 조건문을 계속 추가했고, 결국 맞았다!

기본적인 BFS 틀에서 내가 고려한 조건은 다음과 같다.

• 격자에서 이동 중 그람(2)를 만났을 때, 현 위치에서 목적지까지는 거리를 절댓값의 합(minTime)으로 구해 미리 저장해둔다.
• 목적지까지 정상 도달한 경우도 도중에 그람을 구했든 아니든 반드시! 해줘야 한다.
  • 목적지까지 도달하던 중에 그람을 구했다면, 정상적으로 도달했을 때까지의 시간과 그람 구해서 직통으로 온 시간의 최솟값을 리턴한다.
  • 그람을 구하지 못했다면, 정상적으로 도달한 시간을 그대로 리턴한다.
• 목적지까지 정상적으로 도달하지 못한 경우,
  • 그람을 구했다면, 목적지까지 도달할 수 있었다는 뜻이므로 minTime을 리턴한다.
  • 그람을 구하지 못했다면, 목적지 도달할 수 없었으므로 공주를 구할 수 있는 최대 시간인 T보다 1큰 수를 리턴한다.
• bfs() 함수로 구한 값(temp)이 T보다 작거나 같으면 공주 구했으므로 temp 그대로 리턴, 그렇지 않다면 공주 구하지 못해 "Fail" 리턴한다.

주어진 TC 이외에도 pass를 받는데 결정적으로 도움을 준 간단한 반례가 있다.

3 3 100
0 1 2
0 1 1
0 0 0

정답 : 4

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

---

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

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

def bfs(sr, sc):
    visited = [[-1] * M for _ in range(N)]
    visited[sr][sc] = 0
    Q = deque([(sr, sc)])
    gramTime = 0
    while Q:
        r, c = Q.popleft()
        if (r, c) == (N-1, M-1):    # 목적지까지 정상 도달
            if gramTime:
                return min(visited[r][c], gramTime)
            return visited[r][c]

        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            if not (0 <= nr < N and 0 <= nc < M):       # 격자 밖이면
                continue
            if A[nr][nc] == 1 or visited[nr][nc] > -1:  # 벽이거나 이미 방문했다면
                continue

            visited[nr][nc] = visited[r][c] + 1
            Q.append((nr, nc))
            if A[nr][nc] == 2:      # 그람 구했다면 현 위치에서 목적지까지 직통시간 미리 구함
                gramTime = visited[nr][nc] + (abs(N-1-nr) + abs(M-1-nc))

    # 목적지까지 정상적으로 도달하지 못한 경우
    if gramTime:
        return gramTime
    return T + 1	# 실패한 경우로 처리

# main
N, M, T = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

temp = bfs(0, 0)
if temp <= T:       # T시간 이내 도달
    print(temp)
else:
    print("Fail")

---

• 시간 : 144ms / 메모리 : 125404kb
• 고찰 : 어렵지 않은 문제라 생각하고 별 생각 없이 코드 짜서 제출했는데 도중에 여러번 틀려서 계속 조건을 추가하는 과정을 반복했다. 문제 처음 풀 때, 엣지 케이스들을 미리 다 고려해보고 조건문을 추가하면서 짜는 것이 시간 단축에 도움이 될 것이다.