All :L

[BOJ/Java] 적록색약 (10026) 본문

CODING/BOJ

[BOJ/Java] 적록색약 (10026)

ofijwe 2024. 8. 25. 23:55
반응형

적록색약 (10026)

1. 문제 분석

문제 개요

  • 입력으로 주어진 N x N 크기의 격자에서 색깔에 따라 구역의 개수를 계산한다.
  • 색약이 없는 사람과 색약이 있는 사람의 구역 개수를 각각 계산한다.
  • 색약이 있는 사람은 빨강(R)과 초록(G)을 동일하게 인식한다.

입력 형식

  • 첫 줄에 격자의 크기 N이 주어진다.
  • 다음 N줄에는 R, G, B로 이루어진 N x N 격자가 주어진다.

출력 형식

  • 첫째 줄에 색약이 없는 사람의 구역 개수와 색약이 있는 사람의 구역 개수를 공백으로 구분하여 출력한다.

2. 알고리즘 종류

이 문제는 "그래프 탐색(DFS)" 문제이다. 각 지점을 시작으로 연결된 같은 색깔의 모든 지점을 탐색하여 구역을 구분하고, 그 개수를 계산한다.

3. 주요 부분 및 코드 작성 방법

1. 방향 벡터 설정

  • 상하좌우 방향으로 이동하기 위한 방향 배열 dx와 dy를 설정한다.

2. 배열 초기화

  • grid 배열은 입력된 그림 정보를 저장하고, visited 배열은 방문 여부를 추적한다.

3. DFS 함수 구현

  • 현재 지점에서 시작해 상하좌우로 이동하며 연결된 색깔을 탐색한다.
  • 색약이 없는 사람의 경우 R, G, B를 각각 구분하여 구역을 계산한다.
  • 색약이 있는 사람의 경우 R과 G를 동일한 색으로 취급하여 구역을 계산한다.

4. 결과 출력

  • 색약이 없는 사람과 색약이 있는 사람 각각의 구역 개수를 출력한다.

4. 코드 설명

색약이 없는 사람의 DFS 함수 (notRGBlind)

public static void notRGBlind(int x, int y, String color) {
    visited[x][y] = true; // 현재 위치 방문 처리
    for (int i = 0; i < 4; i++) { // 4방향으로 탐색
        int nx = x + dx[i]; // 새로운 x 좌표
        int ny = y + dy[i]; // 새로운 y 좌표
        // 범위를 벗어나거나 이미 방문한 위치는 건너뜀
        if (nx < 0 || ny < 0 || nx >= N || ny >= N || visited[nx][ny]) continue;
        if (grid[nx][ny].equals(color)) { // 동일한 색깔이 연결된 경우
            cnt++; // 구역 내 크기 증가
            visited[nx][ny] = true; // 새로운 위치 방문 처리
            notRGBlind(nx, ny, color); // 재귀적으로 탐색
        }
    }
}
  • 현재 위치에서 시작해 상하좌우로 탐색하면서 동일한 색깔의 영역을 재귀적으로 방문한다.
  • 구역 내 크기를 cnt로 계산한다.

색약이 있는 사람의 DFS 함수 (RGBlind)

public static void RGBlind(int x, int y, String color) {
    visited[x][y] = true; // 현재 위치 방문 처리
    for (int i = 0; i < 4; i++) { // 4방향으로 탐색
        int nx = x + dx[i]; // 새로운 x 좌표
        int ny = y + dy[i]; // 새로운 y 좌표
        // 범위를 벗어나거나 이미 방문한 위치는 건너뜀
        if (nx < 0 || ny < 0 || nx >= N || ny >= N || visited[nx][ny]) continue;
        if (color.equals("R") || color.equals("G")) { // 색약인 경우 R과 G를 동일하게 인식
            if (grid[nx][ny].equals("R") || grid[nx][ny].equals("G")) {
                cnt++;
                visited[nx][ny] = true;
                RGBlind(nx, ny, color); // 재귀적으로 탐색
            }
        } else { // 색약이 아닌 경우 B
            if (grid[nx][ny].equals(color)) {
                cnt++;
                visited[nx][ny] = true;
                RGBlind(nx, ny, color); // 재귀적으로 탐색
            }
        }
    }
}
  • 색약인 경우 R과 G를 동일하게 인식하여 연결된 영역을 탐색한다.
  • B는 색약 여부와 관계없이 처리한다.

