BFS 최단경로 역추적하는 방법 배우기

1. 문제

 

24463번: 미로 (acmicpc.net)

24463번: 미로

 

 

입구에서 출구로 가는데, 최단 경로가 아닌 경로는 모두 @로 바꿔서 표시하는 문제

 

 

2. DFS 풀이

 

최단 경로가 아닌 경로를 찾는게 그냥 찾을려하면 생각보다 까다롭다

 

아이디어의 핵심은 이동할 수 있는 모든 위치 .을 먼저 @로 바꿔놓는다

 

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

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

start_target = []

for y in range(n):
    
    for x in range(m):
        
        if maze[y][x] == '.':
            
            maze[y][x] = '@'

 

그리고 입구와 출구를 찾는다

 

문제 조건에 따라 미로 가장자리에 존재하는 . 2곳이 입구와 출구가 된다

 

이제 .은 @로 바뀌었으니까..

 

for y in range(n):
    
    if y == 0 or y == n-1:
        
        for x in range(m):
            
            if maze[y][x] == '@':
                
                start_target.append((x,y))
    
    else:
        
        if maze[y][0] == '@':
            
            start_target.append((0,y))
        
        elif maze[y][m-1] == '@':
            
            start_target.append((m-1,y))

 

 

DFS를 수행해서 경로 탐색을 진행한다

 

x,y에서 출발해서 z,w로 가는 것을 목표로 한다

 

def dfs(x,y,z,w,n,m,maze):
    
    if x == z and y == w:
        
        return True

 

z,w로 왔으면 return하면서 재귀 탐색을 중단시켜

 

z,w로 오지 못했으면... 사방향 델타 탐색을 수행

 

배열의 범위를 벗어나지 않아야하며, @로만 이동 가능하다

 

    else:

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

            if dx >= 0 and dy >= 0 and dx <= m-1 and dy <= n-1 and maze[dy][dx] == '@':

 

visited 배열 대신에 maze를 그대로 사용하면 된다

 

방문했으면 @를 .으로 바꿔주고 다음 좌표 dx,dy에 대해 dfs를 들어가면 된다

 

                maze[dy][dx] = '.'

                find = dfs(dx,dy,z,w,n,m,maze)

 

근데 dx,dy가 True로 출구를 찾았으면... 더 이상 탐색할 필요가 없으니까 계속 True를 return해서 더 이상 탐색하지 않도록 막아준다

 

                maze[dy][dx] = '.'

                find = dfs(dx,dy,z,w,n,m,maze)

                if find:
                    
                    return True

 

True를 return하지 못할 수도 있잖아..

 

그런 경우에는 다시 갈림길로 되돌아가면서 .으로 바꾼 것을 @로 되돌려놔야지

 

이런 dfs 테크닉은 많이 했었지..?

 

                maze[dy][dx] = '@'
        
        return False

 

이동하면서 @를 .으로 바꿔놓으면 최단 경로가 아닌 경로는 모두 @이고 최단 경로는 .이 된다

 

출구로 통과하면 return해서 더 이상 탐색하지 않도록 하면 되고

 

출구로 통과하지 못하면 다시 되돌아가면서 .으로 바꾼 것을 @로 바꿔주면 되겠다

 

from sys import stdin
import sys

sys.setrecursionlimit(50000)

def dfs(x,y,z,w,n,m,maze):
    
    if x == z and y == w:
        
        return True
    
    else:

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

            if dx >= 0 and dy >= 0 and dx <= m-1 and dy <= n-1 and maze[dy][dx] == '@':
                
                maze[dy][dx] = '.'

                find = dfs(dx,dy,z,w,n,m,maze)

                if find:
                    
                    return True

                maze[dy][dx] = '@'
        
        return False
         
n,m = map(int,stdin.readline().split())

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

start_target = []

for y in range(n):
    
    for x in range(m):
        
        if maze[y][x] == '.':
            
            maze[y][x] = '@'

for y in range(n):
    
    if y == 0 or y == n-1:
        
        for x in range(m):
            
            if maze[y][x] == '@':
                
                start_target.append((x,y))
    
    else:
        
        if maze[y][0] == '@':
            
            start_target.append((0,y))
        
        elif maze[y][m-1] == '@':
            
            start_target.append((m-1,y))

x,y = start_target[0]
z,w = start_target[1]

maze[y][x] = '.'

dfs(x,y,z,w,n,m,maze)

for row in maze:
    
    print(''.join(row))

 

입구에서 출구를 찾는 모든 경로를 탐색하고 난다면..

 

maze를 순회해서 각 한줄씩 문자열로 바꿔서 출력하면 되겠지

 

 

3. BFS 풀이

 

BFS로 풀어볼려하면 보통 어려운게 아니다..

 

최단 경로의 길이는 쉽게 찾아도 최단 경로 그 자체를 찾기는 까다롭다

 

고수의 풀이를 좀 배워보자

 

먼저 미로의 .을 @로 바꿔놓는다

 

n,m = map(int,input().split())

maze = [list(input()) for _ in range(n)]

#이동할 수 있는 .을 @로 바꿔놓는다

for y in range(n):
    
    for x in range(m):
        
        if maze[y][x] == '.':
            
            maze[y][x] = '@'

 

가장자리를 탐색해서 입구와 출구를 찾는다

 

n,m = map(int,input().split())

maze = [list(input()) for _ in range(n)]

#이동할 수 있는 .을 @로 바꿔놓는다

for y in range(n):
    
    for x in range(m):
        
        if maze[y][x] == '.':
            
            maze[y][x] = '@'

