[백준 10026] - 적록색약

[문제] 

출처 - https://www.acmicpc.net/problem/10026

10026번: 적록색약

---

[문제 풀이]

맵은 R, G, B 중 하나를 색칠한 그림이 있다.

적록색약은 'G' 를 'R' 으로 판단한다

구역은 같은 색으로 이루어져 있고 같은 색상이 상하좌우에 인접해 있는 경우 두 글자는 같은 구역이다.

적록색약인 사람이 봤을 때 와 아닌 사람이 봤을 때 구역의 수를 구하자!

 

• 적록색약이 아닌 사람의 봤을 때 구역을 BFS로 구한다.
• 구역을 StringBuilder에 넣어주고 방문한 map과 구역의 개수를 초기화한다.
• 맵의 'G' 을 'R'로 바꾼다.
• 적록색약인 사람이 봤을 때 구역을 BFS로 구한다.

 

---

[소스 코드]

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

class Node{
	int x;
	int y;
	Node(int x, int y){
		this.x = x;
		this.y = y;
	}
}

public class Main {

	static final int dx[] = {0,0,1,-1};
	static final int dy[] = {1,-1,0,0};
	static int n;
	static char[][] map;
	static boolean[][] visit;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		n = Integer.parseInt(br.readLine());
		map = new char[n][n];
		visit = new boolean[n][n];
		for(int i=0; i<n; i++) {
			String s = br.readLine();
			for(int j=0; j<n; j++) {
				map[i][j] = s.charAt(j);
			}
		}
		
		//일반인일 경우
		int cnt = 0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(!visit[i][j]) {
					bfs(i,j,map[i][j]);
					cnt++;
				}
			}
		}
		sb.append(cnt + " ");
		
		cnt = 0; //구역 초기화
		visit = new boolean[n][n]; //방문지역 초기화
		
        	//map의 G 를 R로 바꾼다.
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(map[i][j] == 'G') {
					map[i][j] = 'R';
				}
			}
		}
        
		//적록색약일 경우
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(!visit[i][j]) {
					bfs(i,j,map[i][j]);
					cnt++;
				}
			}
		}
		sb.append(cnt);
	
		
		System.out.println(sb);
	}
	
	static void bfs(int x, int y, char color) {
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(x,y));
		visit[x][y] = true;
		while(!q.isEmpty()) {
			Node p = q.poll();
			x = p.x;
			y = p.y;
			
			for(int k=0; k<4; k++) {
				int nx = x + dx[k];
				int ny = y + dy[k];
				
				if(0<=nx && nx<n && 0<=ny && ny<n) {
					if(map[nx][ny] == color && !visit[nx][ny]) {
						q.add(new Node(nx,ny));
					}
				}
			}		
		}
	}
}