적록색약

문제

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

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

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

RRRBB GGBBB BBBRR BBRRR RRRRR

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

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

입력

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

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

출력

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

 

 

import java.util.*;

class Main {
	static int n;	// 그리드 크기
	static char[][] board1;	// 정상 그림
	static char[][] board2;	// 적록색약 그림
	static int[] dx = { 1, 0, -1, 0 };
	static int[] dy = { 0, 1, 0, -1 };
	static int cnt = 0;	// 구역 수

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();

		board1 = new char[n][n];
		board2 = new char[n][n];

		for (int i = 0; i < n; i++) {
			String str = scan.next();
			for (int j = 0; j < n; j++) {
				board1[i][j] = str.charAt(j);
				if (str.charAt(j) == 'G') {	// 적록색약이므로 초록색을 빨간색으로 바꿈
					board2[i][j] = 'R';
					continue;
				}
				board2[i][j] = str.charAt(j);
			}
		}
		
		while (findR(board1) != null) {	
			bfs(findR(board1).x, findR(board1).y, board1);
		}
		while (findG(board1) != null) {
			bfs(findG(board1).x, findG(board1).y, board1);
		}
		while (findB(board1) != null) {
			bfs(findB(board1).x, findB(board1).y, board1);
		}

		System.out.print(cnt + " ");	// 정상 그림 구역수

		cnt = 0;

		while (findR(board2) != null) {
			bfs(findR(board2).x, findR(board2).y, board2);
		}
		while (findG(board2) != null) {
			bfs(findG(board2).x, findG(board2).y, board2);
		}
		while (findB(board2) != null) {
			bfs(findB(board2).x, findB(board2).y, board2);
		}
		System.out.print(cnt);	// 적록색약 그림 구역수
	}

	static Dot findR(char[][] board) {	// 빨간 구역 찾기
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (board[i][j] == 'R') {
					return new Dot(i, j);
				}
			}
		}
		return null;
	}

	static Dot findG(char[][] board) {	// 초록 구역 찾기
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (board[i][j] == 'G') {
					return new Dot(i, j);
				}
			}
		}
		return null;
	}

	static Dot findB(char[][] board) {	// 파랑 구역 찾기
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (board[i][j] == 'B') {
					return new Dot(i, j);
				}
			}
		}
		return null;
	}

	static void bfs(int x, int y, char[][] board) { // bfs
		Queue<Dot> q = new LinkedList<Dot>();
		q.add(new Dot(x, y));
		
		if (board[x][y] == 'R') {	// 빨간 구역 탐색
			board[x][y] = 'O';

			while (!q.isEmpty()) {
				Dot d = q.poll();

				for (int i = 0; i < 4; i++) {
					int next_x = d.x + dx[i];
					int next_y = d.y + dy[i];

					if (next_x < 0 || next_y < 0 || next_x >= n || next_y >= n || board[next_x][next_y] == 'O'
							|| board[next_x][next_y] == 'G' || board[next_x][next_y] == 'B')
						continue;

					q.add(new Dot(next_x, next_y));
					board[next_x][next_y] = 'O';
				}
			}

			cnt++;
		} else if (board[x][y] == 'G') {	// 초록 구역 탐색
			board[x][y] = 'O';

			while (!q.isEmpty()) {
				Dot d = q.poll();

				for (int i = 0; i < 4; i++) {
					int next_x = d.x + dx[i];
					int next_y = d.y + dy[i];

					if (next_x < 0 || next_y < 0 || next_x >= n || next_y >= n || board[next_x][next_y] == 'O'
							|| board[next_x][next_y] == 'R' || board[next_x][next_y] == 'B')
						continue;

					q.add(new Dot(next_x, next_y));
					board[next_x][next_y] = 'O';
				}
			}

			cnt++;
		} else if (board[x][y] == 'B') {	// 파란 구역 탐색
			board[x][y] = 'O';

			while (!q.isEmpty()) {
				Dot d = q.poll();

				for (int i = 0; i < 4; i++) {
					int next_x = d.x + dx[i];
					int next_y = d.y + dy[i];

					if (next_x < 0 || next_y < 0 || next_x >= n || next_y >= n || board[next_x][next_y] == 'O'
							|| board[next_x][next_y] == 'R' || board[next_x][next_y] == 'G')
						continue;

					q.add(new Dot(next_x, next_y));
					board[next_x][next_y] = 'O';
				}
			}

			cnt++;
		}
	}
}

class Dot {
	int x;
	int y;

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

 

문제출처

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