[ 백준 - Java ] 적록색약 ( 자바 )

( dfs / 적록색약 / 10026 )

[문제]

문제 설명

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

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

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

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

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

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

제한사항

메모리 제한 : 128 MB

입출력 예시

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개 줄에는 그림이 주어진다.

 

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

---

[코드]

import java.util.Scanner;

public class RGB10026 {
    static int n;               // 구역크기
    static char[][] map;        // 구역정보를 담을 배열
    static boolean[][] visited; // 방문여부 담을 배열
    // x, y위치 변화에 따른 증감 값
    static final int[] dx = {0, 1, 0, -1};
    static final int[] dy = {-1, 0, 1, 0};

    public static void main(String[] args){
        // === 입력 ===
        Scanner sc = new Scanner(System.in);

        n = Integer.parseInt(sc.nextLine());    // 크기 입력
        map = new char[n][n];                   // 입력받은 크기로 초기화
        visited = new boolean[n][n];            // 입력받은 크기로 초기화
        // 구역정보 입력
        for(int i = 0; i < n; i++) map[i] = sc.nextLine().toCharArray();

        sc.close();

        // === 풀이 ===
        int[] answer = new int[2];     // 색맹이 아닌 사람이 구별한 구역의 개수를 담을 변수
        // 깊이 우선 탐색
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                // 방문하지 않은 구역일 경우 깊이 우선 탐색
                if(!visited[i][j]){
                    dfs(j, i, map[i][j]);   // 깊이 우선 탐색
                    answer[0]++;            // 색맹 아닌 사람이 구별한 영역 카운트 증가
                }
            }
        }
        // 방문여부 초기화
        visited = new boolean[n][n];
        // 모든 G를 R로 변경
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(map[i][j] == 'G') map[i][j] = 'R';
            }
        }
        // 깊이 우선 탐색
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                // 방문하지 않은 구역일 경우 깊이 우선 탐색
                if(!visited[i][j]){
                    dfs(j, i, map[i][j]);   // 깊이 우선 탐색
                    answer[1]++;            // 색맹인 사람이 구별한 영역 카운트 증가
                }
            }
        }

        // === 출력 ===
        for(int i : answer) System.out.print(i + " ");
    }

    // 깊이 우선 탐색
    public static void dfs(int x, int y, char c){
        // 방문했거나 다른색일경우
        if(visited[y][x] || map[y][x] != c) return;
        // 현재 위치 방문처리
        visited[y][x] = true;
        // 4방향 방문 시도
        for(int i = 0; i < 4; i++){
            // 다음 x, y좌표 계산
            int nx = x + dx[i];
            int ny = y + dy[i];
            // 좌표가 범위내 존재 && 방문하지 않음 && 다음 값이 찾고자 하는 값과 일치
            if(nx < n && nx >= 0 && ny < n && ny >= 0 && !visited[ny][nx] && map[ny][nx] == c){
                dfs(nx, ny, c);     // 깊이 우선 탐색
            }
        }
    }
}

문제 링크

10026번: 적록색약

제가 잘못 알고 있거나 잘못된 부분이 있을 경우 알려주시고 추가로 궁금한 점 있으신 분들도 댓글이나 메일 주시면 성실히 답변해 드리겠습니다.🧑🏻‍💻

감사합니다~😄