백준 15591

[BJ] 백준 15591 MooTube (Silver) (JAVA)

문제 https://www.acmicpc.net/problem/15591 풀이 방법 이 문제는 시간초과가 관건인 문제였다. 처음에는 인접 행렬로 풀이를 하려고 했는데 계속해서 시간초과가 발생했다. 그래서 도저히 시간을 단축시킬 방법이 생각이 안나서 찾아봤더니 인접 리스트를 사용하면 풀리는 문제였다. 풀이 과정은 다음과 같다. 1. 인접 리스트를 생성해서 인접한 정점들과 USADO 값을 저장해준다. 2. v번째 정점으로부터 BFS를 시작한다. 3. queue에서 poll를 한 정점(n)과 인접하고(USADO값이 존재) 방문하지 않은 정점들만 탐색 후보가 된다. 4. n번 정점과 탐색 후보 사이의 USADO 값이 k이상인 경우에만 que에 넣어준다. 5. 그리고 cnt도 하나 증가해준다. 왜냐면 visit배..