[알고리즘] BFS 입문(JAVA)

BFS

프로그래머스 게임 맵 최단거리 문제를 통해 처음 bfs 를 접해보았다. 

bfs 가 무엇인가 맛보고 이해하기에 좋은 문제인것 같다.

dfs 로 풀어보려고 안간 힘을 써봤지만 실패했다. 

최단거리 문제는 대표적인 bfs 문제라고 하며, Queue 를 이용한다.

 

---

풀이

1. 너비 우선 탐색 알고리즘을 이용하여 탐색
2. queue 에서 시작 좌표 값(0, 0)을 꺼내서 visited 에 방문 여부 겸 이동 수를 기록 후 사방탐색 시작
3. 사방탐색 조건에 의해 사방이 막혔거나 방문한 길 밖에 없는 경우의 수는 걸러지고 남은 경우들은 각자의 최선의 선택으로 탐색
4. 사방탐색 후 다음 좌표를 queue 에 저장하고 다음 좌표의 방문 여부 겸 이동 수를  visited 에 기록
5. 각자의 최선의 선택으로 탐색한 경우만 남았으므로 가장 먼저 queue 가 비어서 탐색을 진행할 수 없는 경우가 최단거리
6. 탐색 종료 후 도착점 좌표에 해당하는 visited 의 값을 반환(0 이면 방문한 적이 없다는 뜻이므로 -1)

최종 코드

import java.util.*;
class Solution {
    int n = 0;
    int m = 0;
    // 사방탐색용 dx, dy
    int[] dx = {1, 0, -1, 0};
    int[] dy = {0, 1, 0, -1};

	// 너비 우선 탐색
    public void bfs(int[][] maps, int[][] visited, int x, int y) {
    	// 방문 여부 겸 이동 수를 해당 시작 좌표에 기록
        visited[y][x] = 1;
        // queue 초기값 (0, 0)
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[]{y, x});
        
        // queue 에서 현재 좌표를 꺼내서 사용
        // queue 가 비었다는건 더 이상 탐색할 수 없다는 뜻
        while (!que.isEmpty()) {
            int[] now = que.poll();
            y = now[0];
            x = now[1];
			
            // 사방탐색 조건
            // 1. y, x 가 최대값(n, m)을 넘지 않음
            // 2. 방문하지 않은 좌표(visited = 0 인 좌표)
            // 3. 해당하는 maps 의 값이 1인 좌표
            for (int i = 0; i < 4; i++) {
                if (x + dx[i] >= 0 &&
                   x + dx[i] < m &&
                   y + dy[i] >= 0 &&
                   y + dy[i] < n &&
                   visited[y + dy[i]][x + dx[i]] == 0 &&
                   maps[y + dy[i]][x + dx[i]] == 1) {
                    // 탐색 조건에 만족할 시 다음 좌표에 방문 여부 겸 이동 수를 기록
                    visited[y + dy[i]][x + dx[i]] = visited[y][x] + 1;
                    // 다음 좌표를 queue 에 추가
                    que.add(new int[]{y + dy[i], x + dx[i]});
                }
            }
        }
    }

    public int solution(int[][] maps) {
        n = maps.length;
        m = maps[0].length;
        int[][] visited = new int[n][m];
        // 너비 우선 탐색 시작
        // 초기값 (0, 0) 설정
        bfs(maps, visited, 0, 0);

        // 도착점(visited) 의 값을 확인
        // 0 이면 방문한 적이 없으므로 -1
        // 0 이 아니면 visited 의 해당 값이 이동 수를 의미
        return visited[n -1][m -1] == 0 ? -1 : visited[n -1][m -1];
    }
}