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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/1829
레벨 : Level 2
분류 : 2017 카카오코드 예선

코딩테스트 연습 - 카카오프렌즈 컬러링북

이 문제는 가장 큰 컬러의 면적과 컬러의 종류를 구하는 문제이다.

문제를 보고 모든 위치를 전부 탐색하는 문제라는 것을 파악해 bfs로 풀이를 시도하였다.

하지만 몇개월만에 다시 시작하는 코딩 테스트라 bfs, dfs를 다 까먹었다...

앞으로 코딩테스트는 한번 할 때 쭉 해야 할 거 같다.

 

구체적인 설명은 하지 않겠다 bfs를 알고 있다면 쉽게 풀 수 있는 문제이다.

 

아래와 같이 풀이를 공유합니다.

import java.util.*;

class Solution {
    public static class Node {
        int x, y;
        Node(int x, int  y) {
            this.x = x;
            this.y = y;
        }
    }
    
    private static int cnt, x, y;
    private static boolean[][] visit;
    private static int[] dx = {0, -1, 0, 1};
    private static int[] dy = {-1, 0, 1, 0};    
    private static Queue<Node> que = new LinkedList<>();
    
    public int[] solution(int m, int n, int[][] picture) {

        visit = new boolean[m][n];
        x = m;
        y = n;
        int max = Integer.MIN_VALUE;
        int type = 0;
        
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(visit[i][j] || picture[i][j] == 0) continue;
                
                cnt = 1;
                type++;
                bfs(picture, i, j);                
                max = Math.max(max, cnt);
            }
        }
        
        int[] answer = new int[2];
        
        answer[0] = type;
        answer[1] = max;
        
        return answer;
    }
    
    public void bfs(int[][] pic, int i, int j) {
        visit[i][j] = true;
        que.add(new Node(i, j));

        int source = pic[i][j];

        while(!que.isEmpty()) {
            Node node = que.poll();

            for(int k = 0; k < 4; k++) {
                int xx = node.x + dx[k], yy = node.y + dy[k];
                if(xx < x && yy < y && xx >= 0 && yy >= 0) {
                    int target = pic[xx][yy];
                    if(!visit[xx][yy] && source == target) {
                        visit[xx][yy] = true;
                        cnt++;
                        que.add(new Node(xx, yy));
                    }
                }
            }
        }
    }
}