[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];
  1. ์ ๋ก์ƒ‰์•ฝ์˜ ๋ฐฐ์—ด์€ 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;
	}
}
  1. 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๋ฅผ ์“ฐ๋Š” ๊ฒƒ์ด ๋” ๋‚˜์„ ๊ฒƒ ๊ฐ™๋‹ค๐Ÿ˜ฅ

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