백준 - 10026

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

public class Main {
	static char[][] board;
	static boolean[][] visited;
	static int[][] dir = {
			{1,0},{-1,0},{0,1},{0,-1}
	};
	static int N;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		board = new char[N][N];
		for(int i = 0; i < N; i++) {
			String a = br.readLine();
			for(int j = 0; j < N; j++) {
				board[i][j] = a.charAt(j);
			}
		}
		int fst = 0;
		visited = new boolean[N][N];
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(!visited[i][j]) {
					bfs(i,j, false);
					fst++;
				}
			}
		}
		int sec = 0;
		visited = new boolean[N][N];
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(!visited[i][j]) {
					bfs(i,j, true);
					sec++;
				}
			}
		}
		System.out.println(fst + " " + sec);
	}
	static void bfs(int i, int j, boolean isGreen) {		
		visited[i][j] = true;
		Queue<int[] > q = new ArrayDeque<>();
		q.offer(new int[] {i,j});
		
		while(!q.isEmpty()) {
			int[] a = q.poll();
			int r = a[0]; int c = a[1];
			
			for(int d = 0; d < 4; d++) {
				int nr = r + dir[d][0];
				int nc = c + dir[d][1];
				
				if(nr >= 0 && nc >= 0 && nr < N && nc < N && !visited[nr][nc]) {
					if(board[nr][nc] == board[i][j]) {
						visited[nr][nc] = true;
						q.offer(new int[] {nr,nc});
					}
					if(isGreen) {
						if(board[i][j] == 'R' && board[nr][nc] == 'G' || board[i][j] == 'G' && board[nr][nc] == 'R') {
							visited[nr][nc] = true;
							q.offer(new int[] {nr,nc});
						}
					}
 				}
			}
		}
	}
}

풀이과정 및 리뷰

• 문제 접근: bfs사용해 R / G / B마다 탐색하되, 인자로 isGreen을 받아 적록색약인 사람과 아닌사람의 영역을 구분하려고 함
• 시간복잡도: $O(N^2)$
• 풀이과정
  • 입력받은 보드에서 BFS를 이용해 일반인의 시각으로 색상 영역 개수를 셈
  • visited 배열 초기화 후, 적록색약자는 R과 G를 같은 색으로 간주하며 다시 BFS 수행
  • 두 경우의 영역 수를 각각 출력하여 구분된 영역 개수 비교
• 개선점
  • 조건 중복 발생. 아래처럼 같은 색인지 판단하는 함수를 분리하는 것이 가독성 및 재사용성에 좋음:

if(board[nr][nc] == board[i][j]) {
    ...
}
if(isGreen) {
    if(board[i][j] == 'R' && board[nr][nc] == 'G' || board[i][j] == 'G' && board[nr][nc] == 'R') {
        ...
    }
}

static boolean isSameColor(char a, char b, boolean isGreen) {
	if (a == b) return true;
	if (isGreen && ((a == 'R' && b == 'G') || (a == 'G' && b == 'R'))) return true;
	return false;
}

if (isSameColor(board[i][j], board[nr][nc], isGreen)) {
    visited[nr][nc] = true;
    q.offer(new int[]{nr, nc});
}