백준 10026. 적록색약 (BFS)

www.acmicpc.net/problem/10026

10026번: 적록색약

문제제목 : 적록색약

문제난이도 : 골드5

문제유형 : BFS, DFS

문제

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

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

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

RRRBB

GGBBB

BBBRR

BBRRR

RRRRR

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

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

입력

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

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

출력

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

접근방식

1. R,G,B가 같은 것끼리 뭉쳐져있는 구역의 개수를 구하는 문제이므로 BFS알고리즘을 사용하였다.

2. 적록색약인 사람의 경우, R과 G를 동일하게 보고 적록색약이 아닌 사람은 R, G, B 각각 따로 구분 짓는다.

3. 적록색약인지 아닌지의 여부는 파라미터에 boolean 값을 이용하여 구분지었다.

코드

package week6;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ10026 {
	public static int N;
	public static boolean[][] visited;
	public static char[][] board;
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, -1, 1};

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		//입력
		N = Integer.parseInt(br.readLine());
		board = new char[N][N];
		for (int i = 0; i < N; i++) {
			String input = br.readLine();
			for (int j = 0; j < N; j++) {
				board[i][j] = input.charAt(j);
			}
		}
		
		//적록색약이 아닌 사람이 보는 구역
		visited = new boolean[N][N];
		int count = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!visited[i][j]) {
					BFS(false, i, j);
					count++;
				}
			}
		}
		bw.write(String.valueOf(count) + " ");
		
		//적록색약인 사람이 보는 구역
		visited = new boolean[N][N];
		count = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!visited[i][j]) {
					BFS(true, i, j);
					count++;
				}
			}
		}
		bw.write(String.valueOf(count) + " ");
		bw.flush();
		bw.close();
		br.close();
	}
	
	public static void BFS(boolean rgb, int x, int y) {
		Queue<Pos> q = new LinkedList<Pos>();
		q.add(new Pos(x, y));
		visited[x][y] = true;
		
		while (!q.isEmpty()) {
			Pos now = q.poll();
			
			for (int i = 0; i < 4; i++) {
				int next_x = now.x + dx[i];
				int next_y = now.y + dy[i];
				
				if (next_x < 0 || next_y < 0 || next_x >= N || next_y >= N) {
					continue;
				}
				
				char nowValue = board[now.x][now.y];
				char nextValue = board[next_x][next_y];
				
				if (!rgb) { 
					//적록색약이 아닌 사람
					if (!visited[next_x][next_y] && nextValue == nowValue) {
						q.add(new Pos(next_x, next_y));
						visited[next_x][next_y] = true;
					} 
				} else {
					//적록색약인 사람
					if (nowValue == 'B') {
						if (!visited[next_x][next_y] && nextValue == nowValue) {
							q.add(new Pos(next_x, next_y));
							visited[next_x][next_y] = true;
						} 
					} else { //청록, 레드 색상은 동일하게 취급
						if (!visited[next_x][next_y] && (nextValue == 'R' || nextValue == 'G')) {
							q.add(new Pos(next_x, next_y));
							visited[next_x][next_y] = true;
						} 
					}
				}
			}
		}
	}
}

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

---

BFS,DFS문제는 익숙해져서 그런지 생각보다 금방 풀 수 있었다. 그래도 코드를 작성하면서 머뭇거리고 참고한 부분이 있으므로 꾸준히 연습해야겠다. BFS() 메소드 안의 조건문을 더 간결하게 줄이고 중복코드를 없애고 싶었는데 중복코드를 줄이니까 가독성이 조금 떨어짐을 느껴서 일단 이렇게 작성~! 뭐...간단한 코드여서 줄이나 마나긴 하지만.....ㅎㅎ

홧팅~푸힝힝