-
[BOJ-18231]파괴된 도시백준알고리즘 2020. 2. 9. 16:26
https://www.acmicpc.net/problem/18231
18231번: 파괴된 도시
저명한 역사학자 지수는 오래된 지도 한 장을 주웠다. 이 지도는 N개의 도시와 M개의 도로로 이루어져 있으며, 각 도시는 1부터 N까지 하나씩 번호가 매겨져있다. 지도에는 불에 탄 모습의 K개의 도시가 있었는데, 지수는 이 지도가 전쟁 당시 파괴된 도시를 표시한 지도임을 알아차렸다. 연구한 바에 의하면, 어떤 도시에 그 당시 사용했던 폭탄을 떨어뜨리면 이 도시를 포함하여 인접한 도시들은 전부 파괴된다고 한다. 지수는 이 사실을 토대로 당시 폭탄이 떨어진
www.acmicpc.net
우리학교 연말 페스티벌 문제였다고한다.
처음에는 DFS를 생각했으나, 구현하게됬을 경우, Deepth가 굉장히 커져서
백퍼센트 시간초과가 날것을 생각할수있다. (노드의 크기는 그닥 안커보이는데.. 간선이 어마무시하다.)
마찬가지로, 일반 BFS를 쓴다고치면, 메모리초과가 날확률이 높다고 생각했다.
전략은 다음과같다.
파괴되어있는 도시를 중심으로, 파괴되지 않은 도시를 이웃으로 가지고있는 도시는 폭탄이 떨어진 도시에서 제외한다.
그리고 그것을 기준으로, 폭탄이 떨어지기에 적합한 도시를 정의할수있고,
이러한 도시를 답으로 도출한다.
의 과정이 되겠다.
'백준알고리즘' 카테고리의 다른 글
[BOJ - 17136]색종이 붙이기 (0) 2020.02.09 [BOJ-17837]새로운 게임2 (0) 2020.02.09 [BOJ-17135]캐슬디펜스 (0) 2020.02.09 [BOJ18235]지금 만나러 갑니다 (0) 2020.02.07 [ BOJ 16985 ] Maaaaaaaaaze (0) 2020.02.06