카카오 프렌즈 컬러링북(프로그래머스, Java)

문제링크: https://programmers.co.kr/learn/courses/30/lessons/1829

코딩테스트 연습 - 카카오프렌즈 컬러링북 | 프로그래머스

알고리즘 설명:

먼저 그림의 영역을 탐색하는 문제이므로 어떤 탐색방법을 선택할지 고민하였다.

BFS와 DFS 방법중에 BFS가 주변탐색과 속도에서 더 용의하므로 BFS 탐색방법을 사용하였다.

문제에서 그림의 크기가 그렇게 크지않아서 큐 or 스택 둘중 아무거나 사용해도 될 것이라 판단하여 큐를 사용하였다.

• X 위치가 들어갈 큐, Y 위치가 들어갈 큐 두개를 만들고 동시에 두 큐를 다룬다.

• 행렬 크기만큼 2차원 배열을 boolean으로 만들어 탐색 여부를 확인한다.

• BFS 알고리즘

  - 이중 for문으로 위치를 하나하나 전부 확인하고 탐색한 적 없는 위치에 경우 위에서 만든 두 큐에 값을 넣고

  while문으로 두 큐의 값이 빌 때 까지(주변 탐색결과 모든 부분의 영역 값이 다를 때 까지) 탐색을 한다.

• while문이 돌아가기전에 탐색한 적 없는 위치가 처음 위치로 설정된 경우(즉 시작 큐 값이 들어간 경우)가 새로운 영역으로 넘어간 경우이므로 카운트한다.

• 이중 for문이 돌 때 마다 큐에 값이 들어간 숫자가 그 영역의 크기이므로 카운트해준다.

막혔던 지점:

주변을 탐색할 때 동시에 이미 탐색한 부분이 있다는 것을 생각하지 않아서 heap 영역 에러가 떴다.

주변 탐색 조건문에 탐색하지 않은 부분에만 스택에 추가함으로써 문제를 해결하였다.

 

public static int[] solution(int m, int n, int[][] picture) {

	Queue<Integer> queueX = new LinkedList<>();
	Queue<Integer> queueY = new LinkedList<>();
	
	boolean[][] visit = new boolean[m][n];
	int max=0;
	int sectionSize;
	int sectionCount=0;
	int[] answer = new int[2];
	
	for(int i=0;i<m;i++) {
		for(int j=0;j<n;j++) {
			sectionSize = 0;
			if(!visit[i][j] && picture[i][j]!=0) {

				queueX.offer(i);
				queueY.offer(j);
				
				visit[i][j]=true;
				sectionSize++;
				sectionCount++;
				
			}
				while(!queueX.isEmpty() || !queueY.isEmpty()) {
				int x = queueX.poll();
				int y = queueY.poll();
				
				if(x>0 && picture[i][j]==picture[x-1][y] && !visit[x-1][y]) {
					queueX.offer(x-1);
					queueY.offer(y);
					visit[x-1][y]=true;
					sectionSize++;
				}
				if(x<m-1 && picture[i][j]==picture[x+1][y] && !visit[x+1][y]) {
					queueX.offer(x+1);
					queueY.offer(y);
					visit[x+1][y]=true;
					sectionSize++;
				}
				if(y>0 && picture[i][j]==picture[x][y-1] && !visit[x][y-1]) {
					queueX.offer(x);
					queueY.offer(y-1);
					visit[x][y-1]=true;
					sectionSize++;
				}
				if(y<n-1 && picture[i][j]==picture[x][y+1] && !visit[x][y+1]) {
					queueX.offer(x);
					queueY.offer(y+1);
					visit[x][y+1]=true;
					sectionSize++;
				}
			}
			max = Math.max(sectionSize, max);
		}
	}
	answer[0] = sectionCount;
	answer[1] = max;
		
	return answer;
		
}