코딩 테스트 [그래프] - 여행 계획 짜기

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 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번째 줄에 도시의 수 N이 주어진다(N ≤ 200). 2번째 줄에 여행 계획에 속한 도시들의 수 M이 주어진다(M ≤ 1,000). 다음 N개의 줄에는 N개의 정수가 주어진다. i번째 줄의 j번째 수는 i번 도시와 j번 도시의 연결 정보를 의미한다. 1이면 연결된 것이고, 0이면 연결되지 않은 것이다. A와 B가 연결됬으면 B와 A도 연결돼 있다. 마지막 줄에는 여행 계획이 주어진다. 도시의 번호는 1에서 N까지 차례대로 매겨져 있다.

출력

1번째 줄에 가능하면 YES, 불가능하면 NO를 출력한다.

예제 입력
3	// 도시 개수
3	// 여행 경로 데이터
0 1 0
1 0 1
0 1 0
1 2 3

예제 출력
YES

---

1단계 - 문제 분석하기

도시의 연결 유무를 유니온 파인드 연산을 이용해 해결하는 문제이다.
이 문제에서는 도시 간 연결 데이터를 인접 행렬의 형태로 주었기 때문에 인접 행렬을 탐색하면서 연결될 때마다 union 연산을 수행하는 방식으로 문제에 접근하면 된다.

2단계 - 손으로 풀어 보기

1 도시와 여행 경로 데이터를 저장하고, 각 노드와 관련된 대표 노드 배열의 값을 초기화한다.

2 도시 연결 정보가 저장된 인접 행렬을 탐색하면서 도시가 연결돼 있을 때 union 연산을 수행한다. 이때 항상 큰 도시가 대표가 되도록 union 연산의 매개변수를 변경한다.

3 여행 경로에 포함된 도시의 대표 노드가 모두 같은지 확인한 후 결괏값을 출력한다.

재귀함수를 빠져나가면서 배열값이 대표노드로 변경
=> 경로 압축
=> 여행 경로에 있는 모든 도시의 대표 도시가 3으로 같으므로 YES 출력

3단계 - sudo코드 작성하기

N(도시의 수) M(여행 계획에 속한 도시의 수)
parent(대표 노드 저장 배열)
city(도시의 연결 데이터 배열), route(여행 계획 도시 저장 배열)

for(N만큼 반복)
{
	대표 노드를 자기 자신으로 초기화.
}

for(N만큼 반복)
{
	for(N만큼 반복)
    {
    	city 데이터 저장
    }
}

for(M만큼 반복)
{
	route 데이터 저장
}

for(i -> N만큼 반복)
{
	for(j -> N만큼 반복)
    {
    	city[i][j] == 1이면 union 연산
    }
}

for(M만큼 반복)
{
	route에 포함되는 노드들의 대표 노드가 모두 동일한지 확인한 후 결괏값 출력
}

union(a, b) {
	a와 b의 대표 노드 찾기
    두 원소의 대표 노드끼리 연결하기
}

find(a) {
	a가 대표 노드면 리턴
    아니면 a의 대표 노드값을 find(parent[a])값으로 저장
}

4단계 - 코드 구현하기

import java.util.Scanner;

public class Q51 {
    public static int[] parent;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        parent = new int[N + 1];
        int[][] city = new int[N+1][N+1];
        int[] route = new int[M+1];

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

        for(int i = 1; i < N+1; i++){
            for(int j = 1; j < N+1; j++){
                city[i][j] = sc.nextInt();
            }
        }

        for(int i = 1; i < M+1; i++){
            route[i] = sc.nextInt();
        }

        for(int i = 1; i < N+1; i++){
            for(int j = 1; j < N+1; j++){
                if(city[i][j] == 1){
                    union(i, j);
                }
            }
        }

        int index = find(route[1]);
        for(int i = 2; i < route.length; i++){
            if(index != find(route[i])){
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }

    public static void union(int a, int b){
        a = find(a);
        b = find(b);
        if(a != b){
            if(b > a){
                int tmp = a;
                a = b;
                b = tmp;
            }
            parent[b] = a;
        }
    }

    public static int find(int a){
        if(a == parent[a])
            return a;
        else
            return parent[a] = find(parent[a]);
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편