[BOJ]1261번: 알고스팟

 

문제: https://www.acmicpc.net/problem/1261

---

다익스트라 문제입니다. 

 

단순 BFS로 벽을 뚫을 때마다 방문표시를한다면 visit[10000][100][100]으로 메모리 초과가 날 것입니다.

 

중복해서 방문을 하지 않도록 조건을 걸어보자면,

 

visit[y][x] : (y,x) 칸을 방문했을 때 부순 벽의 갯수

 

위와 같이 방문배열을 정의하고 now.BROEKN < visit[y][x].BROKEN 조건일 때만 방문할 수 있도록 갱신해주면

최소한으로 벽을 부순 상태로만 계속 탐색을 할 수 있습니다.

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ1261.cc