백준 | 10026번. 적록색약 - BFS & DFS 풀이

⬛ 백준 10026번. 적록색약 - BFS & DFS 풀이

https://www.acmicpc.net/problem/10026

10026번: 적록색약

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

💚나의 풀이 - DFS 풀이

• DFS로 풀면서 직전 값과 다음 값이 같은 값일 때에만 깊이 탐색하는 식으로 영역을 구분한다.
• DFS를 재귀호출하면서 DFS(x, y)로 호출했다면 호출된 map[x][y] 값과 같은 nx, ny를 지닐 때에만 더 깊이 탐색하는 방식으로 직전 값과의 비교를 진행했다.
• map은 2번 나누어 생성할 건데, 정상인이 보는 map과 적록색약 있는 사람이 보는 map을 따로 두고 하나의 DFS로 각각 탐색한다.
• DFS함수 내부에서 현재 좌표로 접근한 값 map[x][y]값을 tmp 변수에 임시로 담아두고, 계속 더 깊이 탐색할 map[nx][ny] 값이 tmp와 같을 때 더 깊이 탐색하는 식으로 영역 구분을 해야 한다. 그렇게 되면 각각의 색에 대한 영역에 대하여 깊이 탐색하고 복귀하기 때문에 영역 수를 구할 수 있게 된다.

package to_0814_B;

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

//10026번. 적록색약 
public class Main {
	static int N, ans1, ans2;
	static int[][] map;
	static boolean[][] visited;
	
	//상하좌우 
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	
	//DFS
	static void DFS(int x, int y) {
		
		visited[x][y] = true;
		int tmp = map[x][y];//현재값과 같은 값에 대하여 깊이 탐색 
		
		for(int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx <0 || ny <0 || nx >= N || ny >= N) continue;
			
			if(map[nx][ny] == tmp && !visited[nx][ny]) {
				DFS(nx, ny);
			}
		}
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		N = kb.nextInt();
		
		map = new int[N][N];
		visited = new boolean[N][N];
		//R-1 G-2 B-3 으로 입력받기 
		for(int i=0; i<N; i++) {
			String tmp = kb.next();
			for(int j=0; j<N; j++) {
				if(tmp.charAt(j) == 'R') map[i][j] = 1;
				else if(tmp.charAt(j) == 'G') map[i][j] = 2;
				else if(tmp.charAt(j) == 'B') map[i][j] = 3;
			}
		}
		
		ans1 = 0;
		//1) 기본으로 했을 떄 
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(!visited[i][j]) {
					DFS(i, j);
					ans1++;
				}
			}
		}
		
		visited = new boolean[N][N];
		ans2 = 0;
		//2) 적록색약이 봤을 때 
		//map 다시 짜기 
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(map[i][j] == 2) map[i][j] = 1; //같은 영역으로 보게 
			}
		}
		
		//호출 
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(!visited[i][j]) {
					DFS(i, j);
					ans2++;
				}
			}
		}
		
		//정답 세팅 
		System.out.println(ans1 + " " + ans2);
	}
}

---

💚나의 풀이 - BFS 풀이

• 직전 값은 Q에서 뽑는 cur[0], cur[1]로 접근하여 비교하면 된다.
• 너비 탐색을 할 때, 계속해서 Q에서 뽑은 직전값과 4방향으로 탐색하는 nx, ny값이 같을 때에만 쭉 뻗어가다가, 더 이상 갈 곳이 없다면 한 덩어리의 탐색이 끝나는 것이므로, 총 호출 횟수 = 덩어리 횟수가 된다.

package to_0908_6;

import java.util.*;
import java.util.Queue;
import java.util.Scanner;
/*적록색약 - BFS 로 풀이 */
public class Main {
	static int N;
	static int[][] map;//지도
	static boolean[][] visited;
	//4방향 
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	
	//BFS
	static void BFS(int x, int y) {
		Queue<int[]> Q= new LinkedList<>();
		/*이 안에서 인접한 애가 직전값이랑 같을 때만 더 뻗어나아가는데 */
		visited[x][y] = true;
		Q.offer(new int[] {x, y});
		
		while(!Q.isEmpty()) {
			int[] cur = Q.poll();
			for(int k=0; k<4; k++) {
				int nx = cur[0] + dx[k];
				int ny = cur[1] + dy[k];
				if(nx <0 || ny<0 || nx >= N || ny>= N) continue;
				//직전값과 다음 인접 정점이 같은 값이면서 방문 전인 경우에만 계속 인접 탐색 
				if(!visited[nx][ny] && map[nx][ny] == map[cur[0]][cur[1]]) {
					visited[nx][ny] = true;
					Q.offer(new int[] {nx, ny});//다시 담기 
					
				}
			}
		}
		
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		
		N =kb.nextInt();
		
		map = new int[N][N];
		
		
		for(int i=0; i<N; i++) {
			String tmp = kb.next();
			for(int j=0; j<N; j++) {
				if(tmp.charAt(j) == 'R') {
					map[i][j] = 1;
				}else if(tmp.charAt(j)=='G') {
					map[i][j] = 2;
				}else if(tmp.charAt(j)=='B') {
					map[i][j] = 3;
				}
			}
		}
		
		//정상인이 볼 때
		int ans1 = 0;
		visited= new boolean [N][N];
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(!visited[i][j]) {
					BFS(i, j);
					//같은 시작값에 대하여 쭉 인접 탐색 하다가 돌아온 거니까. 그 횟수가 덩어리 개수임 
					ans1++;
				}
			}
		}
		//적녹색약이 볼 때
		
		int ans2 = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(map[i][j] == 2) map[i][j] = 1;//얘도 통합시키고 
			}
		}
		
		visited = new boolean[N][N];
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(!visited[i][j]) {
					BFS(i, j);
					ans2++;
				}
			}
		}

		System.out.println(ans1 + " "+ ans2);
	}
}