백준 17836 - 공주 구출 [bfs]

"""
17836 백준
"""

from collections import deque
H, W, T = map(int, input().split())
arr = [list(map(int, input().split())) for i in range(H)]
dirs = [
    [0,1],
    [1,0],
    [0,-1],
    [-1,0]
]
def bfs():
    visited = [[False for i in range(W)] for j in range(H)]
    visitSword = [[False for i in range(W)] for j in range(H)]
    q = deque([[0,0,0,0]])
    visited[0][0] = True
    while q:
        y, x, t, sword = q.popleft()
        if y == H -1 and x == W-1:
            if t > T:
                print("Fail")
            else:
                print(t)
            return
        if sword :
            for i in range(2):
                ny = y + dirs[i][0]
                nx = x + dirs[i][1]
                if 0 <= ny < H and 0 <= nx < W and not visitSword[ny][nx]:
                    visitSword[ny][nx] = True
                    q.append([ny,nx,t+1,1])
        else :
            for i in range(4):
                ny = y + dirs[i][0]
                nx = x + dirs[i][1]
                if 0 <= ny < H and 0 <= nx < W and arr[ny][nx] != 1 and not visited[ny][nx]:
                    if arr[ny][nx] == 2:
                        visitSword[ny][nx] = True
                        q.append([ny, nx, t + 1, 1])
                    else:
                        visited[ny][nx] = True
                        q.append([ny, nx, t + 1, 0])
    print("Fail")
bfs()

문제 설정이 재밌어서 재밌게 풀었던 문제.

처음에 visit 체크를 하나로 통일해서 풀었다가 실패떠서 원인을 곰곰히 생각해보니 검을 얻고 난 이후의 visit 체크는 따로 해줘야한다. 그렇지 않으면 다음의 테스트케이스를 통과하지 못한다.

 

테스트 케이스 공유

6 10 50
0 0 0 0 0 0 1 1 0 2
1 1 1 1 0 0 1 0 0 1
1 1 1 1 0 0 1 0 1 1
0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0

검을 오른쪽 위에서 얻고 바로 수직으로 내려오면 20시간만에 공주를 찾지만 만약 visit 배열을 하나로 체크하면 검을 얻고 난 이후에는 내려올 수가 없다.. 그냥 단순히 검을 얻고난 이후의 visit을 따로 체크해주면 되므로 어려운 문제가 아니었다.

---

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