문제 링크https://www.acmicpc.net/problem/17086 문제 요약임의의 점 \((i, j)\)의 안전거리는 \((i, j)\)에서 시작해서 아기 상어가 있는 곳까지의 최소 거리를 의미한다. 여기서 거리는 인접한 8방향(상하좌우 및 대각선)으로 이동한 칸 수로 계산한다. 격자판 위의 모든 점들 중에서 안전거리가 최대인 값을 찾아 출력하는 것이 이 문제의 목표이다. 문제 풀이기본적인 풀이너비 우선 탐색(이하 BFS)을 이용하면 임의의 점 \((i, j)\)에서 가장 가까운 아기 상어까지의 거리를 계산할 수 있다. 그리고 N과 M의 크기가 작으므로 모든 점들에 대해서 BFS를 한 번씩 돌려도 제한시간 내에 충분히 답을 구할 수 있다. 아래 더보기 버튼을 누르면 이 방법으로 푼 코드를 볼..
문제 링크https://www.acmicpc.net/problem/9376 문제 요약두 죄수 A, B가 최소한의 문을 열어 감옥에서 탈출하려고 한다. 한 죄수가 문을 열면, 그 문은 계속 열려 있어서 다른 죄수도 그 문을 이용할 수 있다.(원래 문제에서는 감옥 밖에 있는 상근이가 특별한 기술을 이용해 문을 열어준다고 되어 있지만, 문제를 더 쉽게 이해할 수 있게 내용을 살짝 바꿨다.) 문제 풀이가장 먼저 떠오르는 생각은 두 죄수의 상태를 동시에 관리하는 것이다. 하지만 죄수가 있을 수 있는 장소는 1만 곳이고, 이를 두 죄수의 상태로 표현하면 1억 가지의 경우의 수가 생긴다. 여기에 탈출을 위해 이용한 문의 개수까지 고려한다면 이 방법은 문제를 제한 시간 내에 풀 수 있는 방법이 아니다. 경우의 수 나누..
