그건 장난감이 아니라 돌이야

https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 하얀 방(1)과 검은 방(0)으로 구성된 1*1 크기의 방들이 n*n크기의 맵을 이루고 있다. 이때, (1, 1)에서 (n, n)까지 가고 싶은데 검은 방은 지나갈 수 없으므로 하얀 방으로 색을 바꾸고 지나가야 한다. 이때 검은 방의 색을 최소한의 횟수로 바꾸고 (n, n)에 도달하려면 몇 번 바꿀 수 있는지 알아보는 문제이다. 얼핏 보면 벽 부수고 지나가기 시리즈를 생각할 수 있는 문제이다. 하..

https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 공기구멍이 송송 뚫려있는 치즈가 있을 때, 바깥공기와 닿은 치즈 부분이 한 층씩 녹아내리는 상황을 시뮬레이션하는 문제이다. 일단 2차원 맵에서 탐색을 해야한다는 것을 봤을 때 직관적으로 BFS가 생각난다. 아니나 다를까 이 문제는 BFS를 사용해서 한 층씩 치즈의 겉을 녹여라! 라는 문제이다. 문제에서는 친절하게 맵의 가장자리는 무조건 공기로 채워져 있다는 제약조건을 준다. 만약 가장자리까지 치즈가 있을 ..