문제 14502번: 연구소 (acmicpc.net) 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 연구소 내 최대 안전구역을 확보하기 위해 3개의 벽을 어떻게 설치할지 결정하는 문제입니다. N x M 의 칸 중 3개를 선택하는 조합(combination)입니다. 다행히도 벽을 꼭 3개를 세워야 하므로 전체 경우의 수는 많지 않습니다. 그렇기 때문에 완전탐색으로 문제를 해결할 수 있습니다. 벽을 어떻게 세울지 결정하였다면 그래프 탐색 알고리즘을 이용하여 바이러스가 닿지 않는 안전구역의 칸 수를 확인해주면 됩니다. 완전..
그래프
문제 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 풀이 최단거리를 구하는 문제인데 출발점이 주어지지 않았습니다. 그렇다면 모든 노드에서 거리를 확인해보아야 하는데 이때 사용할 알고리즘은 플로이드-워셜 알고리즘이 적합해보입니다. 플로이드-워셜 알고리즘 설명 특별하게 이 문제에서는 출발점으로 다시 돌아오는 것까지 계산해야 합니다. 특정 노드까지의 거리를 구한 뒤 다시 출발점으로 돌아오는 경우까지 고려하여 최단 ..
문제 13460번: 구슬 탈출 2 (acmicpc.net) 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 풀이 십자 방향으로 구슬을 움직이며 도착지점까지의 최단거리를 찾는 문제입니다. 최단거리를 찾는 문제이므로 bfs 탐색을 통해 물제를 해결해 보겠습니다. 구현 문제와 살짝 짬뽕되어 문제의 조건도 많고 구현과정도 길어지지만 큰 알고리즘은 bfs 탐색으로 하나씩 정리해나가면 이해할 수 있습니다. 먼저 bfs 탐색 종료 조건부터 알아봅시다. 종료조건 1 - 구슬 ..
