[BOJ] 백준 1976번 : 여행 가자 (JAVA)

문제

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 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를 출력한다.

 

 

풀이

유니온 파인드의 기초 문제였습니다. 혹시나 유니온 파인드 문제를 한 번도 안 풀어 보신 분은 아래 포스팅을 참조하시길 바랍니다.

 

 

[BOJ] 백준 1717번 : 집합의 표현 (JAVA)

 

 

전반적인 로직은 아래와 같습니다.

 

 

1. 주어진 행렬에서 1인 요소가 있으면, union(a, b) 연산을 한다.

2. 여행 계획에서 맨 처음 도시를 find 연산하여 루트 노드를 찾는다.

3. 여행 계획 상의 2 ~ N 도시에 대하여 find 연산을 한 루트 노드와 2에서 수행한 루트 노드를 비교한다.

3-1. 만약, 서로 루트 노드가 다를 경우 "NO"를 출력한다.

3-2. 만약, 모든 여행 계획 상의 도시의 루트 노트가 같을 경우 "YES"를 출력한다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

소스코드 - 유니온 파인드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    static int[] parent;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
 
        parent = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }
 
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                int temp = Integer.parseInt(st.nextToken());
 
                // 연결된 부분은 합집합 연산함.
                if (temp == 1) {
                    union(i, j);
                }
            }
        }
 
        st = new StringTokenizer(br.readLine());
        int start = find(Integer.parseInt(st.nextToken()));
        for (int i = 1; i < M; i++) {
            int now = Integer.parseInt(st.nextToken());
 
            // 맨 처음 출발 도시와 연결되어있지 않은 도시가 있으면
            // 여행 계획이 불가능한 것임.
            if (start != find(now)) {
                bw.write("NO\n");
                bw.flush();
                bw.close();
                br.close();
                return;
            }
        }
 
        bw.write("YES\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
    // x의 부모를 찾는 연산
    public static int find(int x) {
        if (x == parent[x]) {
            return x;
        }
 
        return parent[x] = find(parent[x]);
    }
 
    // y의 부모를 x의 부모로 치환하는 연산 (x > y 일 경우, 반대)
    public static void union(int x, int y) {
        x = find(x);
        y = find(y);
 
        if (x != y) {
            if (x < y) {
                parent[y] = x;
            } else {
                parent[x] = y;
            }
        }
    }
 
}

 

 

추가사항

유니온 파인드 외에 플로이드 와샬 알고리즘도 풀린다는 것을 확인하였습니다.

N이 최대 200이기때문에 O(N^3)을 취해도 괜찮은 듯 합니다.

 

다만, 시작점과 도착점이 같은 경우는 항상 여행이 가능하다는 점만 유의하시면 됩니다.

 

아래는 플로이드 와샬 알고리즘으로 구현한 소스코드입니다.

 

 

소스코드 - 플로이드 와샬 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    static int[] parent;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
 
        int[][] arr = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
 
                if (i == j) { // 출발점과 도착점이 같은 경우도 항상 여행이 가능함.
                    arr[i][j] = 1;
                }
            }
        }
        
        // 플로이드 와샬 알고리즘
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (arr[i][k] == 1 && arr[k][j] == 1) {
                        arr[i][j] = 1;
                    }
                }
            }
        }
 
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        for (int i = 1; i < M; i++) {
            int now = Integer.parseInt(st.nextToken());
 
            if (arr[start][now] == 0) {
                bw.write("NO\n");
                bw.flush();
                bw.close();
                br.close();
                return;
            }
        }
 
        bw.write("YES\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
}
 

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.