알고리즘/너비 우선 탐색(bfs)
[Python]1216-백준-알고스팟
1. 문제 출처 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 2. 풀이 BFS를 이용하지만 벽을 부수는 경우가 있기 때문에 데이크스트라 알고리즘도 같이 이용해야 한다. 벽부시는 것을 가중치로 두고 만약 벽을 부수지 않고 이동한다면, 가중치를 더해주지 않는 것이 필요하다. 다음과 같이 진행된다. 1. 상하좌우 중 범위를 나가지 않는 곳으로 이동 2. 해당 이동좌표에 벽이 있다면 전 가중치+1 을 해주고 append를 통..
