삼성 기출 문제집 - 백준 14502 연구소 문제 풀기
https://www.acmicpc.net/problem/14502
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다.
www.acmicpc.net
소요 시간 : 1시간 가량
풀이 : 완전탐색 / BFS
바이러스와 벽을 세울 수 있는 것을 ArrayList에 추가한다.
1. 3중 for문을 통해서 3개를 추출(벽 세울 수 있는 곳)
2. 추출한 인덱스들을 통해 copyMap에다가 벽을 세운 뒤, Virus들에 대해서 모두 BFS를 돌리면서, 값을 2로 변경
3. 끝난 다음, copyMap에 0의 개수와 max값을 구해서 max값을 찾음.
이 과정을 1로 돌아간 다음 계속 돌림. 1의 for문이 끝나면 실행이 끝나고 max값을 출력하도록 구현.
'알고리즘' 카테고리의 다른 글
| 백준 14501 퇴사 - JAVA (0) | 2020.03.04 |
|---|---|
| 백준 15686 (BOJ 15686) 치킨배달 - JAVA (0) | 2020.03.03 |
| [백준 13458 - JAVA] 시험감독 (0) | 2020.03.01 |
| [JAVA 백준 16236] - 아기상어 (0) | 2020.02.27 |
| [삼성 SW 역량 테스트 기출 문제집] 백준 3190 뱀 (0) | 2020.02.26 |