백준 10026번: 적록색약

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

 

스스로 해보려고 했는데, 너무 오래 걸려서 다른 사람의 코드를 보며 풀었다.

 

맨 처음에는 같은 색으로 이어져 있는 조각을 탐색하고,

그 조각과 붙어있는 다른 색들을  큐에 넣은 다음에

탐색하지 않은 것들을 큐에서 꺼내서 탐색하게 끔 했는데 메모리 초과가 났다.

 

내가 찾아본 코드에선 간순하게 N * N의 크기를 탐색하게 한 것을 보고

내가 너무 복잡하게 생각하지 않았나 생각이 들었다.

 

일단, DFS로 풀면서 색약인 경우와 그렇지 않은 경우 두번으로 나눠서 탐색을 했으며,

정상인 경우일 때, DFS를 돌린 뒤에 G를 미리 R로 바꿔주었다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
//import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
  static int N;
  static char[][] table;
  static boolean[][] visited;
  static int[] dx = {-1, 0, 0, 1};
  static int[] dy = {0, -1, 1, 0};
  
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    table = new char[N + 2][N + 2];
    visited = new boolean[N + 2][N + 2];

    for (int x = 1; x < N + 1; x++) {
      String str = br.readLine();
      for (int y = 1; y < N + 1; y++) {
        table[x][y] = str.charAt(y - 1);
      }
    }

    int nm = 0;
    for (int x = 1; x < N + 1; x++) {
      for (int y = 1; y < N + 1; y++) {
        if ( !visited[x][y] ) nm += DFS(x, y);
        if ( table[x][y] == 'G' ) table[x][y] = 'R';
      }
    }

    visited = new boolean[N + 2][N + 2];

    int cw = 0;
    for (int x = 1; x < N + 1;  x++) {
      for (int y = 1; y < N + 1; y++) {
        if ( !visited[x][y] ) cw += DFS(x, y);
      }
    }

    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    bw.write(nm + " " + cw);
    bw.flush();
    bw.close();
  }

  static int DFS(int x, int y) {
    visited[x][y] = true;
    char nowColor = table[x][y];
    for (int i = 0; i < 4; i++) {
      int X = x + dx[i];
      int Y = y + dy[i];

      if ( X < 0 || Y < 0 || X > N || Y > N ) continue;

      if (nowColor == table[X][Y] && !visited[X][Y]) DFS(X, Y);
    }
    return 1;
  }
}