[BOJ] 10026 적록색약 [Java]

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

10026번: 적록색약

---

1. 문제 요약

주어진 map에 대하여, 적록색약이 아닌 사람은 R,G,B를 각각 다른색으로 보고 적록색약인 사람은 R,G는 같은 색으로 본다.

이 때, 같은 색끼리의 구역의 개수를 구하는 문제이다.

 

 

2. 풀이

DFS로 순회한 구역의 개수를 세주는 문제이다. DFS 함수는 전형적인 틀을 사용하였다.

주의할 점은 적록색약인 경우 continue 조건이다.

나는 이 조건을 아래와 같이 주었다.

시작점이 R또는 G인 경우, B를 만나면 넘어가겠다 (R,G를 같은 색으로 묶음)

시작점이 B인 경우, B가 아닌 다른 색을 만나면 넘어가겠다

 

1. map에서 모든 점을 순회하며 방문하지 않은 점에 대해서 DFS를 수행한다.

2. DFS를 사용하여 같은 색끼리의 구역을 모두 방문한다, 방문했으면 visited를 true로 갱신해준다.

3. 적록색약이 아닌 경우 dfs1(), visited1 / 적록색약인 경우 dfs2(), visited2를 사용했다.

 

3. 문제점

1. 중복되는 코드가 많다.

- dfs 함수의 틀은 거의 같고, 조건 한 두줄만 다르다. 

 

2. 배열이 많다.

- 이중for문 돌릴 때 한번에 2개의 dfs를 돌리려고 했기 때문에 dfs함수 2개, visited 배열 2개가 필요했다. 
반복문을 여러번 돌리는 것보다 배열을 하나 더 만드는게 낫지않을까? 하는 생각으로 만들었다.

 

4. 코드

방법1. dfs1(), dfs2() 구분

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	static int[] dy = {-1, 1, 0, 0};
	static int[] dx = {0, 0, -1, 1};
	static int N, cnt1, cnt2;
	static char color;
	static char[][] map;
	static boolean[][] visited1, visited2;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new char[N][N];
		visited1 = new boolean[N][N];
		visited2 = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			map[i] = br.readLine().toCharArray();
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				color = map[i][j];
				if (!visited1[i][j]) {
					dfs1(i, j);
					cnt1++;
				}
				if (!visited2[i][j]) {
					dfs2(i, j);
					cnt2++;
				}
			}
		}
		System.out.println(cnt1 + " " + cnt2);
	}
	
	//적록색약 아님
	static void dfs1(int y, int x) {
		visited1[y][x] = true;
		for (int d = 0; d < 4; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];
			if (ny < 0 || nx < 0 || ny >= N || nx >= N||visited1[ny][nx]) continue;
			if (map[ny][nx] != color) continue;
			visited1[ny][nx] = true;
			dfs1(ny, nx);
		}
		
	}

	// 적록색약
	static void dfs2(int y, int x) {
		visited2[y][x] = true;
		for (int d = 0; d < 4; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];
			if (ny < 0 || nx < 0 || ny >= N || nx >= N || visited2[ny][nx]) continue;
			if ((color == 'R' || color == 'G') && map[ny][nx] == 'B') continue;
			else if (color == 'B' && map[ny][nx] != 'B') continue;
			visited2[ny][nx] = true;
			dfs2(ny, nx);
		}
	}
}

방법2. dfs 같이 씀

* visited 배열을 재활용하기 위해 중간에 초기화를 해줘야 했다.

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

public class BOJ_10026_적록색약 {

	static int[] dy = {-1, 1, 0, 0};
	static int[] dx = {0, 0, -1, 1};
	static int N, cnt1, cnt2;
	static char color;
	static char[][] map;
	static boolean[][] visited;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new char[N][N];
		visited = new boolean[N][N];
		
		//입력받는방법1. 한줄을 통째로 넣어줌
		for (int i = 0; i < N; i++) {
			map[i] = br.readLine().toCharArray();
		}
		//입력받는방법2. 문자 하나하나를 넣어줌 -> 입력받을 때 조건을 처리해줄 수 있음
		/*
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = br.readLine().charAt(j);
			}
		}
		*/
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				color = map[i][j];
				if (!visited[i][j]) {
					dfs1(i, j);
					cnt1++;
				}
			}
		}
		//visited 초기화 방법1 - Arrays.fill(배열, false);
		for (int i = 0; i < N; i++) {
			Arrays.fill(visited[i], false); 
		}
		//visited 초기화 방법2 - 객체 새로 생성
		//visited = new boolean[N][N];
		
		//map의 R->G로 바꿔줌
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 'R') {
					map[i][j] = 'G';
				}
			}
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				color = map[i][j];
				if (!visited[i][j]) {
					dfs1(i, j);
					cnt2++;
				}
			}
		}
		System.out.println(cnt1 + " " + cnt2);
	}
	
	//적록색약 아님
	static void dfs1(int y, int x) {
		visited[y][x] = true;
		for (int d = 0; d < 4; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];
			if (ny < 0 || nx < 0 || ny >= N || nx >= N||visited[ny][nx]) continue;
			if (map[ny][nx] != color) continue;
			visited[ny][nx] = true;
			dfs1(ny, nx);
		}
		
	}

	/*
	// 적록색약
	static void dfs2(int y, int x) {
		visited2[y][x] = true;
		for (int d = 0; d < 4; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];
			if (ny < 0 || nx < 0 || ny >= N || nx >= N || visited2[ny][nx]) continue;
			if ((color == 'R' || color == 'G') && map[ny][nx] == 'B') continue;
			else if (color == 'B' && map[ny][nx] != 'B') continue;
			visited2[ny][nx] = true;
			dfs2(ny, nx);
		}
	}
	*/
}