[백준 16929] Two Dots

문제

각각의 칸은 색이 칠해진 공이 하나씩 있다. 이 게임의 핵심은 같은 색으로 이루어진 사이클을 찾는 것이다.

다음은 위의 게임판에서 만들 수 있는 사이클의 예시이다.

점 k개 d1, d2, ..., dk로 이루어진 사이클의 정의는 아래와 같다.

• 모든 k개의 점은 서로 다르다. 
• k는 4보다 크거나 같다.
• 모든 점의 색은 같다.
• 모든 1 ≤ i ≤ k-1에 대해서, di와 di+1은 인접하다. 또, dk와 d1도 인접해야 한다. 두 점이 인접하다는 것은 각각의 점이 들어있는 칸이 변을 공유한다는 의미이다.

게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구해보자.

---

풀이

문제는 같은 색의 점으로 싸이클이 만들어지는지 가능 유무만 판단하면 된다

처음 문제를 봤을 땐 대각선도 싸이클 결정에 관여하는지 헷갈렸는데 사이클의 정의를 보면 상하좌우로 인접한 점들만 사이클 결정에 관여한다

 

사이클의 존재하는지만 판단하면 되기에 dfs로 접근하면 금방 풀 수 있겠다고 생각했다

  static int N,M,depth;
  static String res;
  static char[][] pad;
  static boolean[][] visit;
  static int[] moveX = {-1,0,0,1};
  static int[] moveY = {0,-1,1,0};

 

변수로 패드의 넓이를 담을 N, M와 결과메세지를 저장할 res, 알파벳으로 주어지는 점의 색을 저장할 pad

깊이우선탐색을 할 때 사용할 depth와 visit, 상하좌우로 인접한 점을 체크하기 위한 X,Y 좌표들을 사용했다

 

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    pad = new char[N][M];
    res = "No";

    for (int i = 0; i < N; i++) {
      String line = br.readLine();
      for (int j = 0; j < M; j++) {
        pad[i][j] = line.charAt(j);
      }
    }

 

입력값은 위와 같이 받고

 

    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        visit = new boolean[N][M];
        visit[i][j] = true;
        searchCycleDfs(new int[]{i,j},i,j);
      }
    }
    System.out.println(res);

 

N*M의 패드 위에 점들 하나하나를 시작점으로 설정하여 시작점으로 돌아오는 사이클이 존재하는지 검사하였다

 

문제는 searchCycleDfs 메소드인데 쉽게 생각했다가 depth초기화에 꽤 많은 시간 고민했다

visit변수에 방문여부를 저장하여 방문한 점을 다시 방문하지 않도록 했는데, 시작점에서부터 인접한 점을 dfs로 탐색하는 과정에서 (사이클을 만들고 depth가 4 이상인 상태로 시작점으로 돌아온 것인지 vs 시작점에서 인접한 점을 방문하고 곧바로 시작점으로 돌아온 것인지) 구분하는데 30분 넘게 고민한 것 같다

    int roadBlock = 0;
    for (int i = 0; i < 4; i++) {
      int nextX = x + moveX[i];
      int nextY = y + moveY[i];
      if (start[0] == nextY && start[1] == nextX && depth >= 3) {
        res = "Yes";
        return;
      }
      if (0 <= nextX && nextX < M && 0 <= nextY && nextY < N && !visit[nextY][nextX] && pad[y][x] == pad[nextY][nextX]) {
        visit[y][x] = true;
        depth++;
        searchCycleDfs(start,nextY,nextX);
      } else {
        roadBlock++;
      }
      if (roadBlock==4) {
        depth = 0;
      }
    }

 

결국 생각해낸 방법은 메소드의 로컬변수로 roadBlock을 선언하고 해당 메소드가 가리키고 있는 점의 위치에서 상하좌우 어디에도 나아갈 길이 없을 때, 즉 깊이우선탐색을 하는 과정에서 더이상 길이 없어서 호출한 메소드로 반환할 때 depth를 0으로 초기화하여 깊이를 판단하고 그 깊이로 사이클의 존재를 결정했다.

 

사실 길이 막혀 반환되는 과정에서 다른 길로 탐색을 시작하면 내 알고리즘의 반례가 존재할것이라 생각했다

하지만 사이클의 존재를 판단할 때 depth를 4가 아닌 3으로 설정하여 반례가 사라진 것 같기도 하다

 

 

문제를 푸는 과정에서 내가 했던 고민들을 글로 쉽게 풀어 설명하기가 참 힘든 것 같다