[백준] 적록색약 JAVA

반응형

728x90

[백준] 적록색약 - GOLD V 10026번

---

접근

• bfs

---

풀이

Red, Green, Blue 세 가지 색이 주어지는데 일반인의 시선으로 봤을 때 나눠지는 색 구역 개수와 적록색약을 가진 사람이 봤을 때 나눠지는 색 구역 개수를 구하는 문제이다. 대체적으로 실버1~골드5 난이도 구간에는 bfs를 사용하는 문제가 참 많은거 같다. 물론 이 문제도 bfs를 사용한 문제로 이전에 풀었던 단지번호 붙이기 문제의 코드를 인용해 수정하여 풀었다.

2024.09.26 - [알고리즘/코딩테스트-백준] - [백준] 단지번호 붙이기 JAVA

[백준] 단지번호 붙이기 JAVA

코드를 살짝만 수정하여 풀었는데 어려움 없이 한 번에 통과가 되었다.

    private static final int[] dx = {0, 0, -1, 1};
    private static final int[] dy = {1, -1, 0, 0};

    private static class Step {
        private final int x;
        private final int y;

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

이전에 사용했던 클래스와 움직임을 위한 배열은 그대로 사용했다.

	int n = Integer.parseInt(br.readLine());
        String[][] rgb = new String[n][n];
        String[][] redBlue = new String[n][n];

        for (int i = 0; i < n; i++) {
            String[] color = br.readLine().split("");
            for (int j = 0; j < n; j++) {
                rgb[i][j] = color[j];

                if (color[j].equals("G")) {
                    redBlue[i][j] = "R";
                } else {
                    redBlue[i][j] = color[j];
                }
            }
        }

적록색약 배열과 일반인 배열을 따로 만들어 주었다. 적록색약의 경우 초록색을 빨간색으로 바꿔 배열에 매핑해주었다.

	boolean[][] isVisitedRGB = new boolean[n][n];
        boolean[][] isVisitedRedBlue = new boolean[n][n];

        int rgbCount = 0;
        int redBlueCount = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!isVisitedRGB[i][j]) {
                    isVisitedRGB[i][j] = true;
                    countArea(rgb, isVisitedRGB, i, j, n, rgb[i][j]);
                    rgbCount++;
                }

                if (!isVisitedRedBlue[i][j]) {
                    isVisitedRedBlue[i][j] = true;
                    countArea(redBlue, isVisitedRedBlue, i, j, n, redBlue[i][j]);
                    redBlueCount++;
                }
            }
        }

따로 두 배열을 나눈만큼 별개의 연산으로 진행해주었고 방문하지 않은 곳에서 연산이 시작될 때마다 한 개의 구역이 만들어지게 되므로 카운트를 증가시켜주었다.

    private static void countArea(String[][] colors, boolean[][] isVisited, int x, int y, int n, String color) {
        Queue<Step> que = new LinkedList<>();
        que.offer(new Step(x, y));

        while (!que.isEmpty()) {
            Step step = que.poll();

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

                if (nx < 0 || nx >= n || ny < 0 || ny >= n || !colors[nx][ny].equals(color)) {
                    continue;
                }

bfs 메서드로 이전 단지번호 붙이기에서 달라진 부분은 if문 내 조건 하나 밖에 없다. 좌표가 범위 내인지 체크하고 메서드 시작 시 넘겨받았던 색깔을 기준으로 시작 색과 다르다면 넘어가기 때문에 같은 색으로 이루어진 구역만 체크하게 된다.

 		if (isVisited[nx][ny]) {
                    continue;
                }

                que.offer(new Step(nx, ny));
                isVisited[nx][ny] = true;

체크가 끝나면 방문 확인을 하고 큐에 추가하고 끝이난다.

---

전체 코드

import java.io.*;
import java.util.*;

public class Main {
    private static final int[] dx = {0, 0, -1, 1};
    private static final int[] dy = {1, -1, 0, 0};

    private static class Step {
        private final int x;
        private final int y;

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

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

        int n = Integer.parseInt(br.readLine());
        String[][] rgb = new String[n][n];
        String[][] redBlue = new String[n][n];

        for (int i = 0; i < n; i++) {
            String[] color = br.readLine().split("");
            for (int j = 0; j < n; j++) {
                rgb[i][j] = color[j];

                if (color[j].equals("G")) {
                    redBlue[i][j] = "R";
                } else {
                    redBlue[i][j] = color[j];
                }
            }
        }

        boolean[][] isVisitedRGB = new boolean[n][n];
        boolean[][] isVisitedRedBlue = new boolean[n][n];

        int rgbCount = 0;
        int redBlueCount = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!isVisitedRGB[i][j]) {
                    isVisitedRGB[i][j] = true;
                    countArea(rgb, isVisitedRGB, i, j, n, rgb[i][j]);
                    rgbCount++;
                }

                if (!isVisitedRedBlue[i][j]) {
                    isVisitedRedBlue[i][j] = true;
                    countArea(redBlue, isVisitedRedBlue, i, j, n, redBlue[i][j]);
                    redBlueCount++;
                }
            }
        }
        System.out.println(rgbCount +" "+redBlueCount);

        br.close();
    }

    private static void countArea(String[][] colors, boolean[][] isVisited, int x, int y, int n, String color) {
        Queue<Step> que = new LinkedList<>();
        que.offer(new Step(x, y));

        while (!que.isEmpty()) {
            Step step = que.poll();

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

                if (nx < 0 || nx >= n || ny < 0 || ny >= n || !colors[nx][ny].equals(color)) {
                    continue;
                }

                if (isVisited[nx][ny]) {
                    continue;
                }

                que.offer(new Step(nx, ny));
                isVisited[nx][ny] = true;
            }
        }
    }
}