3차원 BFS에서 조금은 섬세한 디테일 -공주님을 구해라!-

1. 문제

 

17836번: 공주님을 구해라! (acmicpc.net)

17836번: 공주님을 구해라!

 

(1,1)에서 용사가 (N,M)에 있는 공주님을 구하고자 움직일 수 있는 최단 시간을 구하는 프로그램을 작성

 

맵에 반드시 하나가 있는 전설의 명검 그람을 획득하였으면 제한 없이 벽을 부수고 이동할 수 있다

 

 

2. 풀이

 

분명 쉬운 문제지만... 너무 쉽게 생각하면 틀리기 쉽다고 해야하나..

 

잘못된 생각

>> 그람이 반드시 하나가 있다면, 그람을 획득하고 이동해야 최단시간?

 

>> 하지만 그람을 못얻는 경우도 분명 있을 수 있음(예: 벽에 둘러싸여서 그람으로 못감)

 

-----------------------------------------------------------------------------------------------------------------

 

visited배열로 3차원 배열.. 그람을 획득한 경우와 그람을 획득하지 못한 경우를 모두 포함하도록 만들자

 

왜냐하면.. 그람을 획득한 경우의 경로와 그람을 획득하지 못한 경우의 경로는 생각해본다면 중복이 가능하니까

 

from collections import deque
from sys import stdin

def bfs(n,m,T):
    
    sword = 0
    
    queue = deque([(0,0)])

    visited = [[[0,0] for _ in range(m)] for _ in range(n)]

    visited[0][0][0] = 1

 

sword는 그람을 획득한 경우 1로 하고 획득하지 못했으면 0으로 만들고

 

t = 0부터 시작해서 bfs를 수행

 

제한시간 T보다 커지면, break를 하고 찾지 못했다는 것을 나타내는 -1을 return하도록

 

    t = 0

    while queue:
        
        t += 1

        if t > T:
            
            break

 

 

매 t마다 큐에 존재하는 모든 경우를 순회해야.. 1초가 지난거니까

 

큐의 길이만큼 반복을 수행하는 기본 테크닉 적용

 

for _ in range(len(queue)):

 

사방으로 이동할 수 있는데 그람을 가지고 있는 경우와 그람을 가지고 있지 않은 경우

 

이동하는 제한이 서로 다를 것

 

그람을 가지고 있으면 maps[dy][dx]와 상관없이 이동 가능하고, 그람을 가지고 있지 않으면

 

maps[dy][dx]가 1이면 이동 불가능

 

for _ in range(len(queue)):
        
    x,y = queue.popleft()

    for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:

        dx = x + ni
        dy = y + nj

        if sword == 0: #검이 없는 경우

        else: #검이 있는 경우

 

 

검이 없는 경우에는 배열의 범위를 벗어나고 벽 maps[dy][dx] == 1이면 이동 불가능하다

 

if sword == 0: #검이 없는 경우

    if dx >= 0 and dx <= m-1 and dy >= 0 and dy <= n-1 and visited[dy][dx][sword] == 0 and maps[dy][dx] != 1:

        if maps[dy][dx] == 2:

            sword = 1 #검을 획득

        if dx == m-1 and dy == n-1:

            return t

        queue.append((dx,dy))
        visited[dy][dx][sword] = 1

 

 

그런데 돌아다니다가, maps[dy][dx] == 2이면 검을 획득했으므로 sword=1로 바꿔준다

 

그리고 이동하다가 dx가 m-1이고 dy가 n-1이면 공주를 만났으므로 t를 return

 

bfs니까, 만나는 순간 무조건 최솟값이 되니까 그 시간을 return하면 된다

 

이동가능한 경우 큐에 넣어주고,  visited를 1로 표시

 

검을 가지고 있는 경우에는 maps[dy][dx]와는 상관없이 이동 가능하다

 

else: #검이 있는 경우

    if dx >= 0 and dx <= m-1 and dy >= 0 and dy <= n-1 and visited[dy][dx][sword] == 0: #어디든 갈 수 있음

        if dx == m-1 and dy == n-1:

            return t

        queue.append((dx,dy,sword))
        visited[dy][dx][sword] = 1

 

3차원 배열로 visited를 만들었기 때문에,

 

검을 가지고 있는 경우와 검을 가지고 있지 않은 경우 경로가 중복되더라도 상관이 없는데 그러한 경우도 고려가 된다

 

반복문을 돌다가 return을 하지 못하면, 찾지 못한 것이므로 -1을 return

 

    return -1
        

