[Algorithm] 👁️백준 10026 적록색약

0. 문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력
적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

1. 아이디어

💡 정상인과 적록색약이 보는 배열을 따로 만듦
💡 적록색약의 배열은 G를 R로 바꿔놓음
💡 bfs 이용하여 연결된 땅 덩어리를 cnt함

2. 핵심 풀이

1. 정상인과 적록색약이 보는 배열을 따로 만듦

char[][] map = new char[n][n];
char[][] abnormalMap = new char[n][n];

2. 적록색약의 배열은 G를 R로 바꿔놓음

for (int i = 0; i < n; i++) {
	String[] s = br.readLine().split("");
	for (int j = 0; j < n; j++) {
		char tmp = s[j].charAt(0);
				
		if ('G' == tmp) {
			abnormalMap[i][j] = 'R';
			continue;
		}

		abnormalMap[i][j] = tmp;
		map[i][j] = tmp;
	}
}

3. bfs 이용하여 연결된 땅 덩어리를 cnt함

for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
		if (!visited[i][j]) {
			bfs(i, j, map);
			cnt[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, abnormalMap);
			cnt[1]++;
		}
	}
}

3. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.LinkedList;
import java.io.OutputStreamWriter;
import java.io.BufferedWriter;

public class Graph_11 {
	static boolean[][] visited;
	static int n;
	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { 1, -1, 0, 0 };
	static int[] cnt = new int[2];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		n = Integer.parseInt(br.readLine());
		char[][] map = new char[n][n];
		char[][] abnormalMap = new char[n][n];
		visited = new boolean[n][n];

		for (int i = 0; i < n; i++) {
			String[] s = br.readLine().split("");
			for (int j = 0; j < n; j++) {
				char tmp = s[j].charAt(0);
				
				if ('G' == tmp) {
					abnormalMap[i][j] = 'R';
					continue;
				}

				abnormalMap[i][j] = tmp;
				map[i][j] = tmp;
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!visited[i][j]) {
					bfs(i, j, map);
					cnt[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, abnormalMap);
					cnt[1]++;
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append(cnt[0]);
		sb.append(" ");
		sb.append(cnt[1]);
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	static void bfs(int x, int y, char[][] map) {
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(x, y));

		while (!q.isEmpty()) {
			Node cur = q.poll();
			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];

				if (nx < 0 || nx >= n || ny < 0 || ny >= n)
					continue;

				if (!visited[nx][ny] && map[nx][ny] == map[cur.x][cur.y]) {
					visited[nx][ny] = true;
					q.add(new Node(nx, ny));
				}

			}
		}
	}

	static class Node {
		int x;
		int y;

		Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

}

4. 결과

성공✨

String equals로 비교시에는 NullpointError가 계속해서 발생한다. 한 자로 이루워져 있으면 되도록이면 char를 쓰는 것이 더 나을 것 같다😥