[BOJ] 백준 11725 트리의 부모 찾기 (Swift)

문제

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

11725번: 트리의 부모 찾기

풀이

• 먼저 트리를 그려보았음
• 루트노드가 1로 고정되어 있어서 BFS/DFS를 1에서 한번만 수행시키면 되겠다고 생각했음
• 간선의 개수는 노드의 개수 - 1개 이므로, 무조건 모든 노드가 연결되어 있을 것이라고 생각했음
• 부모의 노드를 알기 위해서는 현재노드 -> 다음노드 로 탐색할 때, 현재노드의 번호를 어딘가에 담아둬야 될 것이라고 생각했음
• visited 배열을 [Bool] 자료형으로 선언해서 사용했었는데, [Int]로 선언에서 그곳에 담아두어서 해결할 수 있다고 아이디어를 떠올렸음

소스코드

	let n = Int(readLine()!)!
	var graph = [[Int]](repeating: [Int](repeating: 0, count: 0), count: n + 1)
	for _ in 0..<n - 1 {
	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let a = input[0], b = input[1]
	graph[a].append(b)
	graph[b].append(a)
	}
	var visited = [Int](repeating: 0, count: n + 1)
	// 루트노드는 1이기 때문에 node를 1로 고정시켜두었음
	func bfs(node: Int = 1) {
	var queue = [node]
	var index = 0
	// 1의 루트노드는 없기 때문에 -1로 처리하였음
	visited[node] = -1
	while queue.count > index {
	let node = queue[index]
	for nextNode in graph[node] {
	if visited[nextNode] == 0 {
	visited[nextNode] = node
	queue.append(nextNode)
	}
	}
	index += 1
	}
	}
	bfs()
	// 2번 노드부터 출력
	for i in 2...n {
	print(visited[i])
	}

view raw 트리의 부모 찾기(BFS).swift hosted with ❤ by GitHub

	let n = Int(readLine()!)!
	var graph = [[Int]](repeating: [Int](repeating: 0, count: 0), count: n + 1)
	for _ in 0..<n - 1 {
	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let a = input[0], b = input[1]
	graph[a].append(b)
	graph[b].append(a)
	}
	var visited = [Int](repeating: 0, count: n + 1)
	// 루트노드는 1이기 때문에 node를 1로 고정시켜두었음
	func dfs(node: Int = 1) {
	for nextNode in graph[node] {
	if visited[nextNode] == 0 {
	visited[nextNode] = node
	dfs(node: nextNode)
	}
	}
	}
	dfs()
	// 2번 노드부터 출력
	for i in 2...n {
	print(visited[i])
	}

view raw 트리의 부모 찾기(DFS).swift hosted with ❤ by GitHub

후기

부모의 노드 번호를 어떻게 알 수 있을까하고 생각을 좀 해봤던 것 같다.
맨 처음에는 외부로 배열을 선언하여 노드의 번호를 인덱스로 이전 노드의 번호를 넣어줄 까 했었는데,
visited 배열을 [Int]로 선언하여 해결할 수 있겠다는 아이디어를 떠올렸다.
생각한대로 풀이해서 좋았다!! 🙌