[BOJ] 16929번 Two Dots java 풀이

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
  static int n, m;
  static char[][] a;
  static boolean[][] visited;
  static int[][] count;
  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 FileReader("src/INPUT.txt"));
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] s = br.readLine().split(" ");
    n = Integer.parseInt(s[0]);
    m = Integer.parseInt(s[1]);
    a = new char[n][m];
    count = new int[n][m];
    visited = new boolean[n][m];

    for (int i = 0; i < n; i++) {
      char[] c = br.readLine().toCharArray();
      for (int j = 0; j < m; j++) {
        a[i][j] = c[j];
      }
    }

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (traversal(i, j, a[i][j], 1)) {
          System.out.println("Yes");
          return;
        }
      }
    }
    System.out.println("No");
  }

  static boolean traversal(int x, int y, int color, int length) {
    if(visited[x][y]) return length - count[x][y] >= 4;

    visited[x][y] = true;
    count[x][y] = length;
    for (int i = 0; i < 4; i++) {
      int nx = x + dx[i];
      int ny = y + dy[i];
      if (0 <= nx && nx < n && 0 <= ny && ny < m) {
        if (a[nx][ny] == color) {
          if (traversal(nx, ny, color, length + 1)) {
            return true;
          }
        }
      }
    }
    return false;
  }
}

• 이중 포문으로 Dots 배열을 순회하면서 한 점에 대해서 내 주변의 같은 점이 있는지를 DFS 로직을 이용해서 같은 색의 점을 탐색하고, 방문여부 배열을 통해서 방문한 점에 다다르면 시작점과 도달한 점의 인덱스에 해당되는 카운트 배열의 값의 차가 4 이상이면 최소한의 사이클인 4칸짜리 사각형 사이클보다 큰 것으로 보고 true를 리턴하는 로직이다.

• 이 문제를 풀면서 어이없었던 것은 Yes or No를 출력하면 되는 건데 YES NO를 출력해서 자꾸 테스트케이스는 맞는것 처럼 보이는데 틀려서 2시간을 날렸다는 것이다. 풀다가 막히면 꼭 문제를 다시 정독하는 습관을 들이자