(24.11.11) BFS를 활용한 미로 최단 거리 찾기

가중치가 없는 그래프일 경우 Map<Integer, List<Integer>> 자료구조의 graph로 BFS를 노드 단위, 또는 neighbor 단위로 활용할 수 있다.

 

하지만, 미로에서는 가중치가 1인 그래프에 특정 조건(막혀있을 경우 해당 경로는 X)이 있기 떄문에

복잡할 수 있는 BFS 내지는 아래 비교를 위한 DFS를 좀더 다듬어서 사용할 수 있었다.

 

이전 DFS BFS 알고리즘에선 그 알고리즘의 플로우에 집중해서 정리를 해서 코드의 양이 길고, 효율적이지 못했기 때문에

이번에는 미로에서 BFS 를 이용한 최단 거리 알고리즘을 통해서

효율적으로 그래프에서 최단거리를 확인하는 방식을 정리하려고 한다.

---

최단경로 미로찾기

• “최단경로” 이기 때문에 BFS를 통해서 Queue 를 통해 같은 레벨의 node(neighbors)를 반복하면서 도착지점에 부합할 때 까지 Count 하는 방식
• 미로찾기의 기본적인 상하좌우를 실행하는 “방향키”를 활용

// 방향키
int[] dx = new int[]{-1, 1, 0, 0};
int[] dy = new int[]{0, 0, -1, 1};
...
// 반복문으로 방향이동 하면서 조건에 부합하는 경우
 for (int j = 0; j < 4; j++) {
                    int newX = x + dx[j];
                    int newY = y + dy[j];
                    ...

• DFS와 검증 알고리즘이 다름
  • DFS일 경우
    • 목적이 달성 되는지 재귀하면서 판단해야하므로 → 통과할경우, 먼저 방향키로 이동된 위치의 검증을 진행 → 부합할시 카운트 하면서 가능한 경우를 구하는 알고리즘
    • 따라서, 조건에 만족하지 않는지 파악 (or 조건문)
  • BFS일 경우
    • Queue(같은 레벨)의 노드들을 일단 다 방문 → 해당 노드들을 각각 상하좌우 반복해서 적용하면서 이동위치의 검증을 진행 → 조건에 부합할 시 카운트가 아닌, 큐에 넣어서 진행
    • 따라서, 검증 통과시 queue에 넣기 때문에, 검증 전에 반복에서 최종점에 도달하는지 확인을 할 필요가 있음

최단거리의 목표지점을 도달했을 경우, 해당 경로의 크기를 구하는 예제

• 단, 시작점은 0,0 도달점은 매개변수 2차원 배열 maps의 왼쪽 최하단

import java.util.*;

class Solution {
    // 이동 방향
    public int[] dx = new int[]{-1, 1, 0, 0};
    public int[] dy = new int[]{0, 0, -1, 1};
    
    public int solution(int[][] maps) {
        int width = maps[0].length;
        int height = maps.length;
        
        // 출발점 (0, 0)
        int[] start = new int[]{0, 0};
        // 목표점 (maps의 마지막 좌표)
        int[] end = new int[]{height - 1, width - 1};
        
        boolean[][] visited = new boolean[height][width];
        
        return bfs(maps, visited, start, end);
    }
    
    public int bfs(int[][] maps, boolean[][] visited, int[] start, int[] end) {
        // bfs 사용 큐
        Queue<int[]> queue = new LinkedList<>();
        
        // 시작점 설정
        visited[start[0]][start[1]] = true;
        queue.add(start);
        int count = 1;  // 출발점부터 카운트 시작
        
        // while문으로 큐 순회
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] current = queue.poll();
                int x = current[0];
                int y = current[1];
                
                // 목표점에 도달했을 경우
                if (x == end[0] && y == end[1]) {
                    return count;
                }
                
                // 상하좌우 반복
                for (int j = 0; j < 4; j++) {
                    int newX = x + dx[j];
                    int newY = y + dy[j];
                    
                    // 이동 좌표 검증
                    if (newX >= 0 && newX < maps.length &&
                        newY >= 0 && newY < maps[0].length &&
                        !visited[newX][newY] && maps[newX][newY] == 1) {
                        queue.add(new int[]{newX, newY});
                        visited[newX][newY] = true;
                    }
                }
            }
            count++;  // 한 단계 탐색이 끝나면 카운트 증가
        }
        
        // while 종료시 도달하지 못하면 실패
        return -1;
    }
}

• 이동 좌표에 따라서 검증을 진행한 새로운 좌표에 한해서 Queue에 등록, 방문처리
• 가로 세로 행 열 width height 관계를 조심
  • x좌표는 열에서 왔다갔다 하지만, 그건 maps가 그려진 상황에서에 해당
  • 따라서, x는 세로로갔다가, y로 가로로 가는 세팅을 해야, maps[][]에도 쓰일 수 있음

