[프로그래머스] Lv.2 리코쳇 로봇 [풀지 못했던 이유 + 코드 + BFS가 왜 최단 경로를 보장할까]

구현 & BFS & 시뮬레이션

https://school.programmers.co.kr/learn/courses/30/lessons/169199

프로그래머스

 

코드

from collections import deque

def bfs(r, c, n, m, board):
    visited = [[0] * m for _ in range(n)]
    visited[r][c] = 1
    queue = deque([[r, c]])
    
    answer = -1
    
    while queue:
        q = queue.popleft()
        x, y = q[0], q[1]
        
        if board[x][y] == "G":
            
            answer = visited[x][y] - 1
            break
            
        dx = [(-1, 0), (0, -1), (1, 0), (0, 1)] 
        
        for idx in range(4):
            nx, ny = x, y
            while True:
                nx += dx[idx][0]
                ny += dx[idx][1]
                
                if nx < 0 or nx >= n or ny < 0 or ny >= m or board[nx][ny] == "D":
                    nx -= dx[idx][0]
                    ny -= dx[idx][1]
                    break
            
            if not visited[nx][ny]:
                visited[nx][ny] = visited[x][y] + 1
                queue.append([nx, ny])
    return answer
    
def solution(board):

    answer = 0
    n = len(board)
    m = len(board[0])
    for i in range(n):
        for j in range(m):
            if board[i][j] == "R":
                answer = bfs(i, j, n, m, board)
    return answer

 

설명

 해당 문제는 BFS를 이용한 '최단 경로' 문제라고 보인다. 나는 최단 경로 문제를 처음 이 문제를 통해서 접해봤다. 그래서 문제의 조건은 이해가 되었는데 BFS에 대한 전반적인 이해도가 낮아 쉽게 풀지 못했던 문제이며 하루동안 고민해 보고 얻은 값진 경험을 적어보려고 한다. 그렇기 때문에 문제에 대한 깊은 이해도가 없을 수 있으며, 경험에 기반하여 작성된 글이기 때문에 부정확한 설명이 있을 수 있다.

 

 BFS라는건 '너비 우선 탐색' 정확한 뜻은 인터넷 검색을 통해서 자세히 나와 있으니 참고하면 좋을 것 같다. 간략하게만 이해해 보자면 현재 노드와 우선되는 노드를 기준으로 먼저 탐색을 진행한다는 것. 그렇기 때문에 DFS와 다른 차이점이라면 깊이가 한 정점의 끝까지 파고 내려갈 수 있는 깊이 우선 탐색에 비해서 가장 빠른 길을 먼저 찾을 수 있다. 근데 나는 이 문제를 BFS로 풀어야 된다는 걸 이론상으로는 알고 있었지만 왜 BFS가 최단 경로 알고리즘으로 불리는지는 이해할 수가 없었다. 그렇기 때문에 많은 시간을 이해하는데 투자했고, 그렇게 얻은 설명을 지금부터 문제에 적용하면서 다시 한번 이해해보려고 한다.

 

 '최단 경로 가장 빠른 경로가 어떤 경로이냐' 라는 문제로 볼 수 있다. 이 문제에서 요구하는 건 최소 이동 횟수다. 최소 이동 횟수라는 건 다른 말로 최대한 이동을 적게 하는 방법으로 빠르게 도착할 수 있는 길이라고 생각해 볼 수 있다. 왜냐하면 도착지가 정해져 있고 거기까지 가야 된다고 했을 때 최대한 적게 이동하는 방법은 오래 걸리지 않는 길로 가는 것이다. 그럼 비교적 오래 걸리는 길을 가는 것보다 오래 걸리지 않는 길을 가는 게 최단 경로의 목적이라고 할 수 있다.

 

 

그렇다면 이러한 최단 경로를 구할때 BFS가 왜 최단 경로를 보장하는가?

 

 

