[백준][자바] 10026 - 적록색약 - BFS(완전탐색)

📌 문제

백준 | 적록색약 | GOLD 5 | 완전탐색

https://www.acmicpc.net/problem/10026

 

 

 

📌 문제 탐색하기

• N*N크기의 그리드
  • R, G, B 가 그리드에 존재
  • 구역이 나뉘어 있고, 같은 색으로 있음
  • 같은 색상이 상하좌우로 인접 ⇒ 두 글자는 같은 구역에 속함
• 적록색약 = 빨간색과 초록색의 차이를 거의 느끼지 못함 (빨강과 초록을 하나로 보는 것)

example)

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약 x = 4구역

적록색약 o = 3구역

 

출력 : 적록색약 아닌 사람이 본 구역의 수, 적록색약인 사람이 본 구역의 수

 

 

 

📌 알고리즘

• 적록색약 및 적록색약 x 사람이 보는 색의 구역을 모두 확인해야하므로, ‘BFS’ 완전탐색을 사용한다.
• N이 100이하이므로, 2차배열을 사용하는 BFS에서 100 ^ 2 ≤ 1초 로 BFS 알고리즘이 사용 가능하다.

 

📌 코드 설계하기

1. N, 그리드 입력
2. 완전탐색 BFS 코드 구현
   1. 코드 구현은 여느 BFS 문제나 같음 BUT, canGo메소드의 차이 존재

 

 

📌 시도 회차 수정

1회차

• 적록색약 grid를 g 제외하고 나머지일 경우, 똑같이 grid에 입력받도록 해야하는데, 이부분을 제외시켰다.

📌 수정 후, 정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

        String[][] gridDiff = new String[n][n]; //적록색약 x
        String[][] gridDiffNo = new String[n][n]; //적록색약 o
        int[][] visited = new int[n][n];
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < n; j++) {
                String color = String.valueOf(line.charAt(j));
                gridDiff[i][j] = color;
                if (color.equals("G")) {
                    gridDiffNo[i][j] = "R";
                } else {
                    gridDiffNo[i][j] = color;
                }
            }
        }

        String[] color = {"R", "G", "B"};
        int redGreenDiff = 0; //적록색약 x
        for (String c : color) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (gridDiff[i][j].equals(c) && visited[i][j] == 0) {
                        bfs(i, j, gridDiff, visited);
                        redGreenDiff++;
                    }
                }
            }
        }

        color = new String[]{"R", "B"};
        visited = new int[n][n];
        int redGreenSame = 0; //적록색약 o
        for (String c : color) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (gridDiffNo[i][j].equals(c) && visited[i][j] == 0) {
                        bfs(i, j, gridDiffNo, visited);
                        redGreenSame++;
                    }
                }
            }
        }


        System.out.print(redGreenDiff + " " + redGreenSame);


    }

    public static void bfs(int x, int y, String[][] grid, int[][] visited) {
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        Queue<GridPoint> queue = new LinkedList<>();
        queue.offer(new GridPoint(x, y));
        visited[x][y] = 1;

        while (!queue.isEmpty()) {
            GridPoint cur = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                if (canGo(nx, ny, grid, visited, grid[cur.x][cur.y])) {
                    queue.offer(new GridPoint(nx, ny));
                    visited[nx][ny] = 1;
                }
            }
        }
    }

    public static boolean canGo(int x, int y, String[][] grid, int[][] visited, String color) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) {
            return false;
        } else if (visited[x][y] == 1 || !grid[x][y].equals(color)) {
            return false;
        }
        return true;
    }

}

class GridPoint {
    int x;
    int y;

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

 

 

GOLD 5여서 처음엔 조금 두려웠지만, 어쨌든 BFS 문제는 정형화되어있어서 풀이가 상대적으로 쉬웠다. 

다만, 시간 복잡도 면에서 적록색약 유무의 코드를 병합시키는 리팩토링이 필요할 듯 하다.