BFS

백준 14938번 서강그라운드 문제 파이썬 풀이입니다. 14938번: 서강그라운드 (acmicpc.net) 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 2017 SPC에 출제 되었던 문제입니다. 한 노드에서 각 노드까지의 최단거리를 알아야하기에, 최단 경로 탐색 알고리즘인 다익스트라(Dijkstra) 알고리즘으로 풀 수 있는 문제입니다. 다익스트라 알고리즘은 N*logN 시간복잡도를 가지게 되는데, 총 N개의 노드를 시작점으로 탐색해야기에 N개 * N*logN 의 시간복잡도를 필요로 하고, N은 최대 100이기에..

백준 14217번 그래프 탐색 1 문제 파이썬 풀이입니다. https://www.acmicpc.net/problem/14217 14217번: 그래프 탐색 남규나라의 왕 zych는 도로 정비 계획을 발표하였다. 두 도시를 잇는 도로들을 새로 만들거나, 안전상의 문제로 도로를 없애기도 할 계획이다. 도로 정비 계획은 두 도시와, 만들건지, 없앨건지에 www.acmicpc.net 비슷한 버전의 '그래프 탐색 2'를 풀었다면 아주쉽게 풀 수 있는 문제였습니다. 도로가 사라졌을 때는 원래 최단 거리였던 길이 없어진 경우도 있기 때문에 매번 distance 배열을 초기화 시켜야 한다는 사실만 주의하면 이전 버전 문제와 거의 유사했습니다. 주요코드 line 18 ~ 33 : 1부터 시작해서 각 node까지 BFS를 ..

백준 14218번 그래프 탐색 2 문제 파이썬 풀이입니다. https://www.acmicpc.net/problem/14218 14218번: 그래프 탐색 2 첫째 줄에는 도시의 개수 n,도로의 개수 m이 주어진다. 다음 m개의 줄에는 두 도시가 주어진다.(2≤n≤1,000,1≤m≤100,000) 다음 줄에는 도로 정비 계획에 들어가 있는 도로의 수 q가 주어지고, 다음 q www.acmicpc.net 실버1 치고는 널널한? 문제였습니다. N이 1000이라 최적화없이 대충짜도 어째저째 돌아가는 문제였습니다. INF로 초기화 시킨 distance 배열을 만들어 두고, 테스트가 들어올 때마다 node 1에서 시작해서 BFS를 돌며 최소거리로 갱신시켜 나가는 방식으로 해결할 수 있었습니다. 주요코드 line 1..