BFS( 너비 우선 탐색 )

프로그래머스 2017 카카오코드 예선 Level 2 문제 카카오프렌즈 컬러링북을 Java를 이용하여 풀어보았다.
BFS를 이용해서 쉽게 풀 수 있는 문제였다.

문제링크 첨부한다.
https://programmers.co.kr/learn/courses/30/lessons/1829

---

BFS로 같은 특징 가진 영역의 size 구하기

백준에서도 쉽게 찾아볼 수 있는 전형적인 BFS 문제였다. 위의 그림대로 같은 숫자가 끊기지 않고 연결된 영역들의 개수와 각 영역의 넓이를 구해서 그 중 가장 큰 녀석을 return 하면 된다.

visited[][] 배열을 활용해서 주어진 모든 칸들을 다 돌며 0이 아니며 이미 방문되지 않은 곳들에 한해서 getAreaSize() 메소드를 사용하면 된다. 넓이를 구해주는 이 메소드의 코드는 다음과 같다.

Integer getAreaSize(int row, int col, int m, int n, int[][] picture) {
        int size = 0;
        int curNum = picture[row][col]; // 다음 방문할 곳의 숫자가 시작점과 동일한지 판별해주기 위한 변수
        q.add(new int[]{row, col});
        visited[row][col] = true;
        size++;

        while (!q.isEmpty()) {
            int[] curPos = q.poll();
            int curRow = curPos[0];
            int curCol = curPos[1];

            for (int dir = 0; dir < 4; dir++) {
                int newRow = curRow + move[dir][0];
                int newCol = curCol + move[dir][1];
                if (!isInRange(newRow, newCol, m, n) || visited[newRow][newCol]) continue; // 범위 밖 OR 이미 방문이면 넘기자
                if (picture[newRow][newCol] != curNum) continue; // 다른 색깔이면 넘기자

                q.add(new int[]{newRow, newCol}); // 모든 조건을 만족하면 큐에 추가해주고
                visited[newRow][newCol] = true; // 방문 처리해주고
                size++; // 넓이값 1 늘려준다
            }
        }

        return size;
    }

BFS 문제를 몇 번 풀어봤다면 매우 보편적인 코드라는 것을 확인할 수 있다.

---

이중 for문으로 탐색하며 영역의 개수와 최대 넓이 갱신하기

하나의 영역 size 를 구하는 것은 위에서 살펴봤다. 그렇다면 총 몇 개의 영역이 나왔으며 그 중 가장 넓은 size는 몇인지 어떻게 얻을 수 있을지 살펴보자.

영역 개수
getAreaSize() 메소드를 한 번 호출할 때마다 새로운 영역이 생기는 것이기 때문에 이 메소드를 호출한 뒤에 영역의 개수를 하나 추가해주면 영역 개수는 해결된다.

최대 넓이
그리고 getAreaSize() 메소드를 통해 얻어낸 해당 영역의 넓이를 기존에 선언해놨던 maxAreaSize 변수와 비교해서 더 크면 새롭게 값을 넣어주고 아니면 그대로 놔두면 된다.

이를 코드로 확인해보면 다음과 같다.

for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (picture[r][c] == 0 || visited[r][c]) continue; // 0이면 OR 방문했으면 패스
                int curSize = getAreaSize(r, c, m, n, picture);
                maxSizeOfOneArea = (maxSizeOfOneArea < curSize ? curSize : maxSizeOfOneArea); // 넓이 최댓값 갱신
                numberOfArea++; // 영역 개수 추가
            }
        }

---

다음은 위 코드를 모두 합쳐 제출한 내 코드다.

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class ColoringBook {
    static boolean[][] visited;
    static int[][] move = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static Queue<int[]> q = new LinkedList<>();

    static int[] solution(int m, int n, int[][] picture) {
        int[] answer = new int[2];
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        visited = new boolean[m][n];

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (picture[r][c] == 0 || visited[r][c]) continue; // 0이면 OR 방문했으면 패스
                int curSize = getAreaSize(r, c, m, n, picture);
                maxSizeOfOneArea = (maxSizeOfOneArea < curSize ? curSize : maxSizeOfOneArea);
                numberOfArea++;
            }
        }

        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }

    static Integer getAreaSize(int row, int col, int m, int n, int[][] picture) {
        int size = 0;
        int curNum = picture[row][col];
        q.add(new int[]{row, col});
        visited[row][col] = true;
        size++;

        while (!q.isEmpty()) {
            int[] curPos = q.poll();
            int curRow = curPos[0];
            int curCol = curPos[1];

            for (int dir = 0; dir < 4; dir++) {
                int newRow = curRow + move[dir][0];
                int newCol = curCol + move[dir][1];
                if (!isInRange(newRow, newCol, m, n) || visited[newRow][newCol]) continue; // 범위 밖 OR 이미 방문이면 넘기자
                if (picture[newRow][newCol] != curNum) continue; // 다른 색깔이면 넘기자

                q.add(new int[]{newRow, newCol});
                visited[newRow][newCol] = true;
                size++;
            }
        }

        return size;
    }

    static Boolean isInRange(int row, int col, int m, int n) {
        if (row < 0 || row >= m || col < 0 || col >= n) return false;
        return true;
    }

    public static void main(String args[]) throws IOException {
        BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        int m = 6;
        int n = 4;
        int[][] picture = {{1, 1, 1, 0}, {1, 1, 1, 0}, {0, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 1}};
        int[] answer = solution(m, n, picture);
        bfw.write(answer[0] + " " + answer[1]);
        bfw.close();
    }
}

BFS를 평범하게 이용해서 해결할 수 있는 문제였다.