티스토리 뷰
728x90
문제 링크
https://www.acmicpc.net/problem/15971
15971번: 두 로봇
2018년 강원도에서 새로운 동굴이 발견되었다. 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번 방, 2번 방, …, N번 방으로 부른다. 통로는 정확히 N-1개가 발견되었는데, 각각 서로 다른 두 방 사이를 연결시켜 주며 중간에 다른 통로와 이어지는 경우는 없다고 한다. 또한 이 통로들을 이용하여 임의의 두 방 사이를 이동하는 것이 가능하며, 임의의 두 방 사
www.acmicpc.net
두 로봇은 인접한 노드에 있으면 통신이 가능합니다.
풀이
1) 두 로봇 사이 최단 거리를 dfs로 구해줍니다.
2) 위에서 구한 최단거리에서, 두 로봇 사이의 경로에 포함된 간선 중 가중치가 가장 큰 간선의 거리를 빼줍니다.
풀이를 두 단계로 적어놨지만 사실 dfs 한 번으로 1), 2)를 동시에 구할 수 있습니다.
자세한 내용은 코드를 참고해주세용
정답 코드
728x90
'알고리즘 > 문제 풀이' 카테고리의 다른 글
| [BOJ] 백준 1726 로봇 (0) | 2019.12.14 |
|---|---|
| [BOJ] 백준 3649 로봇 프로젝트 (0) | 2019.10.15 |
| [BOJ] 백준 17141 연구소2, 17142 연구소 3 (0) | 2019.10.15 |
| [2019 숭고한 캠프] 백준 17392 우울한 방학 (1) | 2019.08.18 |
| [2019 SCCC] 백준 17131 여우가 정보섬에 올라온 이유 (0) | 2019.06.04 |
댓글