[BFS] BOJ 10026번, 적록 색약(JAVA)

---

문제풀이

 

다른 BFS 문제와 비슷하게 R, G, B가 각각 연속적으로 이어진 영역의 개수를 구해주면된다.

 

적록색약인 사람은 R과 G가 똑같이 보이므로 BFS를 돌리기전에 배열의 R => G 로 변경해주었다.

 

이 방법 말고도 BFS안에서 현재 색이 R이거나 G일때를 확인해서 돌려도 괜찮을것같다.

 

---

소스코드

import java.util.*;
import java.io.*;
class Main{
    static int n;
    static char[][] arr;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int[] ans = new int[2];
    static boolean[][] visited;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        
        n = Integer.parseInt(br.readLine());
        arr = new char[n][n];
        visited = new boolean[n][n];
        
        for(int i=0;i<n;i++)
        {
            String input = br.readLine();
            for(int j=0;j<n;j++)
            {
                arr[i][j] = input.charAt(j);
            }
        }
        
        //적록색약 아닌 사람
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(!visited[i][j])
                {
                    bfs(i,j, arr[i][j]);
                    ans[0]++;
                }
            }
        }
        
        //배열 적록색약으로 바꾸기 R -> G
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(arr[i][j] == 'R')
                {
                    arr[i][j] = 'G';
                }
            }
        }
        visited = new boolean[n][n];
        //적록색약인 사람
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(!visited[i][j])
                {
                    bfs(i,j, arr[i][j]);
                    ans[1]++;
                }
            }
        }
        System.out.println(ans[0] + " " + ans[1]);
    }
    public static void bfs(int y, int x, char color)
    {
        Queue<Pos> q = new LinkedList<>();
        q.add(new Pos(y,x));
        visited[y][x] = true;
        
        while(!q.isEmpty())
        {
            Pos p = q.poll();
            for(int i=0;i<4;i++)
            {
                int ny = p.y + dy[i];
                int nx = p.x + dx[i];
                
                if(ny>=0 && nx>=0 && nx<n && ny<n)
                {
                    if(!visited[ny][nx] && arr[ny][nx] == color)
                    {
                        visited[ny][nx] = true;
                        q.add(new Pos(ny,nx));
                    }
                }
            }
        }
    }
}
class Pos{
    int y,x;
    public Pos(int y, int x)
    {
        this.y = y;
        this.x = x;
    }
}

https://www.acmicpc.net/problem/10026

10026번: 적록색약