bfs는 위에서도 간략하게 작성했듯이 너비를 우선적으로 탐색한다 조금 더 풀어 해석하자면 내가 갈림길에 있다고 생각해 보자 해당 갈림길을 통해서 목적지에 도달해야 한다. 5개의 갈림길이 존재하고 있을 때 DFS 같은 경우는 이전 갈림길을 선택해서 현재에 왔을 때 또 이전갈림길과 관련된 곳을 먼저 가려고 하고 BFS 같은 경우는 항상 해당 갈림길에 서서 고민한다고 생각해 보자. 5개의 길중 어디를 가야 할지 그때 5개의 길을 모두 가보고 이렇게 가봤는데 없으면 그다음 처음부터 전부 가보자고 생각해 볼 수 있다. 이렇게 생각해 본다면 DFS는 이미 저 멀리 가고 있을 것이고 만약 DFS가 원하는 길이 아니라면 현재 내가 있는 5개의 갈림길에 돌아올 것이다. (목적지가 아닌 경우)

 

그러면 dfs는 한길만 파고 있을 때 나는 나와 가까운 갈림길 5개를 먼저 다 탐색해 보는 거다. 가정으로 해당 갈림길 중 한길이 도착지에 가장 빠르게 도착하는 길이라고 해보자. 그러면 dfs는 이미 '5개의 갈림길을 지나쳤다.'

 

여기서 해볼 수 있는 생각은 dfs가 가는 길 자체가 5개의 갈림길 중 가장 빠른 경로로 도착하는 길일 수도 있지만 그렇지 않을 수도 있다. 위 상황에서는 이미 해당 갈림길 중 한길이 최단경로의 길이라고 했을 때 저 멀리 dfs는 지나쳤다고 했으니 dfs는 최단경로의 길을 고른 게 아니다. 그럼 최단경로를 고를 가능성이 높아진 건 BFS가 될 것이다. 왜냐하면 아직 BFS는 5개의 길 중 어느 곳도 가지 않은 상태에서 가려고 하는 준비상태기 때문이다. 그렇게 BFS가 한길씩 가보면서 목적지를 찾아본다. 그때 BFS는 해당 목적지를 찾는다. 여기서 찾았다고 한 문장을 조금 더 상상해 보자면 1,2,3,4,5 이렇게 5개의 길중 dfs는 1번 길을 먼저 파고든 것이고 실제 최단 경로 목적지는 5번에 있다고 한다면 BFS는 1,2,3,4,5번을 먼저 순서대로 가보면서 목적지를 찾게 되니까 dfs는 1번 길이 무한히 길다고 했을 때 1번 길을 무한히 긴 만큼 탐색하고 있을 것이다. 그때 BFS는 이미 5번 길에서 최단 경로를 찾게 된다.

 

그럼 여기서 알 수 있는 사실이 무엇일까. 단지 dfs가 최단경로를 찾기 어렵다고만 결론을 내야 하는 것인가? 어떻게 보면 틀린 말은 아니라고 생각한다. 실제로 저런 상황이라면 최단 경로를 dfs로 찾기에는 어렵거나 불가능할 테니까 여기서 BFS가 왜 최단 경로를 보장할까 라는 말을 좀 이어서 해보고자 한다.

 BFS는 위 상황처럼 자기와 관련된 위치(정점)에서부터 관련된 노드(갈림길)를 우선적으로 탐색을 한다고 한다. 그랬을 때 최단 경로가 이 처럼 현재 레이어 즉 현재 상태에서 찾을 수 있다면 그리고 그게 맞다고 한다면 노드를 더 뻗을 이유가 없다. 왜냐하면 이미 최단 경로는 해당 레이어에 존재하기 때문에. 그럼 이제 dfs는 생각하지 않고 BFS에서 그럼 어떤 노드들이 더 빠르게 도착할까. 목적지는 1,2,3,4,5번 노드 전부 도착할 수 있다고 봤을 때 5번이 최단경로라고 했으니 다른 경로들은 그럼 최단경로가 안 되는 건가? 안 되는 게 맞다면 왜 안될까

 

 나는 이걸 이해하기 위해서 이렇게 설명해보고 싶다. 최단경로에 도착하는 길이 있다고 했을 때 BFS로 찾은 그 경로는 다른 경로와 비교해 봤을 때 먼저 도착한다. 즉 먼저 도착한다는 건 다른 노드들이 그 길을 가기 위해서 길을 뻗고 있을 때 나는 이미 거기에 도착한 것이다. 결국 가장 먼저 도착한 게 최단 경로가 되기 때문에 다른 노드들은 최단으로 도착한 경로에 비해서 항상 더 많은 노드를 뻗는다. 그렇다면 간선의 개수를 많이 뻗어서 나갈수록 간선의 개수를 뻗어 다른 레이어에 도착할수록 최단 경로에서 항상 멀어진다. 따라서 최단경로라는 게 존재한다고 했을 때 먼저 도착한게 최단경로기 때문에 도착점을 두고 멀어지면 멀어질 수록 더 많은 길을 가야 된다는 얘기가 된다. 해당 목적지 까지 가는 길이 여러개 존재한다면 이미 방문한 것들은 이미 도착한 곳들이다 도착점을 향해서 가야 하는 길이라고 했을때 그럼 내가 도착했을 때 이미 도착해 있다면 내가 한발 늦은 거라고 볼 수 있다. 결국 내가 한 발 늦었다는 건 나보다 더 빨리 도착한 사람이 있다는 거니까 그리고 그 길을 따라가려고 했을 땐 이미 최단 경로라는 목적에 부합하지 않는 경로라는 사실을 알 수 있다. 

 

 

