[Java Algorithm] 적록색약 BOJ #10026

문제

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

10026번: 적록색약

 

내 문제 풀이

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

public class BOJ_10026 {

	static int n, cnt;
	static char[][] map, tmp;
	static Deque<int[]> que = new ArrayDeque<>();

	public static void dfs(int x, int y, char color) {
		if(x < 0 || y < 0 || x >= n || y >= n) return;
		if(color != tmp[x][y]) return;

		tmp[x][y] = 'F'; // 중복 방지

		dfs(x, y-1, color);
		dfs(x, y+1, color);
		dfs(x-1, y, color);
		dfs(x+1, y, color);
	}

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

		n = Integer.parseInt(in.readLine());
		map = new char[n][n];

		for(int i = 0; i < n; i++) {
			String str = in.readLine();
			for(int j = 0; j < n; j++) {
				map[i][j] = str.charAt(j);
			}
		}

		tmp = new char[n][n];
		for(int i = 0; i < n; i++) tmp[i] = Arrays.copyOf(map[i], n);
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(tmp[i][j] != 'F') {
					dfs(i, j, tmp[i][j]);
					cnt++;
				}
			}
		}
		out.append(cnt + " ");
		cnt = 0;

		for(int i = 0; i < n; i++) tmp[i] = Arrays.copyOf(map[i], n);
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(tmp[i][j] == 'G') tmp[i][j] = 'R';
			}
		}
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(tmp[i][j] != 'F') {
					dfs(i, j, tmp[i][j]);
					cnt++;
				}
			}
		}
		out.append(cnt);

		System.out.println(out);
	}

}

👉 DFS 문제

적록색약이 아닌 사람의 기준으로 먼저 확인 후 적록색약인 사람의 기준으로 확인하는 식으로 구현

• map 배열을 그대로 유지하기 위해서 tmp 배열을 만들고 복사해서 사용했다.
• 먼저 적록색약이 아닌 사람의 기준으로 확인했는데,
  tmp 배열을 탐색하면서 'F'가 아닌 경우 dfs 메서드를 실행하도록 했다.
• dfs 메서드에서는 탐색하면서, 인접하며 같은 문자를 가진 곳들을 찾고
  그 곳들은 모두 'F'로 바꿔주어 중복된 탐색을 할 수 없도록 해주었다.
• 위와 같은 실행을 반복하며 그룹의 개수를 세고, out에 cnt를 추가한 뒤 cnt는 다시 0으로 초기화했다.
• 이제 적록색약인 사람의 기준으로 확인할 차례이므로, 다시 tmp에 map 배열을 복사해준 뒤,
  tmp를 탐색하며 'G'인 자리는 'R'로 바꿔주었다. (같은 색으로 인지하므로)
• 그 다음 위에서 적록색약이 아닌 사람의 기준으로 확인했던 것과 같은 동작으로 탐색을 실행했다.

 

💡 피드백

• 간단한 문제였다.!! 근데 생각해보니 어차피 'F'가 아닐 경우 dfs를 실행하는 2중 for문은
  같은 코드를 두 번 반복하니,, 메서드로 만들어서 처리해줬으면 더 깔끔했을 것 같다.