[BOJ] 1976 여행 가자 - JAVA

1. 문제

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

1976번: 여행 가자

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.

도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.

---

2. 풀이

• 인접행렬로 입력을 주기 때문에 그에 맞춰서 입력받는다. 따로 행렬구조로 저장은 하지 않았다.
• 1인 요소끼리 전부 합한다.
• 동혁이가 준 경로로 이동하던 중 루트가 다른 걸 만나면 NO를 출력하고 메인함수를 바로 종료한다.
• 중간에 종료되지 않으면 모두 이어져있는 경우이므로 YES를 출력한다.

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

public class BOJ_1976_여행가자 {
   static int[] set;
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st;
      int N = Integer.parseInt(in.readLine());
      int M = Integer.parseInt(in.readLine());

      set = new int[N+1];
      for(int i=1;i<N;i++) set[i] = i;

      for(int i=1;i<=N;i++){
         st = new StringTokenizer(in.readLine());
         for(int j=1;j<=N;j++){
            if(st.nextToken().equals("1")) union(i,j);
         }
      }

      st = new StringTokenizer(in.readLine());
      int root = find(Integer.parseInt(st.nextToken()));
      for(int i=1;i<M;i++){
         if(root!=find(Integer.parseInt(st.nextToken()))){
            System.out.println("NO");
            return;
         }
      }
      System.out.println("YES");
   }

   private static int find(int x){
      if(set[x]==x) return x;
      return set[x]=find(set[x]);
   }

   private static void union(int a, int b){
      int pa = find(a);
      int pb = find(b);

      if(pa==pb) return;

      if(pa>pb) set[pb] = pa;
      else set[pa] = pb;
   }
}

---

3. 결과

[다른 문제] 에서 static으로 했을 때 더 빨라진 이슈가 있어서 테스트해봤다. 아래가 static 사용, 위가 지역변수를 사용한 결과다. 이 문제에서는 시간도 똑같고 메모리도 비슷하다.