99클럽 코테 스터디 4일차 TIL: DFS

문제

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

 

풀이

오늘은 챌린저 문제가 아닌 미들러 문제를 풀었다.
그 이유는 챌린저 문제를 1시간안에 풀어보려 했지만 풀이하지 못했다.
힌트를 확인해보니 벨만포드 알고리즘이였고,
벨만포드 알고리즘 하면 기억나는데 음의간선에서도 최단거리를 구할 수 있다는점..? 그래서 사이클이 존재하면 안된다는 점 밖에 기억이 나지 않았다..

그래서 일단은 미들러 문제를 풀고, 주말에 벨만포드 알고리즘에 대해 더 학습하고 풀어야겠다고 생각했다.

미들러문제는 DFS의 기본적인 문제였고, 챌린저 문제와 난이도 차이가 있다고 느꼈다.
DFS에 대해 알고, 조금만 응용한다면 쉽게 풀 수있다.

방문 여부를 확인하는 visited 배열을 Int로 사용하였고, 0일 때는 아직 방문하지 않은 것, 그 이후 자연수는 방문한 Depth로 두었다.

소스코드

	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let n = input[0], m = input[1], r = input[2]
	var visited = [Int](repeating: 0, count: n + 1)
	var graph = [[Int]](repeating: [], 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)
	}
	for i in 1...n { graph[i] = graph[i].sorted(by: <) }
	var depth = 1
	func dfs(node: Int) {
	visited[node] = depth
	for nextNode in graph[node] {
	if visited[nextNode] == 0 {
	depth += 1
	dfs(node: nextNode)
	}
	}
	}
	dfs(node: r)
	print(visited[1...].map { String($0) }.joined(separator: "\n"))

view raw 24479_알고리즘 수업 - 깊이 우선 탐색 1.swift hosted with ❤ by GitHub

후기

갑자기 챌린저 문제가 어려웠다.. 주말에 꼭 풀어봐야지..