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

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/1829?language=java

풀이

DFS를 이용하면 되는 문제였다. BFS 대신 DFS를 사용하는 이유는 재귀 호출을 통해 면적 합계를 구하기 용이하기 때문이다. 기존 좌표의 상하좌우에 해당하는 새로운 좌표를 구한 뒤, visit이 가능한 조건(배열 범위, 이미 방문했는지 여부, 같은 색깔)을 만족하는지를 확인하여 dfs() 메서드를 재귀 호출하면 된다. 그러면 한 영역에 속하는 점 하나를 골라 dfs()를 호출하면 해당 영역의 모든 점들을 visit하여 총 면적을 구할 수 있다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    int[][] picture;
    List<Integer> areas;
    boolean[][] visited;
    int[] rowDir = {1, 0, -1, 0};
    int[] colDir = {0, 1, 0, -1};

    public int[] solution(int m, int n, int[][] picture) {
        this.picture = picture;
        areas = new ArrayList<>();
        visited = new boolean[m][n];

        for(int row = 0; row < m; row++) {
            for(int col = 0; col < n; col++) {
                if(picture[row][col] == 0) continue;
                int added = dfs(row, col);
                if(added != 0) areas.add(added);
            }
        }

        int[] result = new int[2];
        result[0] = areas.size(); // 영역 개수
        result[1] = Collections.max(areas); // 가장 넓은 영역 넓이

        return result;
    }

    public int dfs(int row, int col) {
        visited[row][col] = true;

        int sum = 1; // 좌표 하나 방문했으므로 면적 1부터 시작

        for(int i = 0; i < 4; i++) {
            // 기존 좌표의 상하좌우에 해당하는 좌표 구하기
            int candidateRow = row + rowDir[i];
            int candidateCol = col + colDir[i];

            // visit이 가능한 조건 판별
            if(!inRange(candidateRow, picture.length)) continue;
            if(!inRange(candidateCol, picture[0].length)) continue;
            if(visited[candidateRow][candidateCol]) continue;
            if(picture[row][col] != picture[candidateRow][candidateCol]) continue;

            sum += dfs(row + rowDir[i], col + colDir[i]);
        }

        return sum;
    }

    public boolean inRange(int val, int bound) {
        return val >= 0 && val < bound;
    }
}