[BOJ] 백준 11724 연결 요소의 개수 (Swift)

문제

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

11724번: 연결 요소의 개수

풀이

• 먼저 예제입력 1에 있는 그래프를 그려보았다.
• 방문하지 않은 모든 노드에대해 BFS/DFS를 수행하면서 총 몇번 수행되는지 확인하면 연결 요소의 개수를 확인할 수 있겠다고 생각했다.
  • [1]번 노드에대해 BFS/DFS 수행시 [2, 5] 노드를 방문하기 때문에 2번 노드는 건너뛰고 3번 노드에 대해 BFS/DFS 수행..
  • [3]번 노드에 대해 수행하면 [4, 6]번 노드를 방문
  • 총 탐색 횟수는 2회! 이는 2개의 그룹의로 나눠져 있다고 이해 할 수 있음

소스코드

	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let n = input[0], m = input[1]
	var graph = [[Int]](repeating: [Int](repeating: 0, count: 0), count: n + 1)
	for _ in 0..<m {
	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let u = input[0], v = input[1]
	graph[u].append(v)
	graph[v].append(u)
	}
	var visited = [Bool](repeating: false, count: n + 1)
	func bfs(node: Int) {
	var queue = [node]
	var index = 0
	visited[node] = true
	while queue.count > index {
	let node = queue[index]
	// 연결된 요소를 방문하지 않았다면 큐에 추가
	for nextNode in graph[node] {
	if !visited[nextNode] {
	visited[nextNode] = true
	queue.append(nextNode)
	}
	}
	index += 1
	}
	}
	var answer = 0
	// BFS 수행
	for i in 1...n {
	if !visited[i] {
	answer += 1
	bfs(node: i)
	}
	}
	print(answer)

view raw 연결 요소의 개수(BFS).swift hosted with ❤ by GitHub

	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let n = input[0], m = input[1]
	var graph = [[Int]](repeating: [Int](repeating: 0, count: 0), count: n + 1)
	for _ in 0..<m {
	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let u = input[0], v = input[1]
	graph[u].append(v)
	graph[v].append(u)
	}
	var visited = [Bool](repeating: false, count: n + 1)
	func dfs(node: Int) {
	visited[node] = true
	// 방문하지 않은 노드에 대해 DFS 수행
	for nextNode in graph[node] {
	if !visited[nextNode] {
	visited[nextNode] = true
	dfs(node: nextNode)
	}
	}
	}
	var answer = 0
	// DFS 수행
	for i in 1...n {
	if !visited[i] {
	answer += 1
	dfs(node: i)
	}
	}
	print(answer)

view raw 연결 요소의 개수(DFS).swift hosted with ❤ by GitHub

후기

말 그대로 연결 노드의 개수를 구하는 문제였다.
기본적인 그래프 문제라고 생각하고 쉽게 풀이할 수 있었다.