BFS 알고리즘읜 미로찾기 FLOW

1. 항상 시작점 start, 마지막점 end 설정
2. 방문처리용 visited 자료구조 설정(boolean 배열)
3. bfs 메서드 생성
   • 문제에서 주어지는 그래프(미로), visited, 시작점, 마지막점 매개변수
   • 경우에 따라 알고리즘이 요구하는 값을 반환 타입
     • 위의 경우 경로의 수이므로
   1. BFS 용 같은 레벨의 노드 저장용 queue 생성
   2. 시작 세팅
      • 시작점 visited, queue 에 등록
      • 기타 필요한 조건의 추가
   3. while(!queue.isEmpty()) { } 문으로 queue 순회 시작
      1. queue를 poll() 하면서 현재 노드(미로에선 좌표) 변수 설정
      2. 좌표가 최종점인지 검증
      3. → 도달할 경우 while문을 탈출하면서 bfs 메서드를 마감하므로 해당값 return
      4. b단계에 해당 안될 경우, 방향키로 움직이면서 검증
      5. → 검증이 통과된다면, 이동점 visited, queue 에 등록
   4. while문이 모두 돌 경우 = 3-b 단계에 걸리지 않을 경우, 도달할 수 없음

int size = queue.size();와 for (int i = 0; i < size; i++)를 분리 이유

• 변동하는 queue(방향키에서 검증을 통해서 queue 등록 중이기 때문에 현재 레벨을 처리하기 위해 따로 변수로 분리
  • BFS 에서는 같은 레벨 노드를 하나씩 돌면서 neighbor 노드가 조건에 부합할 때마다 다음 레벨을 위해서 queue에 들어감
  • 이 때, queue는 FIFO구조이기때문에 queue 추가가 되는 이상 무한 반복
• 같은 레벨의 queue의 노드 수만큼 반복하고 나서 count 해줘야하기때문에 같은 레벨의 queue 의 노드 수를 지정해서 계속 이어지지 않게 하기 위해

DFS 사용 전체 경로 탐색일 경우 (비교용)

import java.util.*;

class Solution {
    // 이동 방향 (상, 하, 좌, 우)
    public int[] dx = new int[]{-1, 1, 0, 0};
    public int[] dy = new int[]{0, 0, -1, 1};
    
    // 전체 경로 수를 저장할 변수
    private int count = 0;
    
    public int solution(int[][] maps) {
        int width = maps[0].length;
        int height = maps.length;
        
        // 출발점 (0, 0)
        int[] start = new int[]{0, 0};
        // 목표점 (maps의 마지막 좌표)
        int[] end = new int[]{height - 1, width - 1};
        
        boolean[][] visited = new boolean[height][width];
        
        visited[start[0]][start[1]] = true;  // 출발점 방문 처리
        
        // DFS 탐색 시작
        dfs(maps, visited, start, end);
        
        return count;
    }
    
    public void dfs(int[][] maps, boolean[][] visited, int[] current, int[] end) {
        int x = current[0];
        int y = current[1];
        
        // 목표 지점에 도달했을 경우
        if (x == end[0] && y == end[1]) {
            count++;  
            return;
        }
        
        // 상하좌우로 탐색
        for (int i = 0; i < 4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];
            
            // 미로 검증: 맵 범위 내, 방문하지 않았고, 벽이 아니어야 함
            if (newX >= 0 && newX < maps.length &&
                newY >= 0 && newY < maps[0].length &&
                !visited[newX][newY] && maps[newX][newY] == 1) {
                
                visited[newX][newY] = true;  // 방문 처리
                
                // 재귀 호출하여 경로 찾기
                dfs(maps, visited, new int[]{newX, newY}, end);
                
                // 백트래킹 (다시 방문 가능하게 함)
                visited[newX][newY] = false;  
            }
        }
    }
}

• DFS 특징의 백트래킹을 사용해서 다시 돌아갈 수 있도록 하는 것이 특징 → 벽이 나오면 다시 되돌아가서 시작해야하기 때문에
• 전체 클래스 변수를 사용
  • BFS일 경우에는 전체 수를 세는 것이 아니라 최적의 가장 짧은 거리를 계산하는 것 하나만을 다루기 때문에 클래스 변수 사용할 필요가 없음

---

과거에 해당 전체탐색 알고리즘을 하나하나 뜯어보느라 너무 방대하게 작성했던알고리즘 코드를 

좀더 깔끔하게 정리했기 때문에,

실제 로직에서 클린코드로 활용할 수 있을 것이라생각한다.