[백준 17836번] 공주님을 구해라! - (python)

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

 

Idea

문제를 보고 처음 생각한 것은 당연히 BFS를 한번만 돌려서 답을 찾는 것이였다. BFS 방식으로 길을 탐색하다가 칼을 만난 이후로는 벽도 부술수 있게 코드를 작성하면 될거라고 생각했다. 

하지만 이 문제의 경우 그렇게 풀면 오답이고 칼이 없다고 생각하고 공주한테 가는 최소시간과 칼을 반드시 잡고 공주한테 가는 최소시간을 따로 구해야 한다. 

그 이유는 다음과 같은 경우를 생각해 보면 알 수 있다.

 

 

이 경우는 칼을 잡기 위해 올 수 있는 길이 아래 한 가지 뿐이고 해당 칼을 잡은 뒤에는 왔던 길이 이미 방문처리가 되어있어서 다시 지나갈 수 없다. 하지만 가장 빠른 길은 칼을 잡고 다시 아래로 내려가고 벽을 부순뒤에 바로 공주에게 가는 길이다. 

 

따라서 BFS를 한번에 돌린다면 칼을 잡은 뒤에 그동안 방문처리 해준 배열을 초기화 해줘야 하는데 초기화를 하면 다른 경로까지 꼬여서 이방법말고 칼을 반드시 찾아서 들고 공주를 구하러 가는 최단 거리와 칼 없이 가는 최단 거리를 각각구해 더 작은 값을 선택하면 된다.

 

코드

from collections import deque # 큐 사용을 위해 

N, M, T = map(int, input().split())
castle = []
for _ in range(N):
    tmp = list(map(int, input().split()))
    castle.append(tmp)

dx = [0, 0, -1, 1] # 격자판에서 이동할 수 있는 경우 4가지 저장
dy = [1, -1, 0, 0]
hour = [[-1] * M for _ in range(N)] # 각 격자판 위치에 도달하는데 걸리는 최소 시간을 저장할 배열 초기화


def normal(): # 검 없이 최단거리
    visited = [[False] * M for _ in range(N)] 
    q = deque()
    q.append((0, 0))
    visited[0][0] = True
    hour[0][0] = 0
    while q:
        x, y = q.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < N and 0 <= ny < M: # index 범위 체크
                if visited[nx][ny] == False and castle[nx][ny] == 0: # 방문 안했고 길인곳만 갈수있게
                    q.append((nx, ny))
                    visited[nx][ny] = True
                    hour[nx][ny] = hour[x][y] + 1 # 시간 정보 저장

    if hour[N-1][M-1]==-1: # 출구에 갈수가 없을때
        return T + 1    # 주어진 최대 시간보다 1 크게 (Fail 출력을 위해서)
    else:
        return hour[N-1][M-1]


def sword(): # 검 들고 최단거리
    visited = [[False] * M for _ in range(N)]
    q = deque()
    q.append((0, 0))
    visited[0][0] = True
    hour[0][0] = 0
    while q:
        x, y = q.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < N and 0 <= ny < M and visited[nx][ny]==False:
                if castle[nx][ny] == 2: # 검을 찾은 경우는 벽을 신경쓸 필요가 없기때문에 그냥 거리 계산식으로 거리를 구한다.
                    dis = hour[x][y] + 1 + (N - 1) + (M - 1) - (nx + ny) # (N-1,M-1) 이 항상 공주가 있는 위치 이므로 절대값으로 계산할 필요 X
                    return dis
                elif castle[nx][ny] == 1: # 벽인 경우는 pass
                    continue
                else: # 길인 경우는 계속 탐색
                    q.append((nx, ny))
                    visited[nx][ny] = True
                    hour[nx][ny] = hour[x][y] + 1

    if hour[N-1][M-1]==-1: # 출구에 갈수가 없을때
        return T + 1
    else:
        return hour[N-1][M-1]


first = normal()
hour = [[-1] * M for _ in range(N)] # 시간 저장 배열 reset
second = sword()
result = min(first, second)

if result > T:
    print('Fail')
else:
    print(result)