[백준 / BOJ] 1261 알고스팟

문제

출처 : www.acmicpc.net/problem/1261

1261번: 알고스팟

N*M크기의 미로가 주어진다.

미로는 0,1로 주어지며 0은 빈 방 1은 벽이다.

알고스팟 운영진이 (1,1)에서 (N,M)으로 이동할때까지 총 몇개의 벽을 부숴야하는지 구하는 문제이다.

 

풀이

다익스트라를 이용해서 푸는문제다.

벽을 부순 횟수를 저장하는 배열을 만들고 배열의 모든칸을 최댓값으로 초기화 시켜준다. (나는 1000000000로 초기화 해줬음)

위 배열에는 해당 (Y,X) 지점 까지 갔을때 벽을 최소로 이동한 횟수를 저장해줄것이다. 

ex) check[Y][X] = 1 (해당 지점까지 1번의 벽을 부수고 이동가능)

 

BFS를 이용해 탐색하면서 해당 지점까지 이동했을때 벽을 부순 횟수가 배열에있는값 보다 작다면 더 이상 이동하지않고, 아니라면 배열을 업데이트 해주고 이동시킨다.

 

소스코드

https://github.com/devxb/JJUNalgo/tree/master/1261%20%EC%95%8C%EA%B3%A0%EC%8A%A4%ED%8C%9F

devxb/JJUNalgo