문제

백준 10026번
https://www.acmicpc.net/problem/10026

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

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

---

생각하기

2개의 방향으로 생각하면 문제를 풀 수있다.

1. 'R', 'G', 'B'를 모두 파악하는 방향
2. 'R' 또는 'G', 그리고 'B' 이렇게 파악하는 방향

나는 총 4번의 큰 회전을 고려했다.

기본 색깔인 R, G, B는 두고 'R' 또는 'G'로 할 'T'를 하나 새로 만들어서 색상 배열을 만들었다.
colors = {R, G, B, T};

이렇게 하면 4개동안 최대 100 * 100의 배열을 탐색하면 40000번의 탐색만 하면되기 때문에 1초로도 충분한 시간이었다.

동작

		for(int i=0; i<4; i++) {
			int result = 0;
			char color = colors[i];
			visit = new boolean[N][N];

			for(int j=0; j<N; j++) {
				for(int k=0; k<N; k++) {

					if(color == 'T' && !visit[j][k] && (arr[j][k] == 'R' || arr[j][k] == 'G')) {
						DFS(j, k, color);
						result++;
					}	
					else if(!visit[j][k] && arr[j][k] == color) {
						DFS(j, k, color);
						result++;
					}

				}
			}

색상의 배열 갯수만큼 회전을 하고, color가 T일 때가 적녹색맹일 때를 고려한 값이다.

이 때는 조건을 arr이 R 또는 G로 주어서 2가지 색상모두 찾도록 만들었다.

			switch(color) {
				case 'R': R = result;
				break;
				case 'G': G = result;
				break;
				case 'B': B = result;
				break;
				case 'T': T = result;
				break;
			}
		}	

		int person1 = R + G + B;
		sb.append(person1 + " ");

		int person2 = B + T;
		sb.append(person2);

이렇게 해서 파악된 값인 result를 색상 변수에 넣어주고 출력하면 결과를 얻을 수 있다.

DFS

BFS

---

코드

DFS

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

public class Main {
	static char arr[][];
	static boolean visit[][];
	static int dirX[] = {0, 0, -1, 1}; // 상 하 좌 우
	static int dirY[] = {-1, 1, 0, 0};

	static int N, nowX, nowY;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		N = Integer.parseInt(br.readLine());
		int R = 0, G = 0, B = 0, T = 0;

		arr = new char[N][N];
		char colors[] = {'R', 'G', 'B', 'T'}; 

		for(int i=0; i<N; i++) {
			String str = br.readLine();

			for(int j=0; j<N; j++) {
				arr[i][j] = str.charAt(j);
			}
		}	

		for(int i=0; i<4; i++) {
			int result = 0;
			char color = colors[i];
			visit = new boolean[N][N];

			for(int j=0; j<N; j++) {
				for(int k=0; k<N; k++) {

					if(color == 'T' && !visit[j][k] && (arr[j][k] == 'R' || arr[j][k] == 'G')) {
						DFS(j, k, color);
						result++;
					}	
					else if(!visit[j][k] && arr[j][k] == color) {
						DFS(j, k, color);
						result++;
					}

				}
			}
			
			switch(color) {
				case 'R': R = result;
				break;
				case 'G': G = result;
				break;
				case 'B': B = result;
				break;
				case 'T': T = result;
				break;
			}
		}	

		int person1 = R + G + B;
		sb.append(person1 + " ");

		int person2 = B + T;
		sb.append(person2);

		System.out.println(sb);
	} // End of main

	static void DFS(int x, int y, char color) {
		visit[x][y] = true;

		for(int i=0; i<4; i++) {
			nowX = dirX[i] + x;
			nowY = dirY[i] + y;

			if(color == 'T') {
				if(range_check() && !visit[nowX][nowY] && (arr[nowX][nowY] == 'R' || arr[nowX][nowY] == 'G')) {
					DFS(nowX, nowY, color);
				}
			}
			else if(range_check() && !visit[nowX][nowY] && arr[nowX][nowY] == color) {
				DFS(nowX, nowY, color);
			}
		}


	} // End of DFS

	static boolean range_check() {
		return (nowX >= 0 && nowY >= 0 && nowX < N && nowY < N); >
	} // End range_check

} // End of class

BFS

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

public class Main {
	static char arr[][];
	static boolean visit[][];
	static int dirX[] = {0, 0, -1, 1}; // 상 하 좌 우
	static int dirY[] = {-1, 1, 0, 0};

	static int N, nowX, nowY;

	static class Node {
		int x;
		int y;

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

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		N = Integer.parseInt(br.readLine());
		int R = 0, G = 0, B = 0, T = 0;

		arr = new char[N][N];
		char colors[] = {'R', 'G', 'B', 'T'}; 

		for(int i=0; i<N; i++) {
			String str = br.readLine();

			for(int j=0; j<N; j++) {
				arr[i][j] = str.charAt(j);
			}
		}	


		for(int i=0; i<4; i++) {
			int result = 0;
			char color = colors[i];
			visit = new boolean[N][N];

			for(int j=0; j<N; j++) {
				for(int k=0; k<N; k++) {

					if(color == 'T' && !visit[j][k] && (arr[j][k] == 'R' || arr[j][k] == 'G')) {
						BFS(j, k, color);
						result++;
					}	
					else if(!visit[j][k] && arr[j][k] == color) {
						BFS(j, k, color);
						result++;
					}

				}
			}
			
			switch(color) {
				case 'R': R = result;
				break;
				case 'G': G = result;
				break;
				case 'B': B = result;
				break;
				case 'T': T = result;
				break;
			}
		}	

		int person1 = R + G + B;
		sb.append(person1 + " ");

		int person2 = B + T;
		sb.append(person2);

		System.out.println(sb);
	} // End of main

	static void BFS(int x, int y, char color) {
		Queue<Node> que = new LinkedList<>();
		visit[x][y] = true;
		que.offer(new Node(x, y));

		while( !que.isEmpty() ) {
			Node node = que.poll();

			for(int i=0; i<4; i++) {
				nowX = dirX[i] + node.x;
				nowY = dirY[i] + node.y;

				if(color == 'T') {
					if(range_check() && !visit[nowX][nowY] && (arr[nowX][nowY] == 'R' || arr[nowX][nowY] == 'G')) {
						visit[nowX][nowY] = true;
						que.offer(new Node(nowX, nowY));
					}
				}
				else if(range_check() && !visit[nowX][nowY] && arr[nowX][nowY] == color) {
					visit[nowX][nowY] = true;
					que.offer(new Node(nowX, nowY));
				}

			}
		}

	} // End of BFS

	static boolean range_check() {
		return (nowX >= 0 && nowY >= 0 && nowX < N && nowY < N); 	
	} // End range_check

} // End of class