백준 - 여행 가자 (1976)

let N = Int(readLine()!)!
let M = Int(readLine()!)!
var graph = Array(repeating: [0], count: N+1)
var parent = Array(0...N)
var flag = true

for i in 1...N {
    let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
    graph[i] += input
}

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

for i in 1...N {
    for j in 1...N {
        if graph[i][j] == 1 {
            union(i, j)
        }
    }
}

var now = parent[plan[0]]
for city in plan {
    if parent[city] != now {
        flag = false
        break
    }
}

print(flag ? "YES" : "NO")

func union(_ a: Int, _ b: Int) {
    let aParent = find(a)
    let bParent = find(b)
    
    if aParent < bParent {
        parent[bParent] = aParent
    } else {
        parent[aParent] = bParent
    }
}

func find(_ node: Int) -> Int {
    if parent[node] == node {
        return node
    }
    parent[node] = find(parent[node])
    
    return parent[node]
}

• 인접 행렬를 순회하며 도시가 연결되어 있으면 유니온 파인드 연산을 수행한다.
• 여행 경로에 있는 도시들의 부모 노드가 모두 같으면 “YES”, 아니면 “NO”를 출력한다.