백준 10026번 : 적록색약 자바

🧫 문제 분석

 

✔️ 출처

적록색약 골드 5

 

📖 문제

 

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;
                }
            }
        }

    }

    
}

❗ 오답노트 / 필요한 지식

1.  두 개의 배열을 쓸려하니 헷갈려서 이름을 잘못 적는 등의 실수가 있다.  틀렸다면 항상 이부분을 확인하고
2. 항상 문제풀때도 정확하게 변수를 쓰자.