목록2025/03/07 (1)

넘치게 채우기

[BOJ] 18231 - 파괴된 도시

https://www.acmicpc.net/problem/18231BOJ - 파괴된 도시문제 유형: 해 구성하기, 그래프 이론문제 난이도: Gold V시간 제한: 2초메모리 제한: 512MB 문제저명한 역사학자 지수는 오래된 지도 한 장을 주웠다. 이 지도는 N개의 도시와 M개의 도로로 이루어져 있으며, 각 도시는 1부터 N까지 하나씩 번호가 매겨져있다. 지도에는 불에 탄 모습의 K개의 도시가 있었는데, 지수는 이 지도가 전쟁 당시 파괴된 도시를 표시한 지도임을 알아차렸다. 연구한 바에 의하면, 어떤 도시에 그 당시 사용했던 폭탄을 떨어뜨리면 이 도시를 포함하여 인접한 도시들은 전부 파괴된다고 한다.지수는 이 사실을 토대로 당시 폭탄이 떨어진 지점들을 알아내기 위해 우리를 초대했다. 우리는 폭탄이 떨어진..
PS/BOJ 2025. 3. 7. 10:19
이전 Prev 1 Next 다음