DFS/BFS 완전정복기5 -3차원 배열을 사용해야하는 경우-

1. 문제

 

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

2206번: 벽 부수고 이동하기

 

N*M 행렬에서 (0,0)에서 출발하여 (n-1,m-1)로 이동하는 최단 거리를 구하는 문제지만,

 

벽으로 표현되는 1을 뚫고 지나가서 거리가 줄어든다면 단 1번만 허용할때, 최단거리를 구한다면..?

 

 

2. 풀이

 

bfs로 벽이 있더라도, 단 1번도 뚫지 않았다면 1번만 뚫고 1번 뚫었다면 그 뒤로는 벽을 지나가지 않도록 bfs 탐색하면 될것 같았는데

 

2차원 배열로 deepcopy하면서 어떻게든 해볼려했더니 시간 초과남

 

bfs, dfs하면 2차원 배열만 생각하기 쉬운데 필요에 따라 3차원 배열도 쓸 수 있다는 것을 기억하자

 

벽을 뚫고 지나간 경우, 벽을 뚫고 지나가지 않은 경우를 각각 z=1, z=0으로 주어 x,y,z의 3차원 탐색을 수행하자

 

from collections import deque
from sys import stdin

def bfs(x,y,z,n,m,maps):
    
    if n == 1 and m == 1:
        
        return 1
    
    else:
    
        visited = [[[0]*2 for _ in range(m)] for _ in range(n)]

        visited[y][x][z] = 1

        queue = deque([(x,y,z)])

        while queue:

            x,y,z = queue.popleft()

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

                dx = x + ni
                dy = y + nj

                if dx >= 0 and dx <= m-1 and dy >= 0 and dy <= n-1:

                    if z == 0:

                        if maps[dy][dx] == '1' and visited[dy][dx][z+1] == 0:

                            visited[dy][dx][z+1] = visited[y][x][z] + 1

                            queue.append((dx,dy,z+1))

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

                                return visited[dy][dx][z+1]

                        elif maps[dy][dx] == '0' and visited[dy][dx][z] == 0:

                            visited[dy][dx][z] = visited[y][x][z] + 1

                            queue.append((dx,dy,z))


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

                                return visited[dy][dx][z]


                    else:

                        if visited[dy][dx][z] == 0 and maps[dy][dx] == '0':

                            visited[dy][dx][z] = visited[y][x][z] + 1

                            queue.append((dx,dy,z))


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

                                return visited[dy][dx][z]

        return -1
        
    
n,m = map(int,stdin.readline().split())

maps = [list(stdin.readline()) for _ in range(n)]

print(bfs(0,0,0,n,m,maps))

 몇가지 디테일을 살펴보자면

 

1) 먼저 n=1이고 m=1인 경우도 가능하므로, 그런 경우 바로 1을 return하도록 만든다

 

def bfs(x,y,z,n,m,maps):
    
    if n == 1 and m == 1:
        
        return 1

 

 

2) 다음에 visited 배열을 3차원 배열로 만드는데

 

z=0, z=1이 가능하고 y는 0~n-1, x는 0~m-1이 가능하므로 

 

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

 

이런식으로 만들면 되는데 그러면 visited 원소에 어떻게 접근하냐?

 

2차원에서 visited[y][x] 이런식으로 했으니까,.. 3차원은 visited[z][y][x]인가??

 

그건 아무 생각 없는거고

 

visited = [  [  [0,0], [0,0]  ] , [  [0,0], [0,0]  ]  ] 이런 느낌이라고 생각해보면

 

먼저 [  [0,0], [0,0]  ]랑 [  [0,0], [0,0]  ]에 접근해야하니까 첫번째 인덱싱은 y로 가야한다

 

visited[y]가 [  [0,0], [0,0]  ]이면, [  [0,0], [0,0]  ]고

 

이 안에서 [0,0]랑 [0,0]는 x원소니까 visited[y][x]가 [0,0], [0,0]에 들어가고..

 

다시 0에 접근할려면 visited[y][x][z]로 접근해야한다

 

