백준 17836 공주님을 구해라! 파이썬 풀이

난이도 : 골드5

풀이일 : 2403262

https://www.acmicpc.net/problem/17836

17836번: 공주님을 구해라!

---

링크로 이동하기 귀찮은 분들을 위한 문제캡쳐

---

풀이 코드

import sys
from collections import deque

N, M, T = list(map(int, sys.stdin.readline().split()))
castle = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
visited = [[0] * M for _ in range(N)]  # 각 칸 도착 시간
gram = 0  # 그람 활용 목적지 도착 시간
di, dj = [-1, 1, 0, 0], [0, 0, -1, 1]  # 상하좌우 이동방향

queue = deque()
queue.append((0, 0))  # 출발지
while queue:
    i, j = queue.popleft()
    time = visited[i][j]  # 현재까지 소요시간
    for k in range(4):
        ni, nj = i + di[k], j + dj[k]  # 상하좌우 확인
        if 0 <= ni < N and 0 <= nj < M:
            # 그람 최초 발견 시, 그람 활용 도착 시간 저장
            if castle[ni][nj] == 2 and not gram:
                gram = time + N - ni + M - nj - 1
            else:
                # 벽이 없는 길 이동 시간 BFS 탐색
                if not visited[ni][nj] and not castle[ni][nj]:
                    visited[ni][nj] = time + 1
                    queue.append((ni, nj))

sol = visited[N - 1][M - 1]  # 도보로 목적지 도착 가능 시
if gram and sol:  # 그람, 도보 모두 목적지 도착 가능 시 작은 값 저장
    sol = gram if gram < sol else sol
elif gram and not sol:  # 그람으로만 목적지 도착 가능 시 저장 값 변경
    sol = gram

# 도착 시간이 0이 아니고 T보다 작을 때 출력, 조건 미충족 시 Fail 출력
print(sol if sol and sol <= T else "Fail")

• castle : 성 내부 구조 2차원 배열이다.
• gram : 그람을 찾은 경우, 공주의 위치가 고정되어 있으므로, 그람의 위치에서 공주의 위치까지 걸리는 시간을 계산하여 저장해준다. 이때, 그람 최초 발견 시 계산한 값이 그람 활용 최소 루트이므로 이미 그람 활용 시간을 계산하여 그람이 0이 아닌 경우는 무시한다.
• visited : 각 칸까지 걸리는 시간을 저장하는 2차원 배열이다. 그람을 활용하지 않은 경우에 걸리는 시간을 저장한다. 공주의 위치까지 걸리는 시간은 visited[N-1][M-1] 칸에 저장된다.
• di, dj : 상,하,좌,우 용사가 움직일 수 있는 네 방향을 탐색하기 위한 방향좌표 역할을 한다. 용사의 현재위치에서 castle 배열을 확인하여 벽이 아닌 곳으로 이동하거나, 그람을 찾는 데에 사용한다.
• time : visited[i][j]를 계속 타이핑 하는 것보다 선언을 한 번 해주는 것이 더 직관적인 것 같아 추가한 변수다.
• sol : 최종적인 답안을 저장한다.
  • 최초 visited[N-1][M-1]로 저장한다.
  • 그람 활용, 도보 모두 목적지에 도착이 가능하다면 둘 중 작은 값으로 sol을 재할당한다.
  • 그람 활용 시에만 목적지 도착이 가능하다면, gram 값으로 sol을 재할당한다.
  • 도보로만 목적지 도착이 가능한 경우, 이미 도보 값이 sol에 할당되어 있으므로 따로 처리해주지 않아도 된다.
  • 두 경우 모두 목적지 도착이 불가능한 경우, sol은 0으로 할당되어 있어 따로 처리해주지 않아도 된다.
• 도착 시간이 0이 아니고, 제한시간 T 이하라면, 계산한 최소 도착 시간 sol을 출력하며, 조건을 만족하지 못할 시 Fail을 출력한다.

---

느낀점

• 제일 좋아하고 많이 푼 문제가 BFS 문제인 것 같은데, 조건들을 충분히 고려하지 않아 여러번 틀렸다. 문제를 보면 충분히 로직을 생각하고 내 방법의 문제점, 필요성을 충분히 생각한 후에 코드로 옮길 수 있도록 하자.