[JAVA] 프로그래머스 - 카카오프렌즈 컬러링북 (DFS , BFS)

문제 내용

https://programmers.co.kr/learn/courses/30/lessons/1829?language=java

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

 

그림의 영역을 난이도(숫자)에 따라 나누고 나눠진 영역의 개수와 가장큰 영역안에 땅의 개수를 세는 문제다.

처음에 문제를 읽고 문제 이해가 잘되지 않았는데

 

난이도가 0으로 표시된 곳은 제외해야한다는 점이다.

 

그외에는 백준의 DFS , BFS 문제로 풀었던 문제들과 유사하다.

 

---

문제 접근 방법

먼저 DFS 방법으로 접근해서 풀었고 후에 BFS로도 풀어봤다.

 

두 방법 모두

 

1. 방문 배열을 필요로 한다.

2. 들어온 인덱스 기준 상하좌우를 체크해줄 배열이 필요하다.

3. 방문하지 않은 인덱스 중 picture의 요소값이 0이 아닌 모든 곳을 BFS , DFS로 돌아야 한다.

4. 한번 돌면 영역의 개수가 1증가 한다.

5. 한 영역안에 땅의 개수는 BFS, DFS 안에서 세어준다.

 

이중 for문을 통해 3~5번을 반복해 주면 풀리는 문제이다.

 

풀이를 보자. 풀이는 

 

solution 함수

dfs 함수

bfs 함수

전체 코드

 

로 나눠 놨다.

---

풀이

solution 함수

public static int[] solution(int m, int n, int[][] picture) {
		int numberOfArea = 0;
		int maxSizeOfOneArea = 0;
		check = new boolean[m][n];
		
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (picture[i][j] != 0 && !check[i][j]) {
					numberOfArea++;
					//dfs(i, j, picture);
					bfs(i,j,picture);
					maxSizeOfOneArea = Math.max(maxSizeOfOneArea, sizeCnt);
					sizeCnt=1;
				}
			}
		}

		int[] answer = new int[2];
		answer[0] = numberOfArea;
		answer[1] = maxSizeOfOneArea;
		
		return answer;
	}

 

---

DFS 함수

public static void dfs(int x, int y,int[][] picture) {
        check[x][y] = true;
        
        for(int i = 0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx>=0 && ny>=0 && nx<picture.length && ny<picture[0].length) {
            	if(picture[x][y]==picture[nx][ny] && !check[nx][ny]) {
            		sizeCnt++;
            		dfs(nx, ny, picture);
            	}
            }
        }
}

 

BFS 함수

public static void bfs(int x, int y, int[][] picture) {
		Queue<pointKakaoBook> q = new LinkedList<pointKakaoBook>();
		q.add(new pointKakaoBook(x, y));
		check[x][y] = true;
		
		while(!q.isEmpty()) {
			pointKakaoBook point = q.poll();
			
			for(int i=0; i<4; i++) {
				int nx = point.pointX + dx[i];
				int ny = point.pointY + dy[i];
				
				if(nx>=0 && ny>=0 && nx<picture.length && ny<picture[0].length) {
					if(picture[point.pointX][point.pointY]==picture[nx][ny] && !check[nx][ny]) {
						sizeCnt++;
						check[nx][ny]=true;
						q.add(new pointKakaoBook(nx, ny));
					}//if
				}//if
			}//for
		}//while
	}//bfs
}//class

class pointKakaoBook{
	int pointX;
	int pointY;
	
	public pointKakaoBook(int x, int y) {
		this.pointX = x;
		this.pointY = y;
	}
}

 

---

전체코드

import java.util.LinkedList;
import java.util.Queue;

public class kakaoFriendsBook {
	static boolean[][] check;
	static int sizeCnt=1;
	static int[] dx = {0,0,-1,1};
	static int[] dy = {-1,1,0,0};
	
	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 } };
		
		solution(m, n, picture);
	}

	public static int[] solution(int m, int n, int[][] picture) {
		int numberOfArea = 0;
		int maxSizeOfOneArea = 0;
		check = new boolean[m][n];
		
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (picture[i][j] != 0 && !check[i][j]) {
					numberOfArea++;
					//dfs(i, j, picture);
					bfs(i,j,picture);
					maxSizeOfOneArea = Math.max(maxSizeOfOneArea, sizeCnt);
					sizeCnt=1;
				}
			}
		}

		int[] answer = new int[2];
		answer[0] = numberOfArea;
		answer[1] = maxSizeOfOneArea;
		
		return answer;
	}
	
	public static void dfs(int x, int y,int[][] picture) {
        check[x][y] = true;
        
        for(int i = 0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx>=0 && ny>=0 && nx<picture.length && ny<picture[0].length) {
            	if(picture[x][y]==picture[nx][ny] && !check[nx][ny]) {
            		sizeCnt++;
            		dfs(nx, ny, picture);
            	}
            }
        }
	}
	
	public static void bfs(int x, int y, int[][] picture) {
		Queue<pointKakaoBook> q = new LinkedList<pointKakaoBook>();
		q.add(new pointKakaoBook(x, y));
		check[x][y] = true;
		
		while(!q.isEmpty()) {
			pointKakaoBook point = q.poll();
			
			for(int i=0; i<4; i++) {
				int nx = point.pointX + dx[i];
				int ny = point.pointY + dy[i];
				
				if(nx>=0 && ny>=0 && nx<picture.length && ny<picture[0].length) {
					if(picture[point.pointX][point.pointY]==picture[nx][ny] && !check[nx][ny]) {
						sizeCnt++;
						check[nx][ny]=true;
						q.add(new pointKakaoBook(nx, ny));
					}
				}
			}
		}
	}
}

class pointKakaoBook{
	int pointX;
	int pointY;
	
	public pointKakaoBook(int x, int y) {
		this.pointX = x;
		this.pointY = y;
	}
}

 

---

마치며

보다시피 DFS와 BFS 방법 두가지로 풀수 있다. 그리고 답을 제출해보니 DFS로 풀었을때가 BFS로 풀었을때 보다 효율이 더 좋게 나오는걸 볼수 있다. 아무래도 BFS는 객체를 새로 만들면서 메모리를 사용하기 때문 아닐까 생각해본다.