Algorithm/프로그래머스

프로그래머스 :: 카카오 프렌즈 컬러링북

jihyun03 2020. 8. 28. 18:30

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

 

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

6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5]

programmers.co.kr

🎈 문제 풀이

 

- DFS를 활용하면 되는 문제였다.

- 다른 문제와 다르게 했던 점은 다음 인접 정점을 탐색하기 위해서는 계속 "같은 색상의 값"이어야 했기

때문에 dfs 파라미터로 처음 dfs 탐색을 시작할 때 가지고 있던 색상 값을 받아서 현재 탐색 중인 정점과 비교했다. 

- 한 번 dfs를 돌 때 마다 numberOfArea를 1씩 추가하고

- dfs 호출을 통해서 반환되어져 오는 "영역의 넓이"를 비교하여 maxSizeOfOneArea를 구했다.

 

🎈 소스 코드

 

import java.util.Arrays;

public class 컬러링북 {
	static int[][] moves = {{-1,0}, {+1,0}, {0,+1}, {0,-1}};
	static boolean[][] visited;

	public static void main(String[] args) {
		int m = 6;
		int n = 4;
		int[][] picture = {{1, 1, 1, 0}, {1, 2, 2, 0}, {1, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 3}, {0, 0, 0, 3}};

		System.out.println(Arrays.toString(solution(m,n,picture)));
	}

	static int[] solution(int m, int n, int[][] picture) {
		int[] answer = new int[2];
		int numberOfArea = 0;
		int maxSizeOfOneArea = 0;
		visited = new boolean[m][n];

		for(int i=0; i<m; i++) {
			for(int j=0; j<n; j++) {
				if(!visited[i][j] && picture[i][j] != 0) {
					numberOfArea++;
					int sizeOfOneArea = dfs(i,j,picture, picture[i][j]);
					if(sizeOfOneArea > maxSizeOfOneArea) {
						maxSizeOfOneArea = sizeOfOneArea;
					}
				}
			}
		}

		answer[0] = numberOfArea;
		answer[1] = maxSizeOfOneArea;
		return answer;
	}

	static int dfs(int m, int n, int[][] picture, int value) { // value = 컬러
		// 종료조건
		if(m < 0 || m >= picture.length || n < 0 || n >= picture[0].length) return 0;
		if(picture[m][n] == 0) return 0;
		if(visited[m][n]) return 0;
		if(picture[m][n] != value) return 0;

		int cnt = 1;
		visited[m][n] = true; // 방문
		for(int[] move : moves) { // 인접정점 돌기
			int nx = m+move[0];
			int ny = n+move[1];

			cnt += dfs(nx, ny, picture, value);
		}
		return cnt;
	}
}