[백준] 17836. 공주님을 구해라!(python, 파이썬)

문제

17836. 공주님을 구해라!

📌 아이디어

검을 사용하는 경우와 사용하지 않는 경우 크게 2가지로 나누어 문제에 접근했습니다. 검을 만난 경우는 더 이상 탐색을 하지 않고 거리를 계산해 정답을 갱신했습니다. 처음에는 검을 사용한 경우가 무조건 최소 경로라 생각했지만, 그 반대의 경우가 최소인 경우도 존재해 문제 해결에 어려움이 있었습니다.

1. BFS 탐색을 통해 0인 경우 이동하고 좌표와 이동 시간을 큐에 추가합니다.
2. 2를 만난 경우를 거리를 계산해 정답을 갱신합니다.
3. 1을 만난 경우는 따로 고려할 필요가 없습니다.
4. N-1, M-1에 도달한 경우 탐색을 종료하고 정답을 반환합니다.
   
   

📌 코드

from collections import deque

def bfs():
    que = deque()
    que.append([0, 0, 0]) # 좌표, 이동시간

    visited = [[0] * M for _ in range(N)]
    visited[0][0] = 1

    ans = 10**9
    while que:
        ci, cj, time= que.popleft()

        if time > T: # 시간을 초과한 경우 종료
            break

        if (ci, cj) == (N-1, M-1): # 목적지에 도달하면 정답 갱신
            ans = min(ans, time)
            break

        for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            ni, nj = ci + di, cj + dj

            if 0 <= ni < N and 0 <= nj < M and visited[ni][nj] == 0:
                if arr[ni][nj] == 0: # 칼을 사용하지 않는 경우
                    visited[ni][nj] = 1
                    que.append([ni, nj, time+1])

                elif arr[ni][nj] == 2: # 칼을 사용하는 경우
                    visited[ni][nj] = 1
                    rst = abs(N-1-ni) + abs(M-1-nj) + time + 1
                    if rst <= T:
                        ans = rst

    if ans > T: # 시간을 초과한 경우 실패
        return 'Fail'
    return ans

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

print(bfs())

피드백 및 개선점은 댓글을 통해 알려주세요😊