알고리즘/문제풀이 - 백준

백준 17142 연구소3

문제 : https://www.acmicpc.net/problem/17142 서론 DFS와 BFS를 둘 다 사용해서 구현하는데 시간이 오래걸렸음에도(약 2시간) 예상할 수 있는 반례를 예제로 주어서 비교적 쉽다는 느낌을 받았다. 아이디어 먼저 비활성 바이러스 중에 활성 바이러스 m개를 선택해서 선택된 m개를 큐에 넣고 BFS를 돌려야한다. 바이러스가 퍼지는건 시간을 체크해야하기 때문에 BFS를 사용해야한다. 문제에 나와있듯이 바이러스가 퍼질때마다(한칸씩 방문할때마다) 1초씩 증가하므로 현재 방문지 = 이전 방문지 +1 을 해주면 마지막 방문지는 최종 시간이 되므로 결과값으로 가져오면 된다. 결과값을 가져올때는 지도 전체를 방문해서 벽에 막혀 바이러스가 퍼질 수 없는 곳이 있는지 체크를 먼저 해야한다. 만..

2019. 9. 5. 21:40