ℹ️ 문제 정보
| 플랫폼 | 번호 | 제목 | 유형 | 난이도 | 언어 |
|---|---|---|---|---|---|
| 백준 | 2644 | 촌수계산 | DFS, BFS | 실버2 | Swift, Python |
🚀 나의 접근 방법
문제를 처음 딱 보면 가계도가 떠오른다. 즉, 입력으로 주어진 부모 자식들의 관계로 그래프를 만들고 탐색을 하면 된다.
필자는 인접행렬로 그래프를 정의하였고 BFS로 탐색하였다. (DFS도 가능하다)
촌수를 계산해야 하는 서로 다른 두 사람의 번호가 입력으로 주어진다. 두 사람 사이의 촌수를 구해야 하므로 두 사람 중 한 명을 탐색 시작 노드로 정한다. 그리고 나머지 한 사람을 찾을 때까지 탐색을 진행하면 된다.
두 사람 사이의 촌수를 알아야 하는데 이는 두 사람(노드) 사이의 간선의 개수와 동일하다. 그래서 탐색을 할 때 간선의 수도 같이 세어 주면 촌수를 알아낼 수 있다.
✍️ 나의 코드
Swift
let n = Int(readLine()!)!
let target = readLine()!.split(separator: " ").map{ Int($0)! }
let (t1, t2) = (target[0], target[1])
let m = Int(readLine()!)!
var graph: [[Int]] = Array(repeating: [], count: n + 1)
for _ in 0..<m {
let input = readLine()!.split(separator: " ").map{ Int($0)! }
let (u, v) = (input[0], input[1])
graph[u].append(v)
graph[v].append(u)
}
var visited: [Bool] = Array(repeating: false, count: n + 1)
func bfs(_ v: Int) -> Int {
var queue = [(v, 0)]
var idx = 0
visited[v] = true
while idx < queue.count {
let n = queue[idx].0
let depth = queue[idx].1
if n == t2 {
return depth
}
for i in graph[n] {
if !visited[i] {
queue.append((i, depth + 1))
visited[i] = true
}
}
idx += 1
}
return -1
}
print(bfs(t1))Python
from collections import deque
n = int(input())
t1, t2 = map(int, input().split(" "))
m = int(input())
graph = [[] for i in range(n + 1)]
for _ in range(m):
u, v = map(int, input().split(" "))
graph[u].append(v)
graph[v].append(u)
visited = [False] * (n + 1)
def bfs(v):
queue = deque([(v, 0)])
visited[v] = True
while len(queue) > 0:
n = queue.popleft()
node = n[0]
depth = n[1]
if node == t2:
return depth
for i in graph[node]:
if not visited[i]:
queue.append((i, depth + 1))
visited[i] = True
return -1
print(bfs(t1))🤔 회고 및 개선사항
문제를 그려봤을 때 손쉽게 그래프가 보이고 탐색으로 찾으면 되겠다고 바로 알 수 있었다.
크게 어려운 부분 없이 해결할 수 있었다.
나야, 개발자