[백준 / BOJ] 6118 숨바꼭질

문제

출처 : www.acmicpc.net/problem/6118

6118번: 숨바꼭질

N개의 정점이 있고, 각 정점의 연결관계를 M번 입력받는다.

이때 1번정점에서 가장 멀리 떨어져있는 정점과, 정점의 거리, 수를 찾는 문제다.

 

풀이

1년전에 틀렸었던 문제다.

음수간선이 존재하지않으니 DFS와 다익스트라를 이용해 풀면 되겠다고 생각했는데, DFS로 풀었더니 시간초과가 나왔다.

(이 문제에선 깊이 우선탐색의 경우 최악의 경우 모든 경우를 다 봐줄수도 있어서 그런것 같다)

다익을 사용하는 이유는 어쨋든 1번노드에서 모든 노드까지의 최소 거리를 구해줘야하기 때문이다.

 

DFS를 BFS로 고쳐서 풀었고 맞았습니다를 받았다.

 

1. arr배열을 선언해 각 정점의 떨어진 정도를 저장한다. (다익을 사용할것이므로 편의를위해 모든 정점을 21억으로 초기화 해줬다.)

2. 1번정점부터 BFS를 돌리면서 인접한 노드를 순서대로 봐준다. 이때, 1번정점 부터의 거리가 저장된 거리보다 크다면 더이상 해당노드로 가주지 않는다. 

3. 모든 노드의 최소거리를 구해주고 arr배열을 1 ~ N까지 반복해주며 가장 멀리 떨어져있는 정점과, 정점의 거리, 수를 찾아 주면된다.

 

천천히 지금까지 배운 알고리즘을 블로그에 올려야겠다.....

소스코드

https://github.com/devxb/JJUNalgo/blob/master/6118%20%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88/main.cpp

devxb/JJUNalgo