<백준> 10026번 적록색약

<링크>

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

[Gold V] 적록색약 - 10026

문제 링크

성능 요약

메모리: 20540 KB, 시간: 200 ms

분류

너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 9월 5일 14:02:44

문제 설명

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

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

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

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

입력

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

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

출력

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

 

 

<아이디어>

1. 상하좌우 다 보면서 그룹핑을 해야하니까 DFS가 더 적절할것 같았는데.. BFS가 아직은 더 익숙해서 BFS로 완전탐색을 돌려봐야겠다 생각!

2. BFS돌릴때, 색약인가 아닌가로 1차적으로 구역을 나누자.

3. 색약일 경우에, R이랑 G는 구별이 안되니까, 하나라고 생각을 해서 or 연산을 쓰는게 좋겠다. +  B일경우에도 queue는 돌아야하니까 꼭 추가해주기!

4. 색약이 아니면 뭐.. 전값이랑 현값이 같으면 queue에 넣어주면 끝!

5. 색약인사람과 색약이 아닌사람 각각 따로 돌아야하니까, visited는 꼭 초기화 해주기!!!!!!!!!

  

 

<풀이 - Java >

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class Main {

	static int N;
	static String[][] matrix;
	static boolean[][] visited;
	// 정상인꺼 count
	static int count;
	// 적록 색약 count
	static int rgCount;

	static int[] dx = { 1, 0, -1, 0 };
	static int[] dy = { 0, 1, 0, -1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		matrix = new String[N][N];
		visited = new boolean[N][N];
		count = 0;
		rgCount = 0;

		for (int i = 0; i < N; i++) {
			String[] split = br.readLine().split("");
			for (int j = 0; j < N; j++) {
				matrix[i][j] = split[j];
			}
		}
		// 정상
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!visited[i][j]) {
					bfs(i, j, false);
					count++;
				}
			}
		}
		// 색약
		// 초기화...
		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, true);
					rgCount++;
				}
			}
		}
		System.out.println(count + " " + rgCount);
	}

	private static void bfs(int i, int j, boolean rg) {
		visited[i][j] = true;
		Queue<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] { i, j });
		String currentColor = matrix[i][j];

		while (!queue.isEmpty()) {
			int[] current = queue.poll();
			int ex = current[0];
			int ey = current[1];
			for (int k = 0; k < 4; k++) {
				int nx = ex + dx[k];
				int ny = ey + dy[k];

				if (isTrue(nx, ny) && !visited[nx][ny]) {
					String nextColor = matrix[nx][ny];
					if (rg) {
						if (currentColor.equals("R") || currentColor.endsWith("G")) {
							if (nextColor.equals("R") || nextColor.equals("G")) {
								queue.add(new int[] { nx, ny });
								visited[nx][ny] = true;
							}
						} else if (currentColor.equals("B")) {
							if (nextColor.equals("B")) {
								queue.add(new int[] { nx, ny });
								visited[nx][ny] = true;
							}
						}
					} else {
						if (nextColor.equals(currentColor)) {
							queue.add(new int[] { nx, ny });
							visited[nx][ny] = true;
						}
					}
				}
			}

		}

	}

	private static boolean isTrue(int i, int j) {
		return i >= 0 && i < N && j >= 0 && j < N;
	}
}