[Programmers] 카카오프렌즈 컬러링북

문제

 

2017 카카오코드 예선 > 카카오프렌즈 컬러링북

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

 

 

아이디어

 

이번 문제의 아이디어는 BFS입니다.

 

풀이 방법은 다음과 같습니다.

 

1. 배열을 탐색하며 원소 값이 0이 아니고 방문한 적이 없는 인덱스 찾기

2. 찾은 인덱스를 기준으로 원소 값이 같은 인접한 인덱스를 BFS로 모두 방문

3. 배열을 모두 탐색할 때 까지 1~2를 반복

 

 

구현 코드 (Java)

 

import java.util.*;

class Solution {
    public int[] solution(int m, int n, int[][] picture) {
    	int dirj[] = {1, 0, -1, 0}; // j방향
    	int diri[] = {0, 1, 0, -1}; // i방향
    	boolean visited[][] = new boolean[m][n]; // 방문여부 체크
    	int region = 0; // 영역 개수
    	int max = Integer.MIN_VALUE; // 가장 큰 영역의 넓이
    	
    	for(int i=0; i<m; i++) {
    		for(int j=0; j<n; j++) {
    			if(picture[i][j] != 0 && !visited[i][j]) { // 원소값이 0이 아니고 방문한적이 없는 경우
    				region++; // 영역 개수 증가
    				
    				Queue<Node> queue = new LinkedList<Node>();
    				int count = 0; // 영역 넓이
    				int target = picture[i][j];
    				queue.add(new Node(i, j));
    				
    				while(!queue.isEmpty()) { // BFS를 이용한 인접 인덱스들 모두 탐색
    					Node node = queue.poll();
    					
    					if(visited[node.i][node.j] || picture[node.i][node.j] != target) {
    						continue;
    					}
    					
    					visited[node.i][node.j] = true; // 방문 체크
    					count++; // 영역 넓이 증가
    					
    					for(int a=0; a<4; a++) {
    						int nexti = node.i + diri[a];
    						int nextj = node.j + dirj[a];
    						
    						if(nexti >= m || nexti < 0 || nextj >= n || nextj < 0 || visited[nexti][nextj] || picture[nexti][nextj] != target) {
    							continue;
    						}
    						
    						queue.add(new Node(nexti, nextj));
    					}
    				}
    				
    				max = Math.max(max, count); // 가장 큰 영역의 넓이 구하기
    			}
    		}
    	}
    	
    	int res[] = new int[]{region, max};
    	
    	return res;
    }
    
    private static class Node {
    	int i, j;
    	public Node (int i, int j) {
    		this.i = i;
    		this.j = j;
    	}
    }
}

 

 

읽어주셔서 감사합니다.