✍ 문제

문제링크

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR
적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

👏 풀이과정

dfs를 사용하여 첫번째는 적록색약이 아닌 rgb함수를 사용했고,
두번쨰는 적록색약인 rgb2를 사용하였다.
두번째에는 arr에서 r -> g로 바꾸어 넣어주었다.

package dfs_bfs;

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

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

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

        String[][] arr = new String[N][N];

        for (int i = 0 ; i < N; i++){
            String aa = br.readLine();
            for (int j = 0; j < N; j++) {
                arr[i][j] = aa.substring(j, j + 1);
            }
        }

        boolean[][] visited = new boolean[N][N];
        int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        System.out.print(rgb(N, arr, visited, dir) + " ");

        visited = new boolean[N][N];
        for (int i = 0 ; i < N; i++){
            for (int j = 0; j < N; j++) {
                if (arr[i][j].equals("R")) {
                    arr[i][j] = "G";
                }
            }
        }
        System.out.println(rgb2(N, arr, visited, dir));
    }

    static int rgb(int N, String[][] arr, boolean[][] visited, int[][] dir) {
        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {

                if (visited[i][j] == false) {
                    count++;
                    Queue<Node> queue = new LinkedList<>();

                    queue.add(new Node(i, j, arr[i][j]));
                    while (!queue.isEmpty()) {
                        Node poll = queue.poll();

                        for (int k = 0; k < dir.length; k++) {
                            int x = poll.x + dir[k][0];
                            int y = poll.y + dir[k][1];

                            if (x > -1 && x < N && y > -1 && y < N) {
                                if (visited[x][y] == false && arr[x][y].equals(poll.cost)) {
                                    visited[x][y] = true;
                                    queue.add(new Node(x, y, poll.cost));
                                }
                            }
                        }
                    }
                }
            }
        }
        return count;
    }
    static int rgb2(int N, String[][] arr, boolean[][] visited, int[][] dir){
        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {

                if (visited[i][j] == false) {
                    count++;
                    Queue<Node> queue = new LinkedList<>();

                    queue.add(new Node(i, j, arr[i][j]));
                    while (!queue.isEmpty()) {
                        Node poll = queue.poll();

                        for (int k = 0; k < dir.length; k++) {
                            int x = poll.x + dir[k][0];
                            int y = poll.y + dir[k][1];

                            if (x > -1 && x < N && y > -1 && y < N) {
                                if (visited[x][y] == false && arr[x][y].equals(poll.cost)) {
                                    visited[x][y] = true;
                                    queue.add(new Node(x, y, poll.cost));
                                }
                            }
                        }
                    }
                }
            }
        }
        return count;
    }
    static class Node{
        int x ;
        int y;
        String cost;
        Node(int x,int y, String cost){
            this.x = x;
            this.y = y;
            this.cost = cost;
        }
    }
}