너비우선탐색 2

[BOJ/16947/Golang] 백준 16947 - 서울 지하철 2호선

문제로 이동하기 https://www.acmicpc.net/problem/16947 접근 방식 큰 순서는 다음과 같습니다. 그래프 내의 모든 사이클과 사이클에 속한 정점을 구한다. 사이클에 속한 정점에 연결된 정점들 중 사이클에 속하지 않은 정점을 방문하며 거리를 구한다. 하지만 이 문제에서 핵심은 사이클을 찾고, 사이클에 속한 정점을 구하는 과정입니다. 위 2번은 그저 찾아낸 정점으로부터 DFS 또는 BFS를 수행하면 쉽게 찾을 수 있습니다. 물론 DFS보다는 BFS로 찾는게 더 효율적입니다. 이유는 후에 설명 드리겠습니다. 트리 N개의 정점과 N-1개의 간선으로 이루어진 그래프는 트리입니다. 트리는 사이클이 없으며, 최단 경로를 DFS와 BFS로 구할 수 있습니다. 만약 이 트리에 간선이 하나 더 추..

PS/BOJ 2021.06.05

[BOJ/13913/Golang] 백준 13913 - 숨바꼭질 4

접근 방식 오랜만에 풀어본 BFS 문제입니다. 일반 숨바꼭질 문제와 똑같습니다만 추가로 이동 방법까지 출력해야 하는 문제입니다. 이동 방법을 구하는 문제라면 이전에도 살펴보았듯이 이전 부모의 이력을 계속 기록해놓았다가 마지막에 역순으로 출력하는 식으로 해결할 수 있습니다. 이 문제에서는 visited 를 확인하는 배열을 따로 두지 않았습니다. 이유는 부모 이력을 기록하는 배열에 이력이 기록된 상태라면 이미 방문한 노드임을 확신할 수 있기 때문입니다. BFS를 수행하는 과정은 쉬운 BFS 문제들과 거의 유사하기 때문에 코드를 보면서 이해하시는 편이 빠를 것이라 생각합니다. 개선 사항 func printRoute(S int) { if P[S] == -1 { fmt.Fprintf(w, "%d ", S) ret..

PS/BOJ 2021.06.02
반응형