[알고리즘] BFS 풀이 순서와 백준 그림 문제 Java 풀이

 

BFS(Breadth First Search, BFS)는 주로 최단거리나 최단 시간등 목표 상태에 도달할 수 있는 가장 빠른 경로를 탐색하는데 활용된다. 왜냐하면 BFS는 인접한 노드들에 대해서 모두 방문을 하기 때문에 방문한 시점이 가장 최단 경로의 시점이기 때문이다.

 

BFS 문제 풀이 순서

1. input 단계에서 방문 체크 isVisited 배열과 , 방문 경로 map의 배열, 방문체크 dy, dx 배열을 만든다

2. for문을 돌아서 map에서 방문 위치를 찾아낸다.

3. 찾은 위치를 Queue에 넣고, 방문 체크를 한다.

4. Queue에서 뽑은 map위치에서 방문 경로를 뒤진다.

5. 방문 경로에서 조건에 맞으면 Queue에 넣는다. Queue가 다 비워질때 까지 계속 방문 경로를 뒤지고 조건에 맞으면 Queue에 넣는다.

 

※ 참고로 방문 경로의 조건은 문제에 따라 다를수 있지만 일반적으로 방문 경로가 map 범위 안에 들어가는지, 방문하지 않았던 곳인지, map 범위안에 들어가도 Queue에 들어가도 되는 위치인지가 있다.

 

백준 그림 문제 java 풀이

https://www.acmicpc.net/problem/1926

 

문제 풀이에서 요점은 전체 그림의 수를 for문을 돌아서 map에서 값이 1인것을 찾았을때 전체 그림의 수 count를 1 늘리는 것이고 bfs를 돌면서 Queue에 담아질때마다 그림의 크기를 구해서 반환값으로 그림의 크기를 가져와서 크기를 비교하는 것이다.

 

시간 복잡도는 인접행렬을 사용했기 때문에 M, N 맥시멈 사이즈 500 * 500 해서 25만 이다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

//https://www.acmicpc.net/problem/1926
public class 그림 {
    /**
     * 1. 아이디어
     *   - 2중 for => 값 1 && 방문 => BFS
     *   - BFS 돌면서 그림 개수 +1, 최대값을 갱신
     *
     *  2. 시간복잡도
     *    - BFS 인접행렬
     *    - M * N = 500 * 500 = 25만
     *
     * 3. 자료구조
     *   - 그래프 전체 지도 : int[][]
     *   - 방문 여부 : boolean[][]
     *   - 전체 그림 개수 : int
     *   - 최대 그림 크기 : int
     *   - Queue(BFS)
     *   - 동서남북 x좌표 : int[]
     *   - 동서남북 y좌표 : int[]
     */

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    static int mapYsize, mapXsize;
    static int[][] map = null;
    static boolean[][] isVisited = null;

    //0 1 오른쪽, 1 0 위쪽, 0 -1 왼쪽, -1 0 밑에쪽
    private final static int[] dy = new int[]{0, 1, 0, -1};
    private final static int[] dx = new int[]{1, 0, -1, 0};

    static int paintingCount = 0; //전체 그림 개수
    static int maxPaintingSize = 0; //제일큰 그림 크기

    private static void input() throws IOException {
        st = new StringTokenizer(br.readLine());

        //도화지 세로크기 y, 가로크기 x
        mapYsize = Integer.parseInt(st.nextToken());
        mapXsize = Integer.parseInt(st.nextToken());

        map = new int[mapYsize][mapXsize];
        isVisited = new boolean[mapYsize][mapXsize];

        for (int i = 0; i < mapYsize; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < mapXsize; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }

    public static void main(String[] args) throws IOException {
        input();

        solve();

        print();
    }

    private static void print() {
        StringBuilder sb = new StringBuilder();

        sb.append(paintingCount).append("\n");
        sb.append(maxPaintingSize).append("\n");

        System.out.println(sb.toString());
    }

    private static void solve() {
        //2중 for => 값 1 && 방문 => BFS
        for (int i = 0; i < mapYsize; i++) {
            for (int j = 0; j < mapXsize; j++) {
                if(map[i][j] == 1 && !isVisited[i][j]) {
                    /**
                     * 방문체크 true
                     * 전체 그림 갯수를 + 1
                     * BFS > 그림 크기를 구해주고
                     * 최대값 갱신
                     */
                    isVisited[i][j] = true;
                    paintingCount++;
                    maxPaintingSize = Math.max(maxPaintingSize, bfs(i, j));
                }
            }
        }
    }

    private static int bfs(int y, int x) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{y, x});
        int mapSize = 1;

        while(!queue.isEmpty()) {
            int[] que = queue.poll();
            int qy = que[0];
            int qx = que[1];

            for (int i = 0; i < dx.length; i++) {
                int ny = qy + dy[i];
                int nx = qx + dx[i];

                /**
                 * map 사이즈 체크
                 * 방문한곳 1인지 체크
                 * 방문여부 체크
                 */
                if (0 <= ny && ny < mapYsize && 0 <= nx && nx < mapXsize && map[ny][nx] == 1 && !isVisited[ny][nx]) {
                    isVisited[ny][nx] = true;
                    queue.add(new int[]{ny, nx});
                    mapSize++;
                }
            }

        }

        return mapSize;
    }
}

 

문제 풀이 방법대로 input 단계 에서 방문 체크 isVisited 배열과 , 방문 경로 map의 배열을 만들었고, static으로 dy, dx 배열도 만들었다. 

그리고 solve() 함수에서 for문을 돌아 map에서 1인것 찾고, 그림수 count + 1, 방문 체크를 한 후 bfs() 함수를 실행시킨다.

bfs() 함수에서는 Queue를 만들고 map에서 1의 위치를 넣은 다음에 Queue를 돌린다.

 

Queue에서 뽑은 map의 위치에서 dy, dx 방문 체크를 하여 조건에 맞으면 Queue에 넣고 그림 크기 + 1한다.

조건은 map, 사이즈 체크, 방문한곳이 1인지 체크, 방문여부 체크이다. 일반적인 방문 조건 체크이다.

 

Queue를 다 돌았으면 그림 크기를 return 하여 Math.max() 함수를 이용하여 그림 크기를 비교한다.

 

 

참고 : https://www.youtube.com/watch?v=ansd5B27uJM&t=932