20180806 2017 카카오코드 예선 [카카오 프렌즈 컬러링 북]

1. 카카오 프렌즈 컬러링북 

https://programmers.co.kr/learn/courses/30/lessons/1829

(1) BFS 또는 DFS 로 풀 것인지 결정

(2) 두 가지를 고려 ( 영역의 개수, 영역의 최대 너비 )

(3) 탐색의 진입점 고려

import java.io.*;
import java.util.*;
 
public class Main {
 
    static OutputStreamWriter osw;
    static BufferedWriter bw;
 
    public static void main(String[] args) throws IOException {
        bw = new BufferedWriter(osw);
 
        int m = 6;
        int n = 4;
        int[][]picture = 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}};
        
        int[]result = solution(m, n, picture);
        
        bw.write(result[0] + " " + result[1] + "\n");
        bw.flush();
        bw.close();
    }
 
    public static int[] solution(int m, int n, int[][] picture) {
        
        // 방문배열
        int visited[][] = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                visited[i][j] = (picture[i][j] == 0)? -1 : 0;
            }
        }
        
        int[]move1 = {1, -1, 0, 0};
        int[]move2 = {0, 0, 1, -1};
        int areaCount = 0;
        int maxArea = 0;
        
        for(int i = 0; i < picture.length; i++){
            for(int j = 0; j < picture[i].length; j++){
                
                // 색칠이 된 상태 && 미방문
                if(picture[i][j] != 0 && visited[i][j] == 0){
                    areaCount += 1; 
                    int areaSize = 0;
                    visited[i][j] = picture[i][j];
                    
                    Queue<Point> q = new LinkedList<Point>();
                    q.add(new Point(i, j));
                    
                    // BFS
                    while(!q.isEmpty()){
                        Point p = q.poll();
                        areaSize += 1;
                        
                        for(int mv = 0; mv < 4; mv++){
                            int my = p.y + move1[mv];
                            int mx = p.x + move2[mv];
                            
                            if(my < 0 || my >= m || mx < 0 || mx >= n)
                                continue;
                            
                            if(visited[my][mx] != 0 || picture[my][mx] == 0)
                                continue;
                            
                            // 값에 따라 구역을 나눔.
                            if(picture[my][mx] != visited[p.y][p.x])
                                continue;
                            
                            q.add(new Point(my, mx));
                            visited[my][mx] = visited[p.y][p.x];
                        }
                    }
                    
                    maxArea = Math.max(maxArea, areaSize);
                }// 색칠 방문
            } // for
        } // for
        
        
        // console.
//        for(int i = 0; i < m; i++){
//            for(int j = 0; j < n; j++){
//                System.out.print(visited[i][j] + " ");
//            }
//            System.out.println();
//        }
        
        return new int[]{areaCount, maxArea};
    }
}
 
class Point{
    int y;
    int x;
    
    public Point(int y, int x){
        this.y = y;
        this.x = x;
    }
}