기본적으로 x,y,z가 주어지면 visited[y][x][z]로 접근해야겠다

 

    else:
    
        visited = [[[0]*2 for _ in range(m)] for _ in range(n)]

        visited[y][x][z] = 1

 

3) 그리고 bfs 일반적인 방식으로 함수를 구현하는데 문제는 maps[y][x]가 1이라고 해서 못가는건 아니라는게 문제다

 

그래서 일단 n*m 배열의 범위를 벗어나지 않는 경우에 탐색을 시작할건데

 

        while queue:

            x,y,z = queue.popleft()

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

                dx = x + ni
                dy = y + nj

                if dx >= 0 and dx <= m-1 and dy >= 0 and dy <= n-1:

 

근데 탐색 좌표 (x,y,z)에서 z가 0이라면, 벽을 1번도 뚫지 않았으니까 벽을 뚫을 기회가 존재한다는 것이므로

 

maps[dy][dx] == '1'이고 visited[dy][dx][z+1] == 0이면 일단 벽을 통과하게 만들어서 거리를 구한다

 

어차피 모든 경로를 탐색해서 최단 거리가 도달 지점에 체크 될거니까.. 

 

당연하지만 벽으로 이동했다면 visited[dy][dx][z]가 아니라 visited[dy][dx][z+1]에 방문처리가 될거니까 visited[dy][dx][z+1] == 0을 검사한다

 

근데 주의할점은 벽을 통과하지 않은 z(=0)상태에서 이제 벽을 통과한 z+1상태로 이동할 것이므로

 

visited[dy][dx][z+1] = visited[y][x][z] + 1로 거리를 계산해야한다

 

                    if z == 0:

                        if maps[dy][dx] == '1' and visited[dy][dx][z+1] == 0:

                            visited[dy][dx][z+1] = visited[y][x][z] + 1

 

근데 z=0인 상태에서 maps[dy][dx] == '0'이고 visited[dy][dx][z] == 0인 경우는 이제 흔하니까..

 

일반적인 방식으로 visited[dy][dx][z] = visited[y][x][z] + 1 의 일반적인 거리 계산으로 구하고

 

z = 1이면, 이제 벽은 통과할 수 없으므로 visited가 0이고 maps가 '0'인 경우만 방문가능하다

 

                  else:

                        if visited[dy][dx][z] == 0 and maps[dy][dx] == '0':

                            visited[dy][dx][z] = visited[y][x][z] + 1

                            queue.append((dx,dy,z))

 

그리고 목적지로 도달가능하다면, 각각의 분기에서 dx == m-1, dy == n-1에 도달할 것이므로 그때 계산된 최종 visited값을 return하면 그만

 

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

    return visited[dy][dx][z]

 

근데 모든 탐색을 수행하더라도, 이 return문을 만나지 못했다면 도달 불가능이므로 while queue가 끝나면 return -1을 하면 된다

 

3) 그리고 어떤 곳에서 벽을 뚫은 것이랑 다른 곳에서 벽을 뚫은 것이랑 visited가 달라야하냐 이렇게 생각해서

 

이것도 copy해야하는거 아니냐? 이런 생각 할수도 있는데

 

그럴 필요 없겠지

 

xa,ya라는 곳에서 벽을 뚫으면 =0에 visited가 형성되고 있다가 그 지점에서는 visited[ya][xa][1]부터 visited 경로가 형성될거고

 

xb,yb라는 곳에서 벽을 뚫으면 z=0에 visited가 형성되고 있다가 그 지점에서는 visited[yb][xb][1]부터 visited 경로가 형성될거고...

 

서로 영향 없이 모든 경로를 탐색해서 최단 거리를 계산하는 자연스러운 bfs가 되는거라 

 

조금만 다시 생각해보면 너가 잘못생각했던게 맞음

 

 

3. 되돌아보기

 

dfs, bfs 무조건 2차원이 아니다

 

필요하다면 3번째 변수를 생각해서 3차원 배열도 생각할줄 아는 사람이 된다면 성장한것