[BaekJoon] 백준 10026번 _ 적록 색약 for JAVA _ DFS 알고리즘

 

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

10026번: 적록색약

 

 

 

 

문제

 

 

 

---

 

 

DFS를 이용해서 풀었다.

 

 

위 문제에서 주의할 점은

 

매번 풀던 문제들은 배열이 0, 1 두 가지로 이루어져 1의 뭉탱이 개수를 구하거나... 하는 것이었는데

 

 

얘는 R, G, B 3가지의 뭉탱이 개수를 구하는 것이다...

 

 

그래서 dfs() 함수에 tmp 변수를 넣어 주변 값이 tmp와 같은 값일 때 재귀를 수행하는 방식으로 짜야했다.

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Baek10026 {
	public static int N = 0;
	public static int dx[] = {1, -1, 0, 0};
	public static int dy[] = {0, 0, 1, -1};
	public static String pic[][];
	public static String pic_cb[][]; // color blindness
	public static boolean visited[][];
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		pic = new String[N][N];
		pic_cb = new String[N][N];
		visited = new boolean[N][N];
		
        // 정상 pic[][] 배열에 넣기
		for(int i = 0; i < N; i++) {
			String in = br.readLine();
			for(int j = 0; j < N; j++)
				pic[i][j] = String.valueOf(in.charAt(j));
		}
				
		//색약 pic_cb[][] 배열에 넣기
		for(int i = 0; i < N; i++)
			for(int j = 0; j < N; j++) {
				if(pic[i][j].equals("G"))
					pic_cb[i][j] = "R";
				else {
					pic_cb[i][j] = pic[i][j];
				}
			}
		
		//정상 뭉탱이 개수 count 세기
		int count = 0;
		for(int i = 0; i < N; i++)
			for(int j = 0; j < N; j++) 
				if(!visited[i][j]) {
					area_dfs(i, j, pic);
					count++;
				}
		
		visited = new boolean[N][N]; // visited[] 배열 초기화
		
        //색약 뭉탱이 개수 count_cb 세기
		int count_cb = 0;
		for(int i = 0; i < N; i++)
			for(int j = 0; j < N; j++) 
				if(!visited[i][j]) {
					area_dfs(i, j, pic_cb);
					count_cb++;
				}
			
		System.out.println(count + " " + count_cb);
	}
	
	public static void area_dfs(int x, int y, String pic[][]) {
		visited[x][y] = true;
		String tmp = pic[x][y];
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx <= -1 || nx >= N || ny <= -1 || ny >= N) continue;
			
			if(!visited[nx][ny] && pic[nx][ny].equals(tmp))
				area_dfs(nx, ny, pic);
		}
		
	}

}

 

 

 

위와 같은 코드가 나온다.

 

 

 

성능

 

 

 

 

3가지 이상의 뭉탱이를 DFS로 구하는 방법을 알게 되었다.