백준

백준 10026- java

으엉어엉 2024. 10. 31. 15:20
728x90

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BJ10026 {
    static char[][] graph; // 그리드 정보를 담는 2차원 배열
    static boolean[][] visited; // 방문 여부
    static int N; // 그리드 크기
    static int[] dx = { -1, 1, 0, 0 }; // 상하좌우 이동 배열
    static int[] dy = { 0, 0, -1, 1 };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); //배열 크기 선언
        graph = new char[N][N]; //배열 생성

        // 입력하기
        for (int i = 0; i < N; i++) {
            String input = sc.next();
            for (int j = 0; j < N; j++) {
                graph[i][j] = input.charAt(j);
            }
        }

        // 적록색약이 아닌 사람의 구역 수
        visited = new boolean[N][N];
        int normalCount = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j]) {
                    bfs(i, j, graph[i][j], false);
                    normalCount++; //색약 X
                }
            }
        }

        // 적록색약인 사람의 구역 수
        visited = new boolean[N][N];
        int colorBlindCount = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j]) {
                    bfs(i, j, graph[i][j], true);
                    colorBlindCount++; //색약 O
                }
            }
        }

        System.out.println(normalCount + " " + colorBlindCount);
    }

    // BFS 탐색 함수
    public static void bfs(int x, int y, char color, boolean colorBlind) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] { x, y });
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int cx = current[0];
            int cy = current[1];

            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];

                if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[nx][ny]) {
                    if (colorBlind) { // 적록색약인 경우
                        if ((color == 'R' || color == 'G') && (graph[nx][ny] == 'R' || graph[nx][ny] == 'G')) {
                            visited[nx][ny] = true;
                            queue.offer(new int[] { nx, ny });
                        } else if (graph[nx][ny] == color) {
                            visited[nx][ny] = true;
                            queue.offer(new int[] { nx, ny });
                        }
                    } else { // 적록색약이 아닌 경우
                        if (graph[nx][ny] == color) {
                            visited[nx][ny] = true;
                            queue.offer(new int[] { nx, ny });
                        }
                    }
                }
            }
        }
    }
}

 

BFS로 너비우선탐색을 하였으며 ,  색약일경우와 아닐경우로 따로 계산하였다.

728x90

'백준' 카테고리의 다른 글

백준 18111-Java  (0) 2024.11.01
백준 7662 - java  (0) 2024.10.31
백준 11724 - Java  (0) 2024.10.26
백준 21736 - Java  (0) 2024.10.25
백준 2178 - Java  (0) 2024.10.25