[BOJ] 1865 웜홀 - JAVA

1. 문제

1865번: 웜홀

때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.

시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.

---

2. 풀이

간선 클래스

도로, 웜홀을 저장할 클래스를 만들었다.

static class Edge {
   int from;
   int to;
   int time;
   Edge(int from, int to, int time){
      this.from = from;
      this.to = to;
      this.time = time;
   }
}

 

음의 순환 체크 메서드

1.  시작이 어디든 상관없이 노드의 개수만큼 반복하면서 시간을 계산한다.

2.  만약 N번째(코드상으로는 N-1번째)에도 dist갱신이 일어난다면 음의 순환이 일어나고 있는 것이므로 true를 리턴하고 그만둔다.

3.  위에서 메서드가 끝나지 않았다면 return false한다.

public static boolean isCycle(){
   int[] dist = new int[N+1];
   Arrays.fill(dist, INF);
   int cur,next,cost;
   for(int i=0;i<N;i++){
      for(Edge edge:edges){
         cur = edge.from;
         next = edge.to;
         cost = edge.time;
         if(dist[next]>dist[cur]+cost){
            dist[next] = dist[cur]+cost;
            if(i==N-1) return true;
         }
      }
   }
   return false;
}

 

메인

static

List<Edge> edges	간선 리스트
int N,M,W	지점 수, 도로 수, 웜홀 수
int INF	최댓값. 임의로 25000001로 지정했다. 도로만 시간이 양수만큼 걸리므로 도로의 최대개수 2500개*최대시간 10000 한 값에 +1을 한 것이다.
String yes,no	반복적으로 String을 만들지 않고 상수처럼 사용하기 위해 만들었다.

 

코드

1.  지정된 tc만큼 반복한다. 새로운 tc마다 edges 리스트 객체를 새로 만든다.

2.  도로와 웜홀을 한꺼번에 입력받는데, 도로를 입력할때는 양방향이므로 방향만 바꿔서 두 번 더한다.

3.  웜홀은 시간이 뒤로 가므로 시간에 -1을 곱한 값을 이용한다.

4.  isCycle메서드가 true라면 음수순환이 일어나므로 출발지에 되돌아왔을 때 시간이 돌아가는 게 가능하다. yes를 sb에 더한다. false라면 no를 한다.

static List<Edge> edges;
static int N,M,W;
static int INF = 25000001;
static String yes = "YES\n", no="NO\n";
public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   int TC = Integer.parseInt(in.readLine());
   StringBuilder sb = new StringBuilder();
   StringTokenizer st;
   for(int tc = 0;tc<TC;tc++){
      st = new StringTokenizer(in.readLine());
      N = Integer.parseInt(st.nextToken());
      M = Integer.parseInt(st.nextToken());
      W = Integer.parseInt(st.nextToken());
      edges = new ArrayList<>();
      int from,to,time;
      for(int i=0;i<M+W;i++) {
         st = new StringTokenizer(in.readLine());
         from = Integer.parseInt(st.nextToken());
         to = Integer.parseInt(st.nextToken());
         time = Integer.parseInt(st.nextToken());
         if(i<M) {
            edges.add(new Edge(from,to,time));
            edges.add(new Edge(to,from,time));
         }else {
            edges.add(new Edge(from,to,-time));
         }
      }

      if(isCycle()) sb.append(yes);
      else sb.append(no);
   }

   System.out.print(sb);
}

---

3. 결과

벨만포드 같으면서도 완전히 벨만포드는 아니고 그 느낌만 내는 문제였다. 출발지가 어딘지 상관없이 음수순환이 일어나는지만 알면 되는 문제다.