[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. ํต์ฌ ํ์ด
- ์ ์์ธ๊ณผ ์ ๋ก์์ฝ์ด ๋ณด๋ ๋ฐฐ์ด์ ๋ฐ๋ก ๋ง๋ฆ
char[][] map = new char[n][n];
char[][] abnormalMap = new char[n][n];
- ์ ๋ก์์ฝ์ ๋ฐฐ์ด์ 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;
}
}
- 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๋ฅผ ์ฐ๋ ๊ฒ์ด ๋ ๋์ ๊ฒ ๊ฐ๋ค๐ฅ
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ([Algorithm] ๐๏ธ๋ฐฑ์ค 10026 ์ ๋ก์์ฝ), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@kha0318/Algorithm-๋ฐฑ์ค-10026-์ ๋ก์์ฝ์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค