[Python] BOJ 17836 - 공주님을 구해라!

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

17836번: 공주님을 구해라!

# 문제자체는 어렵지 않지만 엄청난 삽질을 한 문제이다.

# 처음에 문제를 제대로 읽지 않아 '그람'이 벽을 한번만 부술 수 있는 줄 알았다.

   그래서 '벽 부수고 이동하기' 문제처럼 visited배열을 3차원으로 만들어서 벽을 부셨을 때와

   벽을 부수지 않았을 때 2가지 상태를 저장했다. 물론, 이렇게도 푼 사람들도 많다.

   

# 하지만, 문제를 잘 읽어보니 '그람'이 부술수 있는 벽의 개수는 제한이 없다고 되어있다.

   따라서, 그람이 있는 위치 기준으로 도착점까지 맨해튼 거리를 바로 구하면 더 쉽게 답을 도출할 수 있다.

 

# bfs함수에서 공주님이 있는 곳에 도착했을 때 visited[x][y]-1과 gram중에 최솟값을 return 해준다.

     (처음에 visited[0][0]을 1로 시작했기 때문에 마지막에 -1을 해줘야 걸린 시간이 나온다.)

  

   그람이 있는 곳에 도착했을 때는 gram에 '현재까지 걸린 시간 + 공주님이 있는 곳까지의 맨해튼 거리'

    를 넣어준다. 나머지 경우는 그냥 bfs함수처럼 진행하면 된다.

 

# res에 bfs함수를 돌려서 return된 값을 넣어주고 그 값이 T보다 크면 'Fail'을 출력하고

   T이하이면 res를 출력한다. (res = 공주님을 구하는 데까지 걸린 시간)

 

import sys
from collections import deque
input = sys.stdin.readline
N, M, T = map(int,input().split())
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
m = [list(map(int,input().split())) for _ in range(N)]
q = deque()
visited = [[0] * M for _ in range(N)]

def bfs():
    gram = 10001
    q.append((0, 0))
    visited[0][0] = 1
    while q:
        x, y = q.popleft()
        # 공주님이 있는 곳에 도착했을 때
        if (x, y) == (N-1, M-1):
            return min(visited[x][y]-1, gram)
        # 그람이 있는 곳에 도착했을 때
        if m[x][y] == 2:
            gram = visited[x][y]-1 + N-1-x + M-1-y

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                if m[nx][ny] == 0 or m[nx][ny] == 2:
                    visited[nx][ny] = visited[x][y] + 1
                    q.append((nx, ny))
    return gram

res = bfs()
if res > T:
    print('Fail')
else:
    print(res)

(solved.ac 티어: 골드 5)

 

# 잊을만 하면 나오는 실수가 또 나왔다.. Fail을 출력하지 않고 fail을 출력해서 계속 틀렸다...

   또, visited를 3차원으로 선언하니 IndexError와 거의 보이지 않는 TypeError까지 난장판이었다.

    (3차원으로 푸는 건 좀 생각해봐야할 듯..)