[BOJ - JAVA] 10026 - 적록색약 (BFS)

# 주소

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

10026번: 적록색약

# 문제

# 문제 해설 및 코드 리뷰

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
public class Main{
	static int n;
	static char[][] normal;
	static char[][] unnormal;
	static int dx[] = {1,0,-1,0};
	static int dy[] = {0,1,0,-1};
	static boolean[][] normal_visit;
	static boolean[][] unnormal_visit;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		normal = new char[n][n];
		unnormal = new char[n][n]; 
		normal_visit = new boolean[n][n];
		unnormal_visit = new boolean[n][n];
		for(int i = 0; i < n; i++) {
			String str = br.readLine();
			for(int j = 0; j < n; j++) {
				normal[i][j] = str.charAt(j);
				unnormal[i][j] = str.charAt(j);
				if(unnormal[i][j] == 'G')
					unnormal[i][j] = 'R';
			}
		}
		int count = 0;
		int count2 = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(normal_visit[i][j] == false) {
					dfs(i,j,normal[i][j]);
					count++;
				}
				if(unnormal_visit[i][j] == false) {
					dfs2(i,j,unnormal[i][j]);
					count2++;
				}
			}
		}
		System.out.println(count + " " + count2);
	}
	public static void dfs(int x, int y, char g) {
		LinkedList<Point> queue = new LinkedList<Point>();
		normal_visit[x][y] = true;
		queue.offer(new Point(x,y));
		while(!queue.isEmpty()) {
			Point now = queue.poll();
			for(int i = 0; i < 4; i++) {
				int nx = now.x + dx[i];
				int ny = now.y + dy[i];
				if(nx >= 0 && nx < n && ny >= 0 && ny < n) {
					if(normal_visit[nx][ny] == false && normal[nx][ny] == g) {
						dfs(nx,ny, normal[nx][ny]);
					}
				}
			}
		}
	}
	public static void dfs2(int x, int y, char g) {
		LinkedList<Point> queue = new LinkedList<Point>();
		unnormal_visit[x][y] = true;
		queue.offer(new Point(x,y));
		while(!queue.isEmpty()) {
			Point now = queue.poll();
			for(int i = 0; i < 4; i++) {
				int nx = now.x + dx[i];
				int ny = now.y + dy[i];
				if(nx >= 0 && nx < n && ny >= 0 && ny < n) {
					if(unnormal_visit[nx][ny] == false && unnormal[nx][ny] == g) {
						dfs2(nx,ny, unnormal[nx][ny]);
					}
				}
			}
		}
	}
}

제가 푼 거중 제일 코드 길이가 길었습니다. (80줄 정도)

bfs문제이기 때문에 Queue를 활용했습니다.

근데 normal과 unnormal 배열 두 개를 만들어서 각각 bfs를 돌려야 하기 때문에 코드 길이가 길어질 수 밖에...없었습니다

normal 배열은 정상인의 입장에서 적록색약을 보는 것이므로 일반적인 bfs문을 돌리면 되겠습니다.

그러나 unnormal은 G와 R을 구분 못한다 하였으므로 둘 중 하나를 통일해서 사용해야 합니다.

따라서 G를 갖고 있으면 모두 R로 바꾸고 이 두 색깔의 각각의 고립된 영역을 구했습니다.

개념자체는 워낙 쉽기 때문에 어렵지 않으시겠지만 전 코드양이 너무 많이 나와서 30분 동안 타자만 친 것 같네요.

다음엔 DFS로 한 번 풀어볼게용

아 그리고 제가 메소드를 dfs랑 dfs2로 지정했는데 왜 그렇게 했는지 사실 저도 몰라요.

이클립스로 코드 작성하고 옮겨서 실행하는 타입이라, 별 생각없이 저렇게 친 것 같은데 수정하실분은 수정하셔요.

 

감사합니다.