백준 9874번: Wormholes (Java)

접근

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

9874번: Wormholes

문제해석: 농부 존이 무언가 실험을 해서 농장에 12개 이하 짝수의 웜홀이 생성되었습니다. 이 웜홀들은 서로 연결될 수 있습니다. 소는 x 방향으로만 이동할 수 있습니다. 웜홀의 갯수와 위치가 주어졌을 때, 소가 웜홀에 붙잡힐 수 있는 웜홀 연결 경우의 수를 구하는 문제입니다. 붙잡힌다는 뜻은 소가 어떤 위치에서 출발하여 x방향으로만 계속 이동하는데, 웜홀에 의해 농장 밖으로 나가지 못하고 영원히 같은 자리를 멤도는 상황을 뜻합니다.

처음에는 map을 그려놓고 소가 이동하는 것을 bfs와 같은 방식으로 풀이하려 하였으나, 웜홀의 좌표 범위가 매우 커 메모리 초과를 얻게 되었습니다. 따라서 이런 식으로 map을 그리는 것이 아니라 좌표 기준으로 소의 움직임을 이동하게 하는 것이 중요합니다.

visited 배열은 웜홀의 수만큼 초기화하여 웜홀에 소가 도달할 경우를 체크해줍니다. 소가 농장을 빠져나가지 못하고 계속 같은 자리를 멤돌기 위해서는 같은 웜홀에 계속 방문해야만 합니다. 따라서 소가 계속 이동하는데 같은 웜홀을 방문(visited 가 true 인 웜홀을 다시 방문)할 경우 멤돈다고 판단하고 카운트해줍니다.

소의 위치에서 다음으로 이동할 수 있는 웜홀이 없을 경우, 농장 바깥으로 나갔다고 판단하고 탐색을 종료합니다.

웜홀의 연결은 dfs 탐색을 통해 모든 연결의 경우의 수를 체크해주었습니다.

코드

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

public class Main {

  static int N, R, C, ans;
  static Node[] wormhole;
  static int[] linked;
  static int[][] map;

  static class Node {

    private int r, c;

    public Node(int r, int c) {
      this.r = r;
      this.c = c;
    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    wormhole = new Node[N + 1];
    linked = new int[N + 1];
    for (int i = 1; i <= N; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      int r, c;
      r = Integer.parseInt(st.nextToken());
      c = Integer.parseInt(st.nextToken());
      wormhole[i] = new Node(r, c);
      R = Math.max(R, r);
      C = Math.max(C, c);
    }
    br.close();
    dfs(0);
    System.out.println(ans);
  }

  // 웜홀의 연결 경우를 탐색하는 함수, linked[a] = b 일 경우 a 웜홀과 b 웜홀이 연결된 것
  static void dfs(int n) {
    if (n == N / 2) {
      // 모든 웜홀이 연결되었을 경우, 해당 경우에서 소가 멤도는지를 확인하여 카운트
      if (isCycling()) ans++;
      return;
    }
    // 1번 웜홀부터 시작하여, 아직 연결되지 않은 웜홀 탐색
    int link1 = 1;
    while (linked[link1] != 0) link1++;
    // link1 웜홀과 연결할 다음 웜홀 탐색
    for (int link2 = link1 + 1; link2 <= N; link2++) {
      if (linked[link2] != 0) continue;
      linked[link1] = link2;
      linked[link2] = link1;
      dfs(n + 1);
      linked[link1] = 0;
      linked[link2] = 0;
    }
  }

  static boolean isCycling() {
    // 모든 웜홀의 위치를 소의 시작점으로 탐색한다
    for (int t = 1; t <= N; t++) {
      LinkedList<Integer> queue = new LinkedList<>();
      boolean[] visited = new boolean[N + 1];
      queue.add(t);
      visited[t] = true;
      while (!queue.isEmpty()) {
        int now = queue.poll();
        int nowr = wormhole[now].r;
        int nowc = wormhole[now].c;
        // 현재 소의 위치에서 c 값이 같고, r 값이 현재 위치보다 더 큰 웜홀을 찾는다.
        // 해당하는 조건의 웜홀이 많을 경우, r 값이 가장 작은 웜홀을 선택한다.
        int next = 0;
        int nextr = Integer.MAX_VALUE;
        for (int ne = 1; ne <= N; ne++) {
          if (now == ne || wormhole[ne].c != nowc || wormhole[ne].r <= nowr) continue;
          if (wormhole[ne].r < nextr) {
            next = ne;
            nextr = wormhole[ne].r;
          }
        }
        if (next != 0) {
          // 조건에 해당하는 웜홀이 있을 경우 웜홀을 통해 반대편으로 이동시키고 위치를 저장한다.
          next = linked[next];
          if (visited[next]) return true;
          queue.add(next);
          visited[next] = true;
        }
      }
    }
    return false;
  }
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!