🧫 문제 분석
✔️ 출처
📖 문제

BFS 혹은 DFS 그래프 탐색 문제이다.
나는 BFS를 좋아해서 BFS로 풀었다.
적록색약은 적록색(R) 과 초록색(G)의 차이를 거의 못느낀다.
따라서 둘중 하나로 통일하면 된다.
나는 문제를 잘못 이해해서
적록색과 초록색의 상화좌우로 인접해 있는 부분만 차이를 못느끼는 줄 알고 문제의 난이도를 더 높여서 풀다가
자꾸 틀리고 이상해서 문제를 다시봤더니 초록색과 적록색 차이가 없다고 보는게 맞았다...(이때문에 시간을 많이 소요함)
이 풀이법도 밑에 올리겠다.
🔅 문제 풀이
import java.io.*;
import java.util.*;
public class Main {
static boolean[][] visited;
static int[] dx = {0, 0, 1, -1};
static int[] dy = {1, -1, 0, 0};
static char[][] rb;
static char[][] color;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
rb = new char[n][n];
color = new char[n][n];
visited = new boolean[n][n];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String s = st.nextToken();
for (int j = 0; j < n; j++) {
char c = s.charAt(j);
color[i][j] = c;
if (c == 'R' || c == 'G') {
rb[i][j] = 'R';
} else {
rb[i][j] = c;
}
}
}
int count = 0;
for (int i = 0; i < rb.length; i++) {
for (int j = 0; j < rb[0].length; j++) {
if (!visited[i][j]) {
bfs(i, j, color[i][j], true);
count++;
}
}
}
bw.write(count +" ");
visited = new boolean[n][n];
count = 0;
for (int i = 0; i < rb.length; i++) {
for (int j = 0; j < rb[0].length; j++) {
if (!visited[i][j]) {
bfs(i, j, rb[i][j], false);
count++;
}
}
}
bw.write(count +"");
bw.flush();
bw.close();
}
private static void bfs(int r, int c, char rgb, boolean check) {
Queue<int[]> q = new LinkedList<>();
q.add(new int[] {r,c});
visited[r][c] = true;
while (!q.isEmpty()) {
int[] poll = q.poll();
for (int i = 0; i < 4; i++) {
int newX = poll[1] + dx[i];
int newY = poll[0] + dy[i];
if (newX < 0 || newX >= rb[0].length ||
newY < 0 || newY >= rb.length || visited[newY][newX]) continue;
if (check) {
if (rgb == color[newY][newX]) {
q.add(new int[]{newY, newX});
visited[newY][newX] = true;
}
} else {
if (rgb == rb[newY][newX]) {
q.add(new int[]{newY, newX});
visited[newY][newX] = true;
}
}
}
}
}
}
🔅 필자가 착각한 문제 풀이
빨간색을 기준으로 상하좌우에 초록색이 있으면 구분하지 못하고, 반대도 마찬가지라고 할때
import java.io.*;
import java.util.*;
public class Main {
static boolean[][] visited;
static int[] dx = {0, 0, 1, -1};
static int[] dy = {1, -1, 0, 0};
static char[][] color;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
color = new char[n][n];
visited = new boolean[n][n];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String s = st.nextToken();
for (int j = 0; j < n; j++) {
char c = s.charAt(j);
color[i][j] = c;
}
}
int count = 0;
for (int i = 0; i < color.length; i++) {
for (int j = 0; j < color[0].length; j++) {
if (!visited[i][j]) {
bfs(i, j, color[i][j]);
count++;
}
}
}
bw.write(count +" ");
visited = new boolean[n][n];
// 빨간색에 인접한 그린은 빨간색으로 바꿈
for (int i = 0; i < color.length; i++) {
for (int j = 0; j < color[0].length; j++) {
if (!visited[i][j] && color[i][j] == 'R') {
bfsRed(i, j);
}
}
}
visited = new boolean[n][n];
count = 0;
for (int i = 0; i < color.length; i++) {
for (int j = 0; j < color[0].length; j++) {
if (!visited[i][j]) {
bfs(i, j, color[i][j]);
count++;
}
}
}
bw.write(count +"");
bw.flush();
bw.close();
}
private static void bfs(int r, int c, char rgb) {
Queue<int[]> q = new LinkedList<>();
q.add(new int[] {r,c});
visited[r][c] = true;
while (!q.isEmpty()) {
int[] poll = q.poll();
for (int i = 0; i < 4; i++) {
int newX = poll[1] + dx[i];
int newY = poll[0] + dy[i];
if (newX < 0 || newX >= color[0].length ||
newY < 0 || newY >= color.length || visited[newY][newX]) continue;
if (rgb == color[newY][newX]) {
q.add(new int[]{newY, newX});
visited[newY][newX] = true;
}
}
}
}
private static void bfsRed(int r, int c) {
Queue<int[]> q = new LinkedList<>();
q.add(new int[] {r,c});
visited[r][c] = true;
while (!q.isEmpty()) {
int[] poll = q.poll();
for (int i = 0; i < 4; i++) {
int newX = poll[1] + dx[i];
int newY = poll[0] + dy[i];
if (newX < 0 || newX >= color[0].length ||
newY < 0 || newY >= color.length || visited[newY][newX]) continue;
if ('G' == color[newY][newX]) {
color[newY][newX] = 'R';
visited[newY][newX] = true;
} else if('R' == color[newY][newX]) {
q.add(new int[]{newY, newX});
visited[newY][newX] = true;
}
}
}
}
}
❗ 오답노트 / 필요한 지식
- 두 개의 배열을 쓸려하니 헷갈려서 이름을 잘못 적는 등의 실수가 있다. 틀렸다면 항상 이부분을 확인하고
- 항상 문제풀때도 정확하게 변수를 쓰자.
'baekjoon > Graph_Search' 카테고리의 다른 글
백준 2206번 : 벽 부수고 이동하기 자바 (0) | 2024.08.22 |
---|---|
백준 1600번 : 말이 되고픈 원숭이 자바 (0) | 2024.08.22 |
백준 번 2023번 : 신기한 소수 자바 (0) | 2024.08.20 |
백준 14500번 : 테트로미노 자바 (0) | 2024.08.19 |
백준 2644번 : 촌수계산 자바 (0) | 2024.08.17 |