[백준 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라는 여행경로를 통해 목적을 달성할 수 있다.
• 도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 (중복 가능) 가능한지 여부를 판별하는 프로그램을 작성하시오.

 

입력

• 첫 줄에 도시의 수 N이 주어진다.
  • N은 200이하이다.
• 둘째 줄에 여행 계획에 속한 도시들의 수 M이 주어진다.
  • M은 1000이하이다.
• 다음 N * N 행렬을 통해 임의의 두 도시가 연결되었는지에 관한 정보가 주어진다.
  • 1이면 연결된 것이고 0이면 연결이 되지 않은 것이다.
  • A와 B가 연결되었으면 B와 A도 연결되어 있다.
• 마지막 줄에는 여행 계획이 주어진다.

 

출력

• 첫 줄에 가능하면 YES 불가능하면 NO를 출력한다.

 

 

솔루션

• Disjoint Set을 이용한 간단한 문제이다.
  • Disjoint Set
• 연결 여부 입력 값이 인접 행렬 형태로 주어진다.
  • 행렬을 입력 받으면서 동시에 도시 사이가 연결되어 있는지 확인한다.
    • 연결되어 있다면 두 도시를 합쳐준다 (합집합 연산).
• 마지막 여행 경로에 대해 여행이 가능한지 집합을 확인하고 종료한다.

 

Code

• 전체 코드 : Solution_1976

초기에 각 노드의 루트를 본인으로 초기화하는 함수

public static void Initialize() {
    for (int i = 1; i <= N; i++)
        parent[i] = i;
}

 

어느 집합에 속해있는지 루트 노드를 반환하는 함수

public static int Find(int u) {
    if (parent[u] == u)
        return u;
 
    return parent[u] = Find(parent[u]);
}

 

상호배타적인 두 노드 집합을 합쳐주는 합집합 연산

public static void Union(int u, int v) {
    int uR = Find(u);
    int vR = Find(v);
 
    if (uR == vR)
        return;
 
    if (rank[uR] > rank[vR])
        Swap(uR, vR);
 
    parent[uR] = vR;
 
    if (rank[uR] == rank[vR])
        rank[vR]++;
}

 

메인 함수

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    N = Integer.parseInt(br.readLine());
    M = Integer.parseInt(br.readLine());
 
    parent = new int[N + 1];
    rank = new int[N + 1];
 
    Initialize();
    
    for (int i = 1; i <= N; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for (int j = 1; j <= N; j++) {
            if(Integer.parseInt(st.nextToken()) == 1)
                Union(i, j);
        }
    }
    
 
    StringTokenizer st = new StringTokenizer(br.readLine());
    int pre = Integer.parseInt(st.nextToken());
    int cur = Integer.parseInt(st.nextToken());
 
    while (Find(pre) == Find(cur)) {
        if (st.hasMoreTokens())
            cur = Integer.parseInt(st.nextToken());
        else
            break;
    }
 
    if (st.hasMoreTokens())
        bw.write("NO");
    else
        bw.write("YES");
 
    bw.flush();
    bw.close();
    br.close();
}

 

결과