[백준] 17836 공주님을 구해라!

문제

• (1, 1) 에서 (N,M) 까지 도달하는데 걸리는 최소 시간은?
  • 3 <= N, M <= 100
  • 상하좌우 인버한 칸으로 이동 가능하고, 각 칸을 이동하는데 1시간이 걸린다.
  • 벽이 있는 곳으로는 갈 수 없는데, 전설의 명검을 획득하면 벽을 부수고 이동할 수 있다.
• T 시간 이후에 도착하면 실패 
  • 1 <= T <= 10000

 

풀이

• (1,1) -> (N,M) 으로의 최단 시간과 (1,1) -> 명검 -> (N, M) 의 최단 시간 비교하기
  • 명검을 찾는 경우에만 명검 -> (N, M) 최단 경로 확인한다. 
  • 명검 -> (N,M) 최단 경로에서는 벽을 무시한다.
• bfs(start, visited, count, target, n, m)
  • start : 시작 칸의 x, y 좌표
  • visited : -1이면 아직 방문하지 않은 칸, 그외 숫자는 해당 칸까지의 최소 이동 횟수
  • count : 시작 칸까지의 이동 횟수
  • target : 갈 수 없는 칸의 숫자 ( 1일 때 벽)
    • 명검 -> (N, M) 최단 경로를 찾을 때는 target 값에 -1 을 줌으로써 벽을 무시하도록 한다.
  • n, m : 도착 칸의 x, y 좌표 

 

from collections import deque
from pprint import pprint

# 최단 경로 찾기
def bfs(start, visited, count, target, n, m):
    q = deque([start])
    visited[start[0]][start[1]] = count

    dx = (-1, 1, 0, 0)
    dy = (0, 0, -1 ,1)
    while q:
        x, y = q.popleft()
        
        if x == n and y == m:   # 마지막 칸 도달한 경우 stop
            break

        for i in range(4):      # 상하좌우 이동
            nx, ny = x+dx[i], y+dy[i]

            # 맵 안 범위고, 이동 가능한 칸이, 간 적 없는 칸이라면 Go
            if 0 <= nx < N and 0 <= ny < M and maps[nx][ny] != target and visited[nx][ny] == -1 :
                visited[nx][ny] = visited[x][y] + 1
                q.append((nx, ny))
    
    return visited[n][m]
            
# 입력 받기
N, M, T = map(int, input().split())
maps = []
sword = ()
for i in range(N):
    line = list(map(int, input().split()))
    for j in range(M):
        if line[j] == 2:    # 명검 위치 기록
            sword = (i, j)
    maps.append(line)

# (1, 1) -> (N, M)
visited = [[-1]*M for _ in range(N)]
cnt1 = bfs((0,0), visited, 0, 1, N-1, M-1)

# (1, 1) -> 명검 -> (N, M)
visited = [[-1]*M for _ in range(N)]
cnt2 = bfs((0,0), visited, 0, 1, sword[0], sword[1])
if cnt2 != -1:  # 명검 획득 가능한 경우만 명검 -> (N, M) 찾기
    visited = [[-1]*M for _ in range(N)]
    cnt2 = bfs(sword, visited, cnt2, -1, N-1, M-1)


# 정답 출력
if cnt1 == cnt2 == -1 :         # 도달 불가능한 경우
    answer = "Fail"
elif min(cnt1, cnt2) == -1 :    # 한 쪽만 도달 가능한 경우
    answer = "Fail" if max(cnt1, cnt2) > T else max(cnt1, cnt2)
else:                           # 둘 다 도달 가능한 경우
    answer = "Fail" if min(cnt1, cnt2) > T else min(cnt1, cnt2)

print(answer)

 

References

• 백준 17836
• 2023.04.30 오늘의 문제