[백준] 적록색약

🔗 문제 보기 - [백준] 적록색약

📖 문제

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

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

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

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

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

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

✍ 입력

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

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

📄 출력

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

✅ 코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
  
public class Main {  
    static int[] moveX = {1, -1, 0, 0};  
    static int[] moveY = {0, 0, 1, -1};  
    static String[][] arr;  
    static boolean[][] visited;  
    static int N;  
  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringBuilder sb = new StringBuilder();  
        N = Integer.parseInt(br.readLine());  
        arr = new String[N + 1][N + 1];  
        visited = new boolean[N + 1][N + 1];  
  
        for(int i = 1; i < N+1; i++) {  
            String line = br.readLine();  
            for(int j = 1; j < N+1; j++) {  
                arr[i][j] = String.valueOf(line.charAt(j - 1));  
            }  
        }  
  
        // 적록색약이 아닌사람   
		int count = 0;  
        for(int i = 1; i < N + 1; i++) {  
            for(int j = 1; j < N + 1; j++) {  
                if(!visited[i][j]) {  
                    dfs(i, j);  
                    count++;  
                }  
            }  
        }  
        sb.append(count).append(" ");  
  
        // R값을 전부 G로 변경  
        for(int i = 1; i < N + 1; i++) {  
            for(int j = 1; j < N + 1; j++) {  
                if(arr[i][j].equals("R")) {  
                    arr[i][j] = "G";  
                }  
            }  
        }  
  
        // 입력된 count, visited 값 초기화  
        count = 0;  
        visited = new boolean[N + 1][N + 1];  
  
        // 적록색약인 경우 dfs 시작  
        for(int i = 1; i < N + 1; i++) {  
            for(int j = 1; j < N + 1; j++) {  
                if(!visited[i][j]) {  
                    dfs(i, j);  
                    count++;  
                }  
            }  
        }  
        sb.append(count);  
  
        System.out.println(sb.toString());  
  
    }  
  
    static void dfs(int x, int y) {  
        if(visited[x][y]) return;  
        visited[x][y] = true;  
  
        for(int i = 0; i < 4; i++) {  
            int mx = x + moveX[i];  
            int my = y + moveY[i];  
  
            if(mx > 0 && mx < N + 1 &&  
                    my > 0 && my < N + 1) {  
                // 현재 위치의 색상과 두변 위치의 값이 동일하고 방문하지 않은 경우 dfs 호출  
                if(arr[mx][my].equals(arr[x][y]) && !visited[mx][my]) {  
                    dfs(mx, my);  
                }  
            }  
        }  
    }  
}