메인 함수 (main)

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()); // grid의 크기 입력
    grid = new String[N][N]; // grid 배열 초기화
    visited = new boolean[N][N]; // 방문 체크 배열 초기화
    List<Integer> answer = new ArrayList<>(); // 구역의 크기를 저장할 리스트

    // grid 정보 입력 받기
    for (int i = 0; i < N; i++) grid[i] = br.readLine().split("");

    // 색약이 없는 사람의 구역 계산
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cnt = 1; // 구역 내 크기 초기화
            if (!visited[i][j]) { // 방문하지 않은 위치 발견 시
                notRGBlind(i, j, grid[i][j]); // DFS 실행
                answer.add(cnt); // 구역 내 크기 저장
            }
        }
    }
    sb.append(answer.size()).append(" "); // 구역 수 저장

    // 색약인 사람의 구역 계산
    answer.clear(); // 리스트 초기화
    visited = new boolean[N][N]; // 방문 체크 배열 초기화
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cnt = 1; // 구역 내 크기 초기화
            if (!visited[i][j]) { // 방문하지 않은 위치 발견 시
                RGBlind(i, j, grid[i][j]); // DFS 실행
                answer.add(cnt); // 구역 내 크기 저장
            }
        }
    }
    sb.append(answer.size()); // 구역 수 저장
    System.out.println(sb); // 결과 출력
}
  • 입력을 받아 grid를 초기화하고, 각 지점을 탐색하여 새로운 구역을 찾을 때마다 DFS를 수행한다.
  • 색약이 없는 사람과 색약이 있는 사람 각각의 구역 수를 계산하여 출력한다.

5. 전체 코드

package BOJ.BOJ10026_240824;

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

public class Main {
    static int N, cnt; // grid 크기와 구역 내 크기
    static String[][] grid; // grid 배열
    static boolean[][] visited; // 방문 체크 배열
    // 상하좌우 탐색을 위한 방향 벡터
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    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()); // grid의 크기 입력
        grid = new String[N][N]; // grid 배열 초기화
        visited = new boolean[N][N]; // 방문 체크 배열 초기화
        List<Integer> answer = new ArrayList<>(); // 구역의 크기를 저장할 리스트

        // grid 정보 입력 받기
        for(int i = 0; i < N; i++) grid[i] = br.readLine().split("");

        // 색약이 아닌 사람의 구역 계산
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                cnt = 1; // 구역 내 크기 초기화
                if(!visited[i][j]) { // 방문하지 않은 위치 발견 시
                    notRGBlind(i, j, grid[i][j]); // DFS 실행
                    answer.add(cnt); // 구역 내 크기 저장
                }
            }
        }
        sb.append(answer.size()).append(" "); // 구역 수 저장

        // 색약인 사람의 구역 계산
        answer.clear(); // 리스트 초기화
        visited = new boolean[N][N]; // 방문 체크 배열 초기화
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                cnt = 1; // 구역 내 크기 초기화
                if(!visited[i][j]) { // 방문하지 않은 위치 발견 시
                    RGBlind(i, j, grid[i][j]); // DFS 실행
                    answer.add(cnt); // 구역 내 크기 저장
                }
            }
        }
        sb.append(answer.size()); // 구역 수 저장
        System.out.println(sb); // 결과 출력
    }

    // 색약이 아닌 사람을 위한 DFS
    public static void notRGBlind(int x, int y, String color) {
        visited[x][y] = true; // 현재 위치 방문 처리
        for(int i = 0; i < 4; i++) { // 4방향으로 탐색
            int nx = x + dx[i]; // 새로운 x 좌표
            int ny = y + dy[i]; // 새로운 y 좌표
            // 범위를 벗어나거나 이미 방문했으면 건너뜀
            if(nx < 0 || ny < 0 || nx >= N || ny >= N || visited[nx][ny]) continue;
            if(grid[nx][ny].equals(color)) { // 동일한 색깔이 연결되어 있으면
                cnt++; // 구역 내 크기 증가
                visited[nx][ny] = true; // 새로운 위치 방문 처리
                notRGBlind(nx, ny, color); // 재귀적으로 탐색
            }
        }
    }

    // 색약인 사람을 위한 DFS
    public static void RGBlind(int x, int y, String color) {
        visited[x][y] = true; // 현재 위치 방문 처리
        for(int i = 0; i < 4; i++) { // 4방향으로 탐색
            int nx = x + dx[i]; // 새로운 x 좌표
            int ny = y + dy[i]; // 새로운 y 좌표
            // 범위를 벗어나거나 이미 방문했으면 건너뜀
            if(nx < 0 || ny < 0 || nx >= N || ny >= N || visited[nx][ny]) continue;
            if(color.equals("R") || color.equals("G")) { // 색약은 R과 G를 동일하게 인식
                if(grid[nx][ny].equals("R") || grid[nx][ny].equals("G")) {
                    cnt++;
                    visited[nx][ny] = true;
                    RGBlind(nx, ny, color); // 재귀적으로 탐색
                }
            } else {
                if(grid[nx][ny].equals(color)) { // B의 경우는 색약 여부와 관계없이 동일
                    cnt++;
                    visited[nx][ny] = true;
                    RGBlind(nx, ny, color); // 재귀적으로 탐색
                }
            }
        }
    }
}
반응형

'CODING > BOJ' 카테고리의 다른 글

[BOJ/Java] 스택 (10828)  (0) 2024.08.26
[BOJ/Java] 알파벳 (1987)  (0) 2024.08.26
[BOJ/Java] 도키도키 간식드리미 (12789)  (0) 2024.08.25
[BOJ/Java] 비밀번호 찾기 (17219)  (0) 2024.08.25
[BOJ/Java] 단지번호붙이기 (2667)  (0) 2024.08.24
'CODING/BOJ' Related Articles more
Comments