[프로그래머스] 1829. 카카오프렌즈 컬러링북

문제 링크

[프로그래머스] 1829. 카카오프렌즈 컬러링북

풀이 과정

전역 변수 사용시, solution 메소드 내에서 초기화를 해주어야만 코드가 맞습니다.

BFS 혹은 DFS 탐색으로 2차원 배열을 그룹핑하는 문제입니다.

for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        if (picture[i][j] != 0 && !visit[i][j]) {
            groupCnt++;
            bfs(i, j, m, n, picture);
        }
    }
}

방문이 안된 좌표를 기준으로 bfs 탐색을 실행합니다. 새로운 그룹이 확인되었으니, groupCnt 를 증가시켜 줍니다.

static void bfs(int x, int y, int m, int n, int[][] picture) {
    Queue<int[]> q = new LinkedList<>();
    visit[x][y] = true;
    q.add(new int[]{x, y});
    int cnt = 0;

    while (!q.isEmpty()) {
        int[] now = q.poll();
        cnt++;

        for (int d = 0; d < 4; d++) {
            int nx = now[0] + dx[d], ny = now[1] + dy[d];

            if (nx < 0 || nx > m - 1 || ny < 0 || ny > n - 1 || visit[nx][ny] || picture[nx][ny] != picture[now[0]][now[1]])
                continue;

            visit[nx][ny] = true;
            q.add(new int[]{nx, ny});
        }
    }

    groupArea = Math.max(groupArea, cnt);
}

bfs 메소드 는 상하좌우 인접한 네 곳에 같은 숫자를 갖는 공간들을 모두 찾아 그 개수를 세고, 마킹합니다. 영역 구분이 끝났다면, groupArea 를 큰 넓이로갱신해 줍니다.

코드

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

public class Main {
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
    static boolean[][] visit;
    static int groupCnt;
    static int groupArea;

    public static int[] solution(int m, int n, int[][] picture) {
        visit = new boolean[m][n];
        groupCnt = 0;
        groupArea = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (picture[i][j] != 0 && !visit[i][j]) {
                    groupCnt++;
                    bfs(i, j, m, n, picture);
                }
            }
        }

        return new int[]{groupCnt, groupArea};
    }

    static void bfs(int x, int y, int m, int n, int[][] picture) {
        Queue<int[]> q = new LinkedList<>();
        visit[x][y] = true;
        q.add(new int[]{x, y});
        int cnt = 0;

        while (!q.isEmpty()) {
            int[] now = q.poll();
            cnt++;

            for (int d = 0; d < 4; d++) {
                int nx = now[0] + dx[d], ny = now[1] + dy[d];

                if (nx < 0 || nx > m - 1 || ny < 0 || ny > n - 1 || visit[nx][ny] || picture[nx][ny] != picture[now[0]][now[1]])
                    continue;

                visit[nx][ny] = true;
                q.add(new int[]{nx, ny});
            }
        }

        groupArea = Math.max(groupArea, cnt);
    }

    public static void main(String[] args) {
       solution(6, 4, new int[][]{{1, 1, 1, 0}, {1, 2, 2, 0}, {1, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 3}, {0, 0, 0, 3}});
        // solution(3, 3, new int[][]{{0, 1, 0}, {1, 1, 0}, {0, 0, 0}});
    }
}