[유니온파인드] 백준 여행 가자

문제

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

예제 입력 1 복사

3
3
0 1 0
1 0 1
0 1 0
1 2 3

예제 출력 1 복사

YES

1. 접근

도시를 연결하는것을 보고 그래프 문제라고 생각했어요. 그리고 연결 여부를 파악하는 부분이랑 특히 1이면 연결된 것이고 0이면 연결이 되지 않은 것이라는 부분에서 유니온파인드로 풀면 되겠다고 생각했어요.

2. 풀이

유니온 파인드로 문제를 풀 것이기 때문에 기본적인 메소드 3개를 정의해줍니다.

1. find: 해당 노드의 root 노드를 찾는 메소드 입니다.
2. union: 두 노드값을 연결하는 메소드인데, 정말 연결한다기 보단 find 메소드를 사용해서 두 최상의 노드를 구해서 비교 후 최상위 노드의 값을 치환하는 식으로 연결해주는 메소드 입니다.
3. checkParent: 두 노드의 최상위 노드값이 같은지 확인해주는 메소드 입니다.

첫번째로 입력값들을 입력받고,

union 메소드로 알려준 노드연결 정보대로 연결을 해준 다음에

checkParent 메소드로 마지막에 입력받은 값이 연결되어 있는지를 확인해서 연결이 안된게 있으면 NO, 모두 연결되있으면 YES를 출력합니다.

3. 소스코드[Swift]

import Foundation

// MARK: - Func
func find(x: Int) -> Int {
    if x == parent[x] {
        return x
    } else {
        return find(x: parent[x])
    }
}

func union(x: Int, y: Int) {
    var a = find(x: x)
    var b = find(x: y)

    if level[a] < level[b] {
        swap(&a, &b)
    }

    if a != b {
        parent[b] = a
    }

    if level[a] == level[b] {
        level[b] += 1
    }
}

func checkParent(x: Int, y: Int) -> Bool {
    let a = find(x: x)
    let b = find(x: y)

    return a == b ? true : false
}

// MARK: - Input & Property
let n = Int(readLine()!)!
var result = Int(readLine()!)!
var nodeArray: [[Int]] = [[0]]
var parent: [Int] = Array(repeating: 0, count: n+1)
var level: [Int] = Array(repeating: 1, count: n+1)
var target: [Int] = []

for i in 1 ... n {
    nodeArray.append(readLine()!.split(separator: " ").map{Int($0)!})
    parent[i] = i
}

target = readLine()!.split(separator: " ").map{Int($0)!}

// MARK: - Run
for i in 1 ... n {
    for j in 0 ..< n {
        if nodeArray[i][j] == 1 {
            union(x: i, y: j+1)
        }
    }
}

for i in 0 ..< target.count-1 {
    if !checkParent(x: target[i], y: target[i+1]) {
        print("NO")
        result = -1
        break
    }
}
if result != -1 { print("YES") }