[BOJ/Java] 10026. 적록색약

[BOJ/Java] 10026. 적록색약

10026번: 적록색약

---

문제 해석

적록색약 문제는 NxN 격자에 분포된 R(빨강), G(녹색), B(파랑) 세 가지 색을 바탕으로, 정상인과 적록색약인 사람이 각각 보는 구역의 수를 구하는 문제이다. 적록색약인 사람은 빨강과 녹색의 차이를 구분하지 못해 이 두 색을 같은 색으로 본다.

풀이 과정

1. 입력을 받아 두 개의 격자 배열 map01과 map02를 생성한다. map01은 정상인용, map02는 적록색약인용 격자로, 적록색약인용 격자에서는 녹색(G)을 빨강(R)으로 변환한다.
2. BFS(Breadth-First Search)를 활용하여 연결된 같은 색상의 구역을 찾는다. 각 구역마다 탐색을 시작할 때마다 구역 수를 증가시키고, 이미 방문한 지점은 다시 방문하지 않도록 한다.
3. 두 배열에 대해 각각 BFS를 수행하여 구역의 수를 구하고, 결과를 출력한다.

코드

package edu.ssafy.im.BOJ.Gold.G5.No10026;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		new Main().io();
	}

	private int n;  // 격자의 크기
	private char[][] map01;  // 정상인용 격자
	private char[][] map02;  // 적록색약인용 격자
	private boolean[][] visited;  // 방문 체크용 배열
	private static final int[][] direction = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };  // 이동 방향 (상하좌우)

	private void io() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		n = Integer.parseInt(br.readLine());
		
		map01 = new char[n][n];
		map02 = new char[n][n];
		for (int i = 0; i < map01.length; i++) {
			String row = br.readLine();
			for (int j = 0; j < map01.length; j++) {
				map01[i][j] = row.charAt(j);
				if(map01[i][j] == 'G') {
					map02[i][j] = 'R';  // 적록색약인 경우 녹색을 빨강으로 변환
				} else {
					map02[i][j] = map01[i][j];
				}
			}
		}
		
		sb.append(sol(map01)).append(" ").append(sol(map02));  // 각 격자별 구역 수 계산 및 출력
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	private int sol(char[][] map) {
		visited = new boolean[n][n];
		int ans = 0;
		for (int i = 0; i < map01.length; i++) {
			for (int j = 0; j < map01.length; j++) {
				if(!visited[i][j]) {
					bfs(i, j, map[i][j], map);
					ans++;
				}
			}
		}
		return ans;
	}

	private void bfs(int x, int y, int COLOR, char[][] map) {
		Queue<Point> queue = new ArrayDeque<>();
		queue.offer(new Point(x, y));
		visited[x][y] = true;
		
		while (!queue.isEmpty()) {
			Point p = queue.poll();
			for (int d = 0; d < direction.length; d++) {
				int nx = p.x + direction[d][0];
				int ny = p.y + direction[d][1];
				
				if(nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny] || map[nx][ny] != COLOR) continue;
				
				visited[nx][ny] = true;
				queue.offer(new Point(nx, ny));
			}
		}
	}

	class Point {
		int x, y;

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

시간 복잡도 분석

BFS를 통해 각 색깔별로 연결된 구역을 찾는 과정에서 최악의 경우 모든 격자점을 한 번씩 방문한다. 따라서 시간 복잡도는 O(N^2)이다.

느낀점

적록색약 문제는 입력 데이터를 변형하여 두 가지 상황에서 BFS를 동일하게 적용하는 방식이 인상적이다. 다양한 BFS 적용 사례를 경험할 수 있어 BFS에 대한 이해도를 높일 수 있었다.