[99클럽 코테 스터디 8일차 TIL] 촌수계산 - 백준 2644

오늘 주제는 DFS/BFS이다.

 

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

우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 
이러한 촌수는 다음과 같은 방식으로 계산된다. 
기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다.

예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 
아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.
여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 
주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

[입력]
사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 
입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 
둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 
그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 
넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 
이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.
각 사람의 부모는 최대 한 명만 주어진다.

풀이 접근

부모가 같아지는 순간의 Depth를 더하면 되겠다는 생각을 했다.

그래서 부모에 어떤 자식이 있는지보다 자식의 부모가 누구인지가 더 중요하기 때문에 아래와 같이 코드를 작성했다.

let n = Int(readLine()!)!
let persons = readLine()!.split(separator: " ").map { Int("\($0)")! }
var parents: [Int:Int] = [:]
for r in 0..<Int(readLine()!)! {
    let pc = readLine()!.split(separator: " ").map { Int("\($0)")! }
    parents[pc[1]] = pc[0]
}

 

이제 부모를 하나씩 올라가면 된다.

하지만 시작하는 Depth가 다르기 때문에 Optional 처리에 신경써야한다.

var result = -1
var xParents: [Int] = [persons[0]]
var yParents: [Int] = [persons[1]]
var xParent: Int? = parents[persons[0]]
var yParent: Int? = parents[persons[1]]
while xParent != nil || yParent != nil {
    if let value = xParent {
        xParents.append(value)
        xParent = parents[value]
    }
    if let value = yParent {
        yParents.append(value)
        yParent = parents[value]
    }

겹치는 부모가 하나라도 발견된 시점이 중요하기 때문에 탐색 종료 조건을 다음과 같이 설정한다.

    let t = Set(xParents).intersection(Set(yParents))
    if let value = t.first {
        result = xParents.firstIndex(of: value)! + yParents.firstIndex(of: value)!
        break
    }
}
print(result)

최종 코드 - Swift

let n = Int(readLine()!)!
let persons = readLine()!.split(separator: " ").map { Int("\($0)")! }
var parents: [Int:Int] = [:]
for r in 0..<Int(readLine()!)! {
    let pc = readLine()!.split(separator: " ").map { Int("\($0)")! }
    parents[pc[1]] = pc[0]
}

var result = -1
var xParents: [Int] = [persons[0]]
var yParents: [Int] = [persons[1]]
var xParent: Int? = parents[persons[0]]
var yParent: Int? = parents[persons[1]]
while xParent != nil || yParent != nil {
    if let value = xParent {
        xParents.append(value)
        xParent = parents[value]
    }
    if let value = yParent {
        yParents.append(value)
        yParent = parents[value]
    }
    let t = Set(xParents).intersection(Set(yParents))
    if let value = t.first {
        result = xParents.firstIndex(of: value)! + yParents.firstIndex(of: value)!
        break
    }
}
print(result)

최종 코드 - Python3

Swift와 같은 로직으로 해결했다.

input()
x,y = map(int,input().split())
parents = {}
for _ in range(int(input())):
  p, c = map(int,input().split())
  parents[c] = p

result = -1
xParents = [x]
yParents = [y]
xParent = parents[x] if x in parents else 0
yParent = parents[y] if y in parents else 0
while xParent != 0 or yParent != 0:
    if xParent != 0:
        xParents.append(xParent)
        xParent = parents[xParent] if xParent in parents else 0
    if yParent != 0:
        yParents.append(yParent)
        yParent = parents[yParent] if yParent in parents else 0
    i = set(xParents).intersection(set(yParents))
    if i:
        v = i.pop()
        result = xParents.index(v) + yParents.index(v)
        break
print(result)

Conclusion

집합 데이터를 처음부터 만들어 사용했으면 배열을 집합으로 변환하는 시간이 줄지 않을까 싶긴하다.

항상 자식노드의 탐색을 통해 문제를 해결했다보니

솔직히 처음에는 부모 노드로 올라가며 탐색할 생각을 못했다.

양방향으로 생각해볼 필요가 있겠다.