1261번: 알고스팟 www.acmicpc.net 이 문제는 미로가 주어질 때 맨 왼쪽 위 지점(좌표로 치면 (1, 1) 지점)에서 출발해 맨 오른쪽 아래 지점(좌표로 치면 (N, M) 지점)으로 이동하기 위해서 최소 몇 개의 벽을 부수어야 하는지를 구하는 문제이다. 우선 벽을 부술 수 없는 경우에는 (1, 1) 지점에서 (N, M) 지점으로 가는 최단 경로를 찾기 위해 BFS, 즉 너비 우선 탐색을 이용했다. 그러므로 벽을 최대한 덜 부수기 위해서, 즉 최대한 벽이 없는 경로를 따라가기 위해서 BFS를 이용한다. 여기에 더해, 벽을 부수는 경우 역시 고려해야 하는데, 여기서는 dynamic programming을 활용한다. 미로 내 각 좌표마다 그 좌표까지 도달하기 위해 부숴야 하는 벽의 갯수의 최솟값..
