백준-10026번/적록색약 (java)

 

문제 이해

위 표와 같이 RGB로 구성된 그래프에서 색깔별 구역의 갯수를 구해주면 된다. 

단, 적록색약의 경우 R과 G를 구분하지 않고 구역의 수를 구해준다.

구역의 갯수를 구해주면 되므로 연결성분의 수를 구해줄때와 마찬가지로 BFS로 구현해봤다.

문제 해결

 

BFS구현

public static void bfs(int x, int y, char c){
    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[]{x, y});
    visit[x][y] = true;

    while(!queue.isEmpty()){
        int[] point = queue.poll();

        int pointX = point[0];
        int pointY = point[1];

        for(int i = 0; i < 4; i++){
            int nextX = pointX + dx[i];
            int nextY = pointY + dy[i];
            if(nextX < 0 || nextY < 0 || nextX >= N || nextY >= N){
                continue;
            }
            if(visit[nextX][nextY] || arr[nextX][nextY] != c){
                continue;
            }

            queue.add(new int[]{nextX, nextY});
            visit[nextX][nextY] = true;
        }
    }
}

입력받은 색과 같은 색의 경우에만 다음칸으로 이동한다.

이동한 뒤에는 visit값을 true로 바꿔줘서 반복 방문을 방지한다.

 

 

<전체 코드>

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

public class Problem10026 {

    static char[][] arr;
    static int N;
    static boolean[][] visit;
    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));
        N = Integer.parseInt(br.readLine());
        arr = new char[N][N];
        visit = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            arr[i] = br.readLine().toCharArray();
        }

        int count1 = 0;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(!visit[i][j]){
                    bfs(i, j, arr[i][j]);
                    count1++;
                }
                if(arr[i][j] == 'G'){
                    arr[i][j] = 'R';
                }
            }
        }

        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                visit[i][j] = false;
            }
        }

        int count2 = 0;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(!visit[i][j]){
                    bfs(i, j, arr[i][j]);
                    count2++;
                }
            }
        }

        System.out.println(count1 + " " + count2);
    }

    public static void bfs(int x, int y, char c){
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});
        visit[x][y] = true;

        while(!queue.isEmpty()){
            int[] point = queue.poll();

            int pointX = point[0];
            int pointY = point[1];

            for(int i = 0; i < 4; i++){
                int nextX = pointX + dx[i];
                int nextY = pointY + dy[i];
                if(nextX < 0 || nextY < 0 || nextX >= N || nextY >= N){
                    continue;
                }
                if(visit[nextX][nextY] || arr[nextX][nextY] != c){
                    continue;
                }

                queue.add(new int[]{nextX, nextY});
                visit[nextX][nextY] = true;
            }
        }
    }
}