728x90
https://www.acmicpc.net/problem/14502
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크
www.acmicpc.net
문제해결
1. 데이터를 2차원배열에 입력받는다.
2. 재귀를 이용하여 모든 경우의 수의 놓일 수 있는 벽을 세운다.
3. 벽을 3개 세우면 bfs을 통해 바이러스를 퍼뜨린다.
4. 바이러스를 퍼뜨린 후 남아있는 안전구역을 센다.
5. 2~4번을 반복하면서 안전구역이 가장 많은 경우를 찾는다.
이 문제는 벽을 세우는게 가장 핵심 포인트다. 나도 처음에는 백트래킹을 잘 몰라서 못풀었는데 백준 문제 중에 N과M이라는 백트래킹 관련 문제가 있었는데 그 문제를 이해하고 풀어보니 쉽게 풀렸다 ㅎㅎ
코드
ide.goorm.io/shared_files/sksj0111_fcc7300b628df822a9245c8da79cea281604759862765
728x90
'그래프 이론 > BFS, DFS 알고리즘' 카테고리의 다른 글
[백준/C++][연결 요소의 개수(11724번)] (0) | 2020.12.01 |
---|---|
[백준/C++][인구이동(16234번)] (0) | 2020.11.28 |
[백준/C++][(1167번)트리의 지름] (0) | 2020.11.21 |
[백준/C++] 치즈(2638번) (0) | 2020.11.11 |
[백준]- 트리(1068번) c++ (0) | 2020.10.17 |