[BOJ] 10026 적록색약 - JAVA

1. 문제

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

10026번: 적록색약

 

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

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

---

2. 풀이

메인

• bfs를 true, false로 나누어 각각 적록색약 아닌 사람, 적록색약인 사람 구역을 계산했다.

static char[][] paints;
static int N;

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

   N = Integer.parseInt(in.readLine());
   paints = new char[N][N];

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

   int rgb = bfs(true);    //적록색약X
   int gb = bfs(false);    //적록색약O

   System.out.println(rgb + " " + gb);

}

 

BFS 탐색

• queue : 다음에 방문할(색이 다른) 시작인덱스 값을 저장한다.
• area : 다음에 색칠할 인덱스 값을 저장한다.
• visited[][] : 방문여부를 저장한다.
• queue에서 뽑은 값이 이미 방문한 적 있다면 반복 처음으로 돌아가 다시 뽑는다.
• 방문한 적 없다면 새 구역을 색칠하기 시작하는 것이다. 구역의 수(cnt)에 +1하고, area에 뽑은 값을 처음값으로 더한다.
• 4방 탐색으로 칠할 수 있는 다음 인덱스들이 있는지 확인한다.
  • 범위를 벗어났거나 방문한 적이 있으면 area에서 다시 뽑는다.
  • 다음 위치의 색과 현 위치의 색이 같거나, 적록색약인경우 R일때 G, G일때 R인 경우 visited에 방문처리하고 area에 값을 넣는다.
  • 위의 경우가 아니라면 queue에 다음에 방문할 시작인덱스값으로 넣어준다.
• 시작인덱스 큐까지 비었다면 지금까지 저장한 cnt(구역 수)값을 리턴한다.

private static int bfs(boolean rgb) {
   int[][] deltas = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
   boolean[][] visited = new boolean[N][N];
   Queue<int[]> queue = new LinkedList<>();   //다음에 방문할 인덱스값
   Queue<int[]> area = new LinkedList<>();       //색칠할 인덱스 값
   int cnt = 0;

   int[] v = {0, 0};
   queue.offer(v);

   while (!queue.isEmpty()) {
      v = queue.poll();
      if (visited[v[0]][v[1]]) continue;    //이미 색칠된 적 있다면 넘어감

      cnt++;                                //구역 추가
      visited[v[0]][v[1]] = true;           //색칠함

      area.offer(v);
      while (!area.isEmpty()) {
         v = area.poll();

         for (int d = 0; d < 4; d++) {
            int ny = v[0] + deltas[d][0];
            int nx = v[1] + deltas[d][1];

            //범위를 벗어났거나 이미 색칠된 적 있다면 넘어감
            if (ny < 0 || ny >= N || nx < 0 || nx >= N || visited[ny][nx]) continue;

            //다음 위치의 색과 현 위치의 색이 같거나, 적록색약인경우(!rgb) R일때 G, G일때 R인 경우
            //색칠하고 area 큐에 값 넣음(이어서 색칠)
            //아니라면 queue에 넣음(새로 색칠)
            if (paints[ny][nx] == paints[v[0]][v[1]]
                  || (!rgb && paints[ny][nx] == 'R' && paints[v[0]][v[1]] == 'G')
                  || (!rgb && paints[ny][nx] == 'G' && paints[v[0]][v[1]] == 'R')) {
               visited[ny][nx] = true;
               area.offer(new int[]{ny, nx});
            } else queue.offer(new int[]{ny, nx});
         }
      }
   }

   return cnt;
}

---

3. 결과

꼭 큐를 두개 써야했을까? 우선순위 큐를 여기도 활용할 수 있지 않았을까? 하는 생각이 든다.