그래프탐색2 BOJ 14502 - 연구소 14502번: 연구소 (acmicpc.net) 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 이번 문제는 DFS와 브루트 포스를 이용하여 풀 수 있는 문제이다. 실행시간도 2초라 널널할 것 같아 다음과 같이 풀었다. 알고리즘은 다음과 같다. 1. 빈 칸(0) 중 3곳을 골라 벽(1)을 세운다. 2. 벽을 세운 상태에서, 바이러스(2)들을 그래프탐색 시키며 지나간곳을 체크한다. 3. 바이러스가 지나가지 않았고, 벽이 아닌 곳의 수가 가장 큰 값을 구한다. 간단하게 해결할 수 있는 문제이다. visited[10][10]을 이.. 2024. 3. 12. BOJ 2206 - 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 1차 시도 부수는 경우와 부수지 않는 경우 총 두가지의 경로가 존재한다. 따라서, 이를 해결하기 위해 부수는 경우를 이차원 배열을 이용하여 저장하려고 시도하였다. broken[][] map[][] chk[][] 그러나 이에 대한 문제가 존재한다. 만약 벽을 하나도 부수지 않는 경우에 이를 이용하면, 도달하지 못한다는 결과가 도출된다. 이런 문제가 발생하는 이유는 벽을 부순.. 2024. 3. 5. 이전 1 다음
