Algorithm/BFS
-
[백준 14502번] 연구소(자바)Algorithm/BFS 2022. 5. 14. 18:07
백준알고리즘 14502번 : 연구소 (Solved.ac 난이도 Gold5) https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 벽을 세우는 경우의 수만큼 BFS를 돌려보는 방식으로 풀 수 있었다. 우리는 배열에서 0을 갖고있는 위치 3군데를 1로 바꾸어 벽으로 만들 수 있다. 3중 for문을 돌려서 0 3개를 1로 바꾼 뒤, BFS를 적용하여 바이러스를 침투시켜본다. 그 후에 남은 0의 개수를 count하면 해당 case의 안전 영역 크기를 도출할 수 있다. ..
-
[백준 7576번] 토마토 (자바)Algorithm/BFS 2022. 5. 13. 21:46
백준알고리즘 7576번 : 토마토 (Solved.ac 난이도 Gold5) https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 전형적인 BFS문제이다만.. 나는 DFS로 몇 번 시도해보고서야 완전 틀린 해석이었다는 걸 깨달았다. DFS로 하게되었을 때의 문제점이라면, 각 구역마다 한번의 탐색으로 끝내도 될 것을 계속 접근하여 비효율적으로 만드는 것이다. 잘 익은 토마토를 기준으로 너비 우선탐색으로 뻗어나가면, 애초에 검증이 많이 필요..