n,m,T = map(int,stdin.readline().split())

maps = [list(map(int,stdin.readline().split())) for _ in range(n)]

result = bfs(n,m,T)

if result == -1:
    
    print('Fail')

else:
    
    print(result)

 

 

근데 이렇게 하면 틀리는데 왜냐하면

 

어떤분이 훌륭하게 지적한 글을 보았다

 

 

-------------------------------------------------------------------------------------------------------------------------------------------------------------

글 읽기 - 틀린 코드가 정답으로 인정됩니다. (acmicpc.net)

글 읽기 - 틀린 코드가 정답으로 인정됩니다.

 

 

30240505번의 틀린 코드가 맞았습니다로 나옵니다.

4 10 100
0 1 1 1 1 2 1 1 1 1
0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0

다음과 같은 테스트 케이스에서 14가 나와야 하는데 12가 나오는 코드가 정답으로 인정됩니다.

위의 테스트 케이스 같은 경우 무조건 그람을 먹고 이동해야 벽을 부수며 공주를 구할 수 있습니다.

그리고 제 코드에서는 북, 남, 동, 서 순서로 탐색을 진행하고, 그람을 먹는 순간 gram 변수를 1로 업데이트 해줍니다.

이 때 발생하는 문제는 i가 0일 때 그람을 발견한 것이 i가 1, 2, 3인 경우에도 그람을 먹은 것처럼 행동합니다.

좀 더 쉽게 설명해 보자면, 현재 위치에서 북쪽의 그람을 발견하는 순간 남, 동, 서쪽 모두 gram을 먹은 상태로 가정하고 움직이게 됩니다.

 

------------------------------------------------------------------------------------------------------------------------------------------------

 

큐에 (x,y)만 넣었기 때문에... 모든 bfs로 탐색한 경로에서 sword값을 공유하고 있는데

 

그람을 먹어버리면, 실제로 그람을 먹지 않은 경로 조차도 그람을 먹은 것처럼 행동해버리기 때문에 오답이 나온다

 

그래서 큐에 (x,y,sword)까지 같이 넣어서 행동을 다르게 해줘야한다..

 

(visited는 다르게 해줘놓고... 좌표는 똑같이 해주면 어쩌자고...)

 

from collections import deque
from sys import stdin

def bfs(n,m,T):
    
    #그람 획득 여부
    sword = 0
    
    #좌표,그람 획득 여부
    queue = deque([(0,0,0)])
    
    #3차원 방문 배열, x,y,그람여부
    visited = [[[0,0] for _ in range(m)] for _ in range(n)]

    visited[0][0][0] = 1

    t = 0 #시간

    while queue:
        
        t += 1

        if t > T: #제한시간을 넘어가면 반복문 종료
            
            break
        
        for _ in range(len(queue)): #매 초마다 큐의 길이만큼 탐색 수행
        
            x,y,sword = queue.popleft()

            for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
                
                dx = x + ni
                dy = y + nj

                if sword == 0: #검이 없는 경우
                    
                    #벽은 이동 불가능
                    if dx >= 0 and dx <= m-1 and dy >= 0 and dy <= n-1 and visited[dy][dx][sword] == 0 and maps[dy][dx] != 1:
                        
                        #탐색하다가 그람을 만나면...
                        if maps[dy][dx] == 2:
                            
                            sword = 1 #검을 획득
                        
                        #탐색하다가 목표지점에 도달한다면 그것이 최단시간
                        if dx == m-1 and dy == n-1:
                            
                            return t
                        
                        queue.append((dx,dy,sword))
                        visited[dy][dx][sword] = 1
                
                else: #검이 있는 경우
                    
                    #maps와는 상관없이 이동가능
                    if dx >= 0 and dx <= m-1 and dy >= 0 and dy <= n-1 and visited[dy][dx][sword] == 0: #어디든 갈 수 있음
                        
                        #탐색하다가 목표지점 m-1,n-1에 도달하면 그것이 최단시간
                        if dx == m-1 and dy == n-1:
                            
                            return t

                        queue.append((dx,dy,sword))
                        visited[dy][dx][sword] = 1
    
    #반복문이 끝나더라도 return하지 못하면 목표지점에 도달하지 못했다
    return -1
        

n,m,T = map(int,stdin.readline().split())

maps = [list(map(int,stdin.readline().split())) for _ in range(n)]

result = bfs(n,m,T)

#목표지점에 도달하지 못하면..
if result == -1:
    
    print('Fail')

#목표지점에 도달했으면..
else:
    
    print(result)