-
백준 1261 (알고스팟)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 26. 19:15
https://www.acmicpc.net/problem/1261
해당 문제는 M * N 크기의 미로가 주어지며 (벽은 1 , 빈 공간 0) 해당 미로의 1 by 1 의 위치에서 N M 의 위치 까지 이동한다고 했을 때 가장 적은 수의 벽을 깨고 갈 수 있는 경우에 깬 벽의 횟수를 구하는 문제이다.
일반적인 Queue를 사용한 BFS탐색을 이용할 경우 결국 모든 경우를 모두 순회 해야 함으로 Queue 메모리 초과가 발생한다.
따라서 Deque 를 사용하여 이동하는 위치가 벽일 경우에는 qu의 뒤쪽에 Push 하여 우선순위를 낮추고 이동하는 위치가 빈 공간 일 경우에는 qu의 앞에 Push 하여 우선순위를 높이는 형태로 다음에 이동할 위치의 우선순위를 결정한다. 이렇게 Push 한 정보를 qu의 front 부터 pop하여 벽을 깨지 않는 경우먼저 탐색하면 된다.
#include <iostream> #include <deque> using namespace std; struct Node{ int y, x; int breakWall; }; int n, m; int checkY[4] = { 0, 0, +1, -1 }; int checkX[4] = { 1, -1, 0, 0 }; char map[101][101]; int visit[101][101]; int res = 0; void bfs(){ deque<Node> qu; qu.push_front({ 1, 1, 0 }); visit[1][1] = 1; while (!qu.empty()){ Node now = qu.front(); qu.pop_front(); for (int i = 0; i < 4; ++i){ int dy = now.y + checkY[i]; int dx = now.x + checkX[i]; if (dy <= 0 || dx <= 0 || dy > n || dx > m) continue; if (visit[dy][dx] == 1) continue; visit[dy][dx] = 1; if (dy == n && dx == m){ res = now.breakWall; return; } else if (map[dy][dx] == '0'){ // 벽이 아닐 경우 qu의 front에 Push qu.push_front({ dy, dx, now.breakWall }); } else if (map[dy][dx] == '1'){ // 벽일 경우 qu의 Back에 Push qu.push_back({ dy, dx, now.breakWall + 1 }); } } } return; } int main(){ //freopen_s(new FILE*, "tes.text", "r", stdin); cin >> m >> n; for (int i = 1; i <= n; ++i){ for (int j = 1; j <= m; ++j){ cin >> map[i][j]; } } bfs(); cout << res << endl; }
'컴퓨터 공학 기초 > 알고리즘 (BFS, DFS)' 카테고리의 다른 글
백준 2206 (벽 부수고 이동하기) (0) 2020.08.26 백준 13549 (숨바꼭질 3) (0) 2020.08.26 백준 2178 (미로 탐색) (0) 2020.08.24 백준 4963 (섬의 개수) (0) 2020.08.24 백준 2667 (단지번호붙이기) (0) 2020.08.24