[프로그래머스] 무인도 여행(Java), 너비 우선 탐색(BFS) 알고리즘

BFS(Breadth-First Search) 알고리즘에 대해

너비 우선 탐색이란?

루트 노드, 혹은 다른 임의의 노드에서 시작해 인접한 노드를 먼저 탐색하는 방법

 

- 시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

- 깊게 탐색하기 전에 넓게 탐색하는 것

- 두 노드 사이의 최단 경로나 임의의 경로를 찾고 싶을 때 이 방법을 선택

너비 우선 탐색의 특징

1. BFS는 재귀적으로 동작하지 않는다.

2. BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐를 사용한다. -> 즉, 선입선출 원칙으로 탐색

 

---

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/154540

프로그래머스

---

문제 풀이

import java.util.*;

class Point {
    int x;
    int y;
    
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class Solution {
    
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static ArrayList<Integer> list = new ArrayList<>();
    static boolean visited[][];
    static char map[][];
    static ArrayList<Integer> answerList = new ArrayList<>();
    
    public int[] solution(String[] maps) {
        
        // 1. maps을 2차원 배열 map으로 변환
        int a = maps.length;
        int b = maps[0].length();
        map = new char[a][b];
        
        for(int i=0; i<a; i++) {
            String str = maps[i];
            for(int j=0; j<b; j++) {
                map[i][j] = str.charAt(j);
            }
        }
        
        // 2. bfs 수행
        visited = new boolean[a][b]; 
        for(int i=0; i<a; i++) {
            for(int j=0; j<b; j++) {
                if(!visited[i][j] && map[i][j] != 'X') {
                    bfs(i, j);
                }
            }
        }
        
        // 3. 정답 형식에 맞게 answerList 변환 
        Collections.sort(answerList); // 오름차순 정렬
        
        if(answerList.size() == 0) {
            answerList.add(-1);
        } 
        int[] answer = new int[answerList.size()];
        
        for(int i=0; i<answer.length; i++) {
            answer[i] = answerList.get(i);
        }   
        
        return answer;
    }
    
    // BFS 알고리즘
    void bfs(int x, int y) { 
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x, y));
        visited[x][y] = true; 
        
        int sum = 0;
        while(!q.isEmpty()) {
            // 1. 큐에서 꺼내옴
            Point p = q.poll();
            
            // 2. 합산
            sum += map[p.x][p.y] - '0';

            // 3. 연결된 곳 순회
            for(int i=0; i<4; i++) {
                int nextX = p.x + dx[i];
                int nextY = p.y + dy[i];
                
                // 4. 갈 수 있는가?
                if(nextY >= 0 && nextY < map[0].length && nextX >= 0 && nextX < map.length 
                && map[nextX][nextY] != 'X' && !visited[nextX][nextY]) {
                    q.add(new Point(nextX, nextY));
                    visited[nextX][nextY] = true;
                }
            }
        }
        answerList.add(sum);
    }
}