Swift) 백준 17619번 개구리점프 - G3

https://www.acmicpc.net/problem/17619

17619번: 개구리 점프

처음 이 문제를 봤을때 프로그래머스의 요격 시스템 문제와 비슷하다고 생각했으나 다른 방식으로 접근 해야했다.

문제의 요점은 A통나무에서 B 통나무로 이동이 가능한를 판단하는 것

만약 통나무 A → D로 이동이 가능하다면 그 중간에 있는 서로 이동 가능한 통나무들끼리는 이동이 가능하다.

A → D로 이동 할 때, A → B, B→D or A→B, B→C, C→D로 이동이 가능하다. 즉 C에서 A로 이동하고 싶다면 C →B, B→A로도 이동이 가능하므로 서로 연결된(이동이 가능한) 통나무 번호가 들어왔을 때 서로 연결이 되어있는지 확인하면 된다.

이때 y축은 신경 안써도 된다.

이런식으로 통나무가 배치되어도 A→D로 갈때 A→B, B→C,C→D로 갈 수 있다. 즉 통나무 끼리 서로 X축의 범위가 연결 되어있다면 한번에 하나의 통나를 거쳐 갈 수 있는 경로가 있다.

따라서 문제는 서로 연결된 노드를 확인하는 알고리즘인 합집합 찾기 (Union-Find) 알고리즘을 이용. 합집합을 만들어서 두개의 통나무가 주어졌을때, 두 통나무가 부모를 체크해서 확인하면 된다.

Union-Find 알고리즘은 동빈나님이 아주 잘 설명하셨으므로 그걸 참고해서 보면 될 듯하다.

 

import Foundation

let nq = readLine()!.split(separator: " ").map { Int($0)! }
let n = nq[0]
let q = nq[1]
var treeArr: [(Int, Int, Int)] = Array(repeating: (0, 0, 0), count: 100001)
var parentsArr: [Int] = Array(repeating: -1, count: 100001)

func find(num: Int) -> Int {
    if num == parentsArr[num] {
        return num
    }
    parentsArr[num] = find(num: parentsArr[num])
    return parentsArr[num]
}

func unite(a: Int, b: Int) {
    let aParent = find(num: a)
    let bParent = find(num: b)
    if aParent < bParent {
        parentsArr[bParent] = aParent
    } else {
        parentsArr[aParent] = bParent
    }
}

func checkIsSameParent(a: Int, b: Int) -> Bool {
    let aParent = find(num: a)
    let bParent = find(num: b)
    if aParent == bParent {
        return true
    }
    return false
}

for i in 1...n {
    parentsArr[i] = i
}

for i in 1...n {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    treeArr[i] = (input[0], input[1], i)
}
treeArr[1...n].sort { $0.0 < $1.0 }
var end = treeArr[1].1
var currentTree = 1
for i in 2...n {
    if treeArr[i].0 <= end {
        if treeArr[i].1 <= end {
            unite(a: treeArr[currentTree].2, b: treeArr[i].2)
        } else {
            unite(a: treeArr[currentTree].2, b: treeArr[i].2)
            currentTree = i
            end = treeArr[i].1
        }
    } else {
        currentTree = i
        end = treeArr[currentTree].1
    }
}

for _ in 0..<q {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    print(checkIsSameParent(a: input[0], b: input[1]) ? 1 : 0)
}