즉 최단 경로로 가는 길이 정해져 있다고 봤을 때 가장 먼저 그 길을 밟아 도착하는 경로가 가장 짧은 경로가 되며, 그 경로를 밟지 않고 다른 곳으로 이탈하면 할수록 최단 경로에서 멀어지게 되기 때문에 최단경로라는 타이틀을 달 수 없다.

 

 

 위 설명을 토대로 문제에 대해서 이 부분만 좀 고민해 본다면 G라는 도착점까지 가야 된다고 했을 때 여러 길이 존재할 것이다. 해당 문제에서는 막다른 길이나, 장애물을 만날때까지 가야 된다고 했기 때문에 끝까지 먼저 가야 한다는 사실을 알 수 있고 그렇게 하기 위해서 한 지점에서 갈 수 있는 곳이라면 그 방향으로 장애물이나, 더 이상 갈 수 없을때 까지 계속 간다. 그리고 BFS는 너비 우선이기 때문에 이후에 이 곳을 다시 방문하기 위해 queue에 다시 방문하기로 하고, 이쪽으로 왔던 길을 다시 되돌아가 원래 갈림길에 다시 도착하여 이번엔 다른 길로 간다. 그렇게 한번씩 다 간다는 것에서 너비우선 탐색을 하고 있다는 걸 알 수 있고, 그렇게 가면서 내가 걸어온 이동 횟수를 저장하여 여기까지 오는데 이 만큼 이동했다. 즉 도착지까지 가기 위해 이쪽에 도달하기 까지 나는 이정도 걸렸다를 알 수 있다. 다른 지점도 이 곳을 밟기 위해서 겹칠 수 있다. 그랬을때 만약 내가 여기에 더 빨리 왔다라면 위에 상황을 다시 생각해보자 내가 여기 더 빨리 왔다라면 먼저 내가 여기 밟았을텐데 그럼 내가 여기 방문하려고 했을때 이미 누가 방문했다는 건 이미 최단경로를 지나고 있는 사람 또는 무언가가 있다는 얘기가 되기 때문에 현재 상황에서 더 이상 나는 큐에 들어가서 방문을 할 필요가 없어진다. 문제에서 원하는 건 '최단 경로' 하나기 때문에 모든 경로를 다 탐색해서 출력해 보라는 게 아니기 때문이다. 따라서 이미 최단 경로를 밟고 있는 경로를 제외하고 나머지는 다른 길로 가게 되니 결국에는 그 도착지점을 찾기 위해 모두가 간선들을 뻗어나가며 도착하려 안간힘을 쓰지만 결국은 최단경로를 밟게 되는 한 지점만 가장 빠르게 도착한다는 걸 알 수 있고, 그때의 경로가 곧 최단 경로가 되기 때문에 해당 문제를 위처럼 풀 수 있다.