[BOJ] 백준 4803 트리 (Swift)

문제

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

4803번: 트리

풀이

무방향 그래프에서 사이클이 있는 지 판별해야 하는 문제입니다.
여러 방법이 있겠지만 저는 DFS를 사용하였습니다.

무방향 그래프이기 때문에 1번 노드와 2번 노드가 연결되어 있다면, 1 -> 2, 2 -> 1 로 가능하기에 사이클이 존재한다고 할 수 있지만,
이러한 점을 제외하기 위해서, 직전의 노드로 탐색하는 것은 제외하고 이미 방문한 노드를 또 방문한다면 사이클이 있다고 판별해주었습니다.

소스코드

	var i = 1
	while let input = readLine()?.split(separator: " ").map({ Int($0)! }), input != [0, 0] {
	let n = input[0], m = input[1]
	print("Case \(i): \(solution(n, m))")
	i += 1
	}
	func solution(_ n: Int, _ m: Int) -> String {
	var graph = [[Int]](repeating: [], count: n + 1)
	var visited = [Bool](repeating: false, count: n + 1)
	var isTree = false
	for _ in 0..<m {
	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let a = input[0], b = input[1]
	graph[a].append(b)
	graph[b].append(a)
	}
	@discardableResult
	func dfs(prev: Int, current: Int) -> Bool {
	visited[current] = true
	for nextNode in graph[current] {
	if nextNode == prev {
	continue
	}
	if visited[nextNode] {
	isTree = false
	continue
	}
	dfs(prev: current, current: nextNode)
	}
	return isTree
	}
	var treeCount = 0
	for i in 1...n {
	if !visited[i] {
	isTree = true
	treeCount += dfs(prev: 0, current: i) ? 1 : 0
	}
	}
	switch treeCount {
	case 0:
	return "No trees."
	case 1:
	return "There is one tree."
	default:
	return "A forest of \(treeCount) trees."
	}
	}

view raw 트리.swift hosted with ❤ by GitHub

후기

처음에는 DFS 함수에서 이미 방문한 노드를 또 방문할 때, 바로 false를 리턴하도록 구현했습니다.
계속해서 오답판정을 받아서 왜 그런지 확인을 해봤는데,

다음과 같을 때, 1번 노드부터 DFS를 실행하면 3번 노드에서 1번 노드를 방문할 때 이미 방문한 노드이므로 false를 리턴하고 DFS 함수를 종료하게 됩니다.
그렇다면 4번 노드는 아직 방문하지 않았기 때문에, 4번 노드에 대해 DFS를 한 번 더 수행하는게 이상했습니다.

결론적으로 이어저 있는 그래프를 전부 방문을 하지 않고 return을 하는 것에 대해서 문제가 있었기에 따로 변수를 두어 전부 방문처리를 한 후,
트리인지 아닌지 확인해주도록 구현하여 정답 판정을 받았습니다.