#가장자리를 조사해서 입구와 출구를 찾는다
#.은 @로 바뀌었다

start = []

for y in range(n):
    
    if y == 0 or y == n-1:
        
        for x in range(m):

            if maze[y][x] == '@':

                start.append((x,y))

    else:

        if maze[y][0] == '@':

            start.append((0,y))

        elif maze[y][m-1] == '@':

            start.append((m-1,y))

 

 

먼저 출구까지 순방향 BFS를 수행해서 visited 배열에 최단 경로 길이를 표시해준다

 

방법은 visited[dy][dx] = visited[y][x] + 1로 많이 했었지

 

그리고 @인 부분만 이동 가능하다

 

from collections import deque

def bfs(x,y,z,w,n,m,maze):
    
    visited = [[0]*m for _ in range(n)]

    visited[y][x] = 1

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

    while queue:
        
        x,y = 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 and visited[dy][dx] == 0 and maze[dy][dx] == '@':
                
                visited[dy][dx] = visited[y][x] + 1

                if dx == z and dy == w:
                    
                    return visited
                
                else:
                    
                    queue.append((dx,dy))

 

이제 bfs를 수행해서 최단 경로 길이가 표시된 visited 배열을 얻어보자

 

#bfs 수행

x,y = start[0][0],start[0][1]
z,w = start[1][0], start[1][1]

visited = bfs(x,y,z,w,n,m,maze)

 

이제 최단 경로 역추적을 수행해보자..

 

어떻게 가능할까?

 

출구 z,w에서부터 시작해서 입구 x,y까지 탐색을 수행하면 되겠다

 

어떤 식으로 최단 경로를 찾아가야 할까? visited를 이용해보자

 

visited[w][z]에는 출구까지 오는 최단 경로 길이가 표시되어 있다

 

여기서 되돌아갈려면 어떨때 되돌아가야할까?

 

현재 위치 z,w에서 사방향 dz,dw를 돌아보겠지

 

여기서 @인 부분만 이동 가능하니.. @이면서도..

 

dz,dw의 visited값이 현재 visited[w][z]값보다 1 적은 곳으로 이동해야겠다

 

그래야 최단경로를 되돌아가는 것이니까

 

그러니까 현재 위치보다 1 적은곳으로만 이동해야하고 이동하면서 @를 .으로 바꿔주면 최단 경로를 표시하면서 이동할 것이다

 

#최단 경로 역추적 bfs

def bfs_tracking(z,w,x,y,n,m,maze,visited):
    
    queue = deque([(z,w)])

    while queue:
        
        z,w = queue.popleft()

        maze[w][z] = '.' #이동하면서 .으로 표시

        for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
            
            dz = z + ni
            dw = w + nj

            #배열의 범위는 벗어나지 말아야하고 @인 부분만 이동 가능함

            if dz >= 0 and dz <= m-1 and dw >= 0 and dw <= n-1 and maze[dw][dz] == '@':
                
                #z,w에서 visited값보다 1 적은 곳으로만 이동 가능하다
                if visited[dw][dz] == visited[w][z] - 1:
                    
                    queue.append((dz,dw))

 

이제 maze에는 최단 경로에 .으로 표시되어 있다

 

그러므로 maze를 순회해서 row를 문자열로 바꿔서 한줄씩 출력

 

from collections import deque
from sys import stdin

#순방향 bfs
#출구까지 가는 최단 경로 길이를 visited에 표시
def bfs(x,y,z,w,n,m,maze):
    
    visited = [[0]*m for _ in range(n)]

    visited[y][x] = 1

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

    while queue:
        
        x,y = 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 and visited[dy][dx] == 0 and maze[dy][dx] == '@':
                
                visited[dy][dx] = visited[y][x] + 1

                if dx == z and dy == w:
                    
                    return visited
                
                else:
                    
                    queue.append((dx,dy))

#최단 경로 역추적 bfs

def bfs_tracking(z,w,x,y,n,m,maze,visited):
    
    queue = deque([(z,w)])

    while queue:
        
        z,w = queue.popleft()

        maze[w][z] = '.' #이동하면서 .으로 표시

        for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
            
            dz = z + ni
            dw = w + nj

            #배열의 범위는 벗어나지 말아야하고 @인 부분만 이동 가능함

            if dz >= 0 and dz <= m-1 and dw >= 0 and dw <= n-1 and maze[dw][dz] == '@':
                
                #z,w에서 visited값보다 1 적은 곳으로만 이동 가능하다
                if visited[dw][dz] == visited[w][z] - 1:
                    
                    queue.append((dz,dw))
              
n,m = map(int,stdin.readline().split())

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

#이동할 수 있는 .을 @로 바꿔놓는다

for y in range(n):
    
    for x in range(m):
        
        if maze[y][x] == '.':
            
            maze[y][x] = '@'

#가장자리를 조사해서 입구와 출구를 찾는다
#.은 @로 바뀌었다

start = []

for y in range(n):
    
    if y == 0 or y == n-1:
        
        for x in range(m):

            if maze[y][x] == '@':

                start.append((x,y))

    else:

        if maze[y][0] == '@':

            start.append((0,y))

        elif maze[y][m-1] == '@':

            start.append((m-1,y))

#bfs 수행

x,y = start[0][0],start[0][1]
z,w = start[1][0], start[1][1]

visited = bfs(x,y,z,w,n,m,maze)

#최단 경로 역추적
bfs_tracking(z,w,x,y,n,m,maze,visited)

for row in maze:
    
    print(''.join(row))