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

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

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

 

특이하게도 이 문제는 테스트케이스가 한 개였다. 그마저도 효율성 쪽을 체크하는 부분은 없었고, 정확성만 체크했다. 아마 최대 제한크기가 각각 100으로 제한되어서인 것 같다. 문제 자체는 BFS를 실행하는 기본적인 문제였다.

---

문제설명

---

입출력 및 예제

---

코드

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

class Solution
{
    // 상하좌우 4방향 체크
    static int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    
    // BFS 실행
    public static int makeChk(int[][] picture, boolean[][] visit, int[] start, int m, int n)
    {
        int cnt = 0;
        Queue<int[]> q = new LinkedList<int[]>();
        q.add(start);
        visit[start[0]][start[1]] = true;
        
        while(!q.isEmpty())
        {
            cnt++;
            int[] temp = q.poll();
            int y = temp[0];
            int x = temp[1];
            int value = picture[y][x];
            
            for(int i=0; i<4; i++)
            {
                y += dir[i][0];
                x += dir[i][1];
                
                // BFS 실행 시작 좌표의 값과 같은 값을 가지는 좌표만 큐에 넣기
                if(y>=0 && y<m && x>=0 && x<n && value==picture[y][x] && !visit[y][x])
                {
                    q.add(new int[]{y, x});
                    visit[y][x] = true;
                }
                
                y -= dir[i][0];
                x -= dir[i][1];
            }
        }
        
        // 이 영역의 개수를 리턴
        return cnt;
    }
    public int[] solution(int m, int n, int[][] picture)
    {
        int cnt = 0;
        int max = Integer.MIN_VALUE;
        boolean[][] visit = new boolean[m][n];
        
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(!visit[i][j] && picture[i][j]!=0)
                {
                    // 영역별 최대값 구하기
                    max = Math.max(max, makeChk(picture, visit, new int[]{i, j}, m, n));
                    cnt++;
                }
            }
        }
        
        return new int[]{cnt, max};
    }
}