[프로그래머스 2017 카카오코드 예선] 카카오프렌즈 컬러링북 -Java

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

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

import java.util.LinkedList;
import java.util.Queue;
class Solution {
	    public int[] solution(int m, int n, int[][] picture) {
	    	int dx[]= {0,0,-1,1};
	    	int dy[]= {-1,1,0,0};
	        int numberOfArea = 0;
	        int maxSizeOfOneArea = 0;
	        int pictures[][] = new int[picture.length][picture[0].length];
	        
	        for(int i=0; i<picture.length; i++) {
	        	for(int j=0; j<picture[0].length; j++) {
	        		pictures[i][j]=picture[i][j];
	        	}
	        }
	        
	        for(int i=0; i<picture.length; i++) {
	        	for(int j=0; j<picture[0].length; j++) {
	        		if(pictures[i][j]!=0) {
	        			numberOfArea++;
	        			maxSizeOfOneArea=Math.max(maxSizeOfOneArea, bfs(i,j,m,n,pictures,dx,dy));
	        		}
	        	}
	        }
	        int[] answer = new int[2];
	        answer[0] = numberOfArea;
	        answer[1] = maxSizeOfOneArea;
	        return answer;
	    }

		private int bfs(int i, int j, int m, int n, int[][] pictures, int[] dx, int[] dy) {
			int num=pictures[i][j]; // 숫자 받고 
			int cnt=1; //카운트 
			
			Queue <int []> queue = new LinkedList<>();
			queue.offer(new int[] {i,j}); //큐에 삽입
			pictures[i][j]=0; //방문체크
			
			while(!queue.isEmpty()) {
				int point[]=queue.poll();
				
				for(int d=0; d<4; d++) {
					int nx=point[0]+dx[d];
					int ny=point[1]+dy[d];
					
					if(nx<0 || ny<0 || nx>=m || ny>=n || pictures[nx][ny]==0 || pictures[nx][ny]!=num) continue; 
					cnt++;
					queue.offer(new int[] {nx,ny});
					pictures[nx][ny]=0;
				}
				
			}
			return cnt;
		}
	}

소요시간 : 30분

 

문제 설명에 오류가 있습니다.

분명 문제에는 picture배열을 건들면 안된다는 말이 없었는데..

초기에 풀었을 때는 picture배열의 값을 건들면서 값을 뽑았더니 계속 답이 틀렸습니다.

도저히 모르겠어서 질문하기를 보았는데 picture값이 바뀌면 틀리는 오류가 있다고 배열을 하나 복사해서 사용하라고 해서 그렇게 해봤더니 바로 정답이 나왔습니다!

 

로직을 살펴보면

1. pictures배열이 0이 아니면 bfs를 돌려준다.

2. 영역의 수를 하나 늘려주고, 최대영역의 수와 bfs에서 나온 영역의 수를 비교해 큰 수를 최대영역의 수에 넣어준다.

 

방문체크하는 방식은 pictures배열의 값을 0으로 바꿔주었습니다!