[백준/Java] 10026 - 적록색약

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

문제

---

풀이

BFS나 DFS를 활용해서 구역이 같은 부분의 개수를 구하는 문제이다

적록색약이 아닌 사람의 경우를 구할 때는 주어진 배열을 그대로 이용하여 bfs를 돌리면 되고

적록색약인 사람의 경우에는 배열 값이 G가 나왔을 때 R로 바꿔주어 같은 구역으로 만들고 bfs를 돌리면 된다

 

bfs 내에서는 현재 위치의 색깔을 저장하고 상하좌우의 인접한 위치의 색깔과 같으면 큐에 추가하는 방식으로 진행하였다

코드

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

public class Main {

	static int N;
	static char[][] arr;
	static boolean[][] visited;

	static int[] dx = {-1, 1, 0, 0}; // 상하
	static int[] dy = {0, 0, -1, 1}; // 좌우

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

		N = Integer.parseInt(br.readLine());
		arr = new char[N][N];
		visited = new boolean[N][N];

		for (int i = 0; i < N; i++) {
			arr[i] = br.readLine().toCharArray();
		}

		// 적록색약이 아닌 사람이 봤을 때 구역 수 계산
		int normalCount = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				// 방문하지 않은 요소일때 bfs 탐색
				if (!visited[i][j]) {
					bfs(i, j);
					normalCount++;
				}
			}
		}

		// G를 R로 변경하여 같은 구역으로 만들어줌
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (arr[i][j] == 'G') {
					arr[i][j] = 'R';
				}
			}
		}

		// 방문 처리 배열을 초기화하고 구역 수 계산
		visited = new boolean[N][N];
		int rgCount = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!visited[i][j]) {
					bfs(i, j);
					rgCount++;
				}
			}
		}

		System.out.println(normalCount + " " + rgCount);

		br.close();
	}

	static void bfs(int x, int y) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[]{x, y});
		visited[x][y] = true;
		char color = arr[x][y]; // 현재 위치의 색깔을 저장

		while (!queue.isEmpty()) {
			int[] current = queue.poll();

			for (int i = 0; i < 4; i++) {
				// 인접한 위치 탐색
				int nx = current[0] + dx[i];
				int ny = current[1] + dy[i];

				// 배열 범위 안에 있고
				if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
					// 방문하지 않았고 현재 색과 인접한 위치의 색과 같으면 진행
					if (!visited[nx][ny] && arr[nx][ny] == color) {
						visited[nx][ny] = true;
						queue.add(new int[]{nx, ny});
					}
				}
			}
		}
	}
}

결과