[백준] 10026번 : 적록색약 – JAVA [자바]

 

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

10026번: 적록색약

 

---

• 문제

 

 

---

• 풀이 방법

이 문제는 전형적인 그래프 문제이다. 조금 더 많은 그래프의 정보를 원한다면 밑에 있는 링크를 참고하면 되겠다.

https://propercoding.tistory.com/entry/자료구조-그래프 Graph

[자료구조] 그래프(Graph)

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못하는 사람을 뜻한다. 그래서 나는 이 문제에서 그래프를 2개를 만들었다. 그래프 1은 평범한 사람이 보는 그림, 그리고 그래프 2는 적록색약인 사람이 보는 그림으로 만들었다. 적록색약인 것을 어떻게 구현했냐 하면 빨간색(R)과 초록색(G)과 같으므로 G로 들어오는 값을 R로 기록해놨다. 이 문제에서 주어진 예제로 예를 들어보겠다.

 

예제 입력

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

 

그래프 1은 주어진 예제랑 같다.

그래프 1

 

따라서 그래프 1에서도 볼 수 있듯이 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 

하지만 적록색약인 사람한테는 R과 G과 같으므로 G를 R로 표현했다. 

그래프 2

따라서 적록색약인 사람은 3개의 구역을 볼 수 있다. (빨강 2, 파랑 1)

 

이렇게 두 개의 그래프 (2차원 배열)을 만들어서 BFS나 DFS를 돌려주면 구역의 개수를 구할 수 있다.

---

 

• 풀이

 

import java.io.*;
import java.util.*;
public class Main {
  static char[][] graph1;
  static char[][] graph2;
  static boolean[][] visited;
  static int count;
  static int n;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());
    StringBuilder sb = new StringBuilder();
    graph1 = new char[n+2][n+2];
    graph2 = new char[n+2][n+2];
    visited = new boolean[n+2][n+2];
    String s;
    for (int i = 1; i <= n; i++) {
      s = br.readLine();
      for (int j = 1; j <= n; j++) {
        graph1[i][j] = s.charAt(j-1);
        if (graph1[i][j] == 'G') {
          graph2[i][j] = 'R';
        } else {
          graph2[i][j] = graph1[i][j];
        }

      }
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (!visited[i][j]) {
          visited[i][j] = true;
          count++;
          dfs1(i,j);
        }
      }
    }
    sb.append(count + " ");
    count = 0;
    visited = new boolean[n+2][n+2];
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (!visited[i][j]) {
          visited[i][j] = true;
          count++;
          dfs2(i,j);
        }
      }
    }
    sb.append(count);
    System.out.print(sb);
  }

  static void dfs1(int x, int y) {
    visited[x][y] = true;
    if (!visited[x-1][y] && graph1[x-1][y] == graph1[x][y]) dfs1(x-1,y);
    if (!visited[x+1][y] && graph1[x+1][y] == graph1[x][y]) dfs1(x+1,y);
    if (!visited[x][y-1] && graph1[x][y-1] == graph1[x][y]) dfs1(x,y-1);
    if (!visited[x][y+1] && graph1[x][y+1] == graph1[x][y]) dfs1(x,y+1);
  }

  static void dfs2(int x, int y) {
    visited[x][y] = true;
    if (!visited[x-1][y] && graph2[x-1][y] == graph2[x][y]) dfs2(x-1,y);
    if (!visited[x+1][y] && graph2[x+1][y] == graph2[x][y]) dfs2(x+1,y);
    if (!visited[x][y-1] && graph2[x][y-1] == graph2[x][y]) dfs2(x,y-1);
    if (!visited[x][y+1] && graph2[x][y+1] == graph2[x][y]) dfs2(x,y+1);
  }
}

 

 

 

---

 

• 후기

이 문제는 골드 5 문제치고는 그렇게 어렵지 않았다. 개인적인 경험을 말하자면 다른 골드 5 문제라도 아직은 어려운 문제가 많은데 이 문제는 괜찮게 다가왔다. 물론 사람마다 다 다르긴 하겠지만 BFS나 DFS 이론을 알고 있는 사람한테는 충분히 쉽게 풀 수 있는 문제였지 않았나 싶다. 아직 나는 갈 길이 먼 거 같다.