알고스팟 문제 링크: https://algospot.com/judge/problem/read/GALLERY
algospot.com :: GALLERY
감시 카메라 설치 문제 정보 문제 전세계의 유명한 인물화들을 모아 두는 미술관에 괴도 콩의 도전장이 날아들었습니다. 2022년 2월 2일을 기념하여, 미술관에 전시된 인물화 중 하나의 얼굴을 모
algospot.com
그래프에서 인접한 노드중에 적어도 하나의 노드에 감시카메라가 설치되어있지 않으면 해당 노드에 감시카메라를 설치 해야한다.
이때 필요한 최소한의 감시카메라의 개수를 구하는 문제이다.
문제 조건에서 "미술관은 한 번 관람한 갤러리를 다시 가기 위해서는 이전에 지나왔던 복도를 반드시 한 번 지나야 하는 구조로 설계되어 있으며"가 있으므로 해당 그래프는 트리형태임을 알 수 있다.
따라서 자손 노드들의 상태를 보고 하나라도 UNWATCHED상태라면 해당 노드에 감시카메라를 설치하는 알고리즘을 사용할 수 있다.
또한 "모든 갤러리가 서로 연결되어 있지 않을 수도 있습니다."라는 조건이 있으므로 모든 노드가 방문되었는지 확인하는 절차도 필요하다.
코드 원본: https://github.com/sbl133/JongmanBook/blob/main/28.%20DFS/GALLERY.cpp
GitHub - sbl133/JongmanBook
Contribute to sbl133/JongmanBook development by creating an account on GitHub.
github.com
댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!
reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2
'Algorithm > algospot' 카테고리의 다른 글
| algospot 소방차(문제ID: FIRETRUCKS) c++ (0) | 2022.03.08 |
|---|---|
| algospot 회의실 배정(문제 ID: MEETINGROOM) c++ (0) | 2022.03.05 |
| algospot 보안종결자(문제 ID: NH) c++ (0) | 2022.03.01 |
| algospot 안녕히, 그리고 물고기는 고마웠어요!(문제 ID: SOLONG) c++ (0) | 2021.12.22 |
| algospot 신호 라우팅 (문제 ID: ROUTING) c++ (0) | 2021.10.29 |