적록색약 [백준 10026][JAVA][골드 5][DFS,BFS]

 

[광고 누르면 오늘의 행운 상승!!]

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

10026번: 적록색약

굉장히 굉장히 쉬운 DFS or BFS 문제

1. 정상일 때 ) DFS를 돌면서 같은 색깔이면 visit배열을 갱신시면서 normal을 증가시킨다.

2. map을 돌면서 G를 B로 (혹은 B를 G로) 변경시킨다

3. 비정상일 때)  1번을 재실행하면서 abnormal을 증가시킨다

4. 출력한다.

package Study5;

import java.io.*;
import java.util.*;

public class 적록색약 {
	
	static int[] dx = {-1,0,1,0};
	static int[] dy = {0,1,0,-1};
	static char[][] map;
	static boolean[][] visit;
	static int N,normal,abnormal;
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		map = new char[N][N];
		visit = new boolean[N][N];
		
		for (int i = 0; i < N; i++) {
			char ch[] = br.readLine().toCharArray();
			for (int j = 0; j < N; j++) {
				map[i][j] = ch[j];
			}
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if(!visit[i][j]) {
					normal++;
					dfs(i,j,map[i][j]);
				}
			}
		}
		visit = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if(map[i][j] == 'R') map[i][j] = 'G';
			}
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if(!visit[i][j]) {
					abnormal++;
					dfs(i,j,map[i][j]);
				}
			}
		}
		
		System.out.println(normal + " " + abnormal);
	}
	private static void dfs(int row, int col,char curColor) {
		visit[row][col] = true;
		
		for (int i = 0; i < 4; i++) {
			int nx = row + dx[i];
			int ny = col + dy[i];
			
			if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
			if(visit[nx][ny]) continue;
			
			if(map[nx][ny] == curColor) {
				dfs(nx,ny,curColor);
			}
		}
	}

}