백준 10026 적록색약

문제

---

10026번: 적록색약 (acmicpc.net)

해결방법

---

• BFS를 통해 두개의 배열을 탐색하여 그룹의 개수를 각각 구하면 된다.

• R, G, B 가 그대로 설정된 2차원 배열과 R을 G로 변경한 2차원 배열 2가지를 탐색하여 그룹의 수를 찾는다.

• 각 배열을 BFS로 4방향 탐색하며 이동할 곳이 현재 그룹의 RGB와 같은 값이고 다른 그룹에 속하지 않았다면 그곳으로 이동하고 그룹에 포함한다.

• 두 배열의 그룹의 수를 출력해준다.

동작과정

---

1. 2차원 배열 형태로 RGB를 입력받으면서 색약이 아닌 사람이 보는 배열과 적록색약인 사람이 보는 배열 두가지의 형태로 2차원 배열을 두개 저장한다.
2. 각 map에서 해당하는 칸이 어느 그룹에 속하는지를 나타내기 위한 2차원 group 배열을 선언한다. 이 때 어느 그룹에도 속하지 못한 곳은 값이 0이다.
3. group 배열을 순회하면서 값이 0이면 해당 위치부터 BFS를 수행하여 그룹을 묶고 숫자를 더한다.
4. 구한 group의 수 2개를 출력한다.

코드

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Queue;

/*
 * BFS를 통해 그룹을 묶고 탐색하는 문제
 * 두가지의 map을 만들어서 각각의 값을 구해낸다.
 */
public class Main{
	
	private static class Point {
		int y;
		int x;

		public Point(int y, int x) {
			this.y = y;
			this.x = x;
		}

	}
	
	private final static int[][] D = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
	private static int N;
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(in.readLine());
		
		// 색약이 아닌 사람이 보는 map
		char[][] map_original = new char[N][N];
		// 적록색약인 사람이 보는 map
		char[][] map_diff = new char[N][N];
		
		// 입력을 받으며 적록색약인 사람이 보는 map의 R을 G로 변경해준다.
		for(int i = 0; i < N; i++) {
			char[] line = in.readLine().toCharArray();
			for(int j = 0; j < N; j++) {
				map_original[i][j] = line[j];
				map_diff[i][j] = line[j];
				if(map_diff[i][j] == 'R')
					map_diff[i][j] = 'G';
			}
		}
		
		// 각 map의 group을 표시하기 위한 배열
		int[][] group_original = new int[N][N];
		int[][] group_diff = new int[N][N];
		
		// 각 map의 group 수
		int original_cnt = 0;
		int diff_cnt = 0;
		
		// 배열을 순회하면서 아직 그룹에 속하지 않은 위치에서 BFS를 수행하여 이어지는 위치들을 그룹으로 묶는다.
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(group_original[i][j] == 0)
					bfs(new Point(i, j), map_original, group_original, ++original_cnt);
				if(group_diff[i][j] == 0)
					bfs(new Point(i, j), map_diff, group_diff, ++diff_cnt);
			}
		}
		
		out.write(original_cnt + " " + diff_cnt);
		out.flush();
	}
	
	// 아직 그룹에 존재하지 않는 위치에서 이어지는 값들을 묶어서 그룹을 만든다.
	private static void bfs(Point start, char[][] map, int[][] group, int g) {
		// 시작 값을 큐에 넣고 group 배열에 표시한다. 그리고 시작 값에 해당하는 값과 같은 값들을 찾기 위해 target을 저장한다.
		Queue<Point> q = new ArrayDeque<>();
		q.offer(start);
		char target = map[start.y][start.x];
		group[start.y][start.x] = g;
		
		// BFS 반복문
		while(!q.isEmpty()) {
			Point now = q.poll();
			
			// 4방향 탐색
			for(int d = 0; d < 4; d++) {
				int dy = now.y + D[d][0];
				int dx = now.x + D[d][1];
				
				// 범위 안에 있고 해당 값이 target과 같으면 그룹으로 묶어주고 Q에 위치를 추가해준다.
				if(isInBound(dy, dx) && group[dy][dx] == 0 && map[dy][dx] == target) {
					group[dy][dx] = g;
					q.offer(new Point(dy, dx));
				}
			}
		}
	}
	
	// 범위체크
	private static boolean isInBound(int y, int x) {
		return y >= 0 && y < N && x >= 0 && x < N;
	}
}