[ Lv 2 ] [ BFS ] 카카오프렌즈 컬러링북

풀이 과정

---

1. 파이썬으로는 풀이할 수가 없어서 Java로 풀이함.
2. 전체적인 흐름은 BFS로 구성
   • 전체 배열을 2중 for문으로 검사하면서, 0이 아닌 수가 발견되면 그 자리에서 bfs 진행
   • bfs의 경우, 현재 자리의 값을 0으로 만들고 현재 자리의 값과 같은 값이 인접 위치에 있다면, 해당 위치를 0으로 만들고 큐에 넣는 방식으로 진행.
   • 0으로 만든 배열 요소의 수를 따로 리턴해 준다.
3. 전체 BFS 진행 횟수가 영역의 개수, BFS 진행하면서 0으로 만든 배열 요소의 수의 최댓값이 가장 큰 영역의 넓이이다.

• 문제 오류인것 같긴 한데.. 입력받은 picture을 직접 수정하면 틀렸다고 나오고, picture를 따로 복사한 다음 수정해야 맞았다고 나온다..

---

소스 코드

---

import java.util.Queue;
import java.util.LinkedList;

class Position {
    int x;
    int y;

    public Position(int a, int b) {
        this.x = a;
        this.y = b;
    }
}

class Solution {
    public int bfs(int curX, int curY, int[][] picture) {
        Queue<Position> queue = new LinkedList<Position>();
        int areaValue = picture[curX][curY];
        queue.add(new Position(curX, curY));
        picture[curX][curY] = 0;
        int count = 1;
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        while (!queue.isEmpty()) {
            Position pos = queue.poll();
            for (int i = 0; i<4; i++) {
                int nx = pos.x + dx[i];
                int ny = pos.y + dy[i];
                if (0 <= nx && nx < picture.length && 
                    0 <= ny && ny < picture[0].length && 
                    picture[nx][ny] == areaValue) {
                    queue.add(new Position(nx, ny));
                    count++;
                    picture[nx][ny] = 0;
                }
            }
        }

        return count;
    }

    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;

        int[][] copypicture = new int[picture.length][picture[0].length];

        for (int i = 0; i<m; i++)
            for (int j=0; j<n; j++)
                copypicture[i][j] = picture[i][j];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (copypicture[i][j] != 0) {
                    maxSizeOfOneArea = Math.max(maxSizeOfOneArea, bfs(i, j, copypicture));
                    numberOfArea++;
                }
            }
        }

        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
}

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges