<Baekjoon> #2206 BFS_벽 부수고 이동하기 c++
#2206 벽 부수고 이동하기
#1450 연구소 문제와 비슷해서 그때 풀었던 것과 비슷하게 풀었는데 시간 초과가 났다.
풀이1
- 벽은 부수거나, 1개만 부수거나이므로 처음에는 벽을 부수지 않았을 때 주어진
map
그대로 해서distance
를 구한다
- 다음
map
의 모든 정점을 순회하면서WALL==1
일 경우 해당 부분을PATH=0
으로 바꾸어주고bfs
탐색 후 다시WALL=1
로 바꾸어 준다. (탐색을 할 때마다 최소distance
를 갱신해준다)
- 참고로 처음
map
을 받을 때 엔터로 하나씩 띄우면서 받는줄 알아서 잘못 짰다. 아래 코드는 테스트 케이스는 통과했지만 백준에서 통과는 안 됐다
#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; const int MAX = 1001; int n, m; int dy[4] = { 0,0,1,-1 }; int dx[4] = { 1,-1, 0,0 }; int dist[MAX][MAX]; int minDist = 0x7fffffff; void bfs(vector<vector<int>> &map) { queue<pair<int, int>> q; q.push(make_pair(1, 1)); dist[1][1] = 1; while (!q.empty()) { int cur_y = q.front().first; int cur_x = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int nx_y = cur_y + dy[i]; int nx_x = cur_x + dx[i]; if (nx_y <= 0 || nx_x <= 0 || nx_y > n || nx_x > m) continue; if (dist[nx_y][nx_x] == 0 && map[nx_y][nx_x]==0) { q.push(make_pair(nx_y, nx_x)); dist[nx_y][nx_x] = dist[cur_y][cur_x] + 1; } } } if (dist[n][m]!=0) minDist = min(minDist, dist[n][m]); } int main() { cin >> n >> m; vector<vector<int>> map(n+1, vector<int>(m+1)); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> map[i][j]; memset(dist, 0, sizeof(dist)); bfs(map); memset(dist, 0, sizeof(dist)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (map[i][j] == 1) { map[i][j] = 0; bfs(map); memset(dist, 0, sizeof(dist)); map[i][j] = 1; } } } if (minDist == 0x7fffffff) cout << -1 << endl; else cout << minDist << endl; return 0; }
풀이2
queue<pair<pair<int, int>, pair<int, int>>> q
를 두어 처음 한 쌍은(y,x)
로 현재 좌표를 뜯하고, 다음 쌍은(break-벽을 부순 횟수 0 or 1, count-distance)
이다.
visited[][][2]
로 만들고visited[y][x][0]
는 벽을 한 번도 부수지 않았을 때 좌표(y,x)
방문 여부,visited[y][x][1]
는 벽을 한 번 부쉈을 때 좌표(y,x)
방문 여부를 나타낸다
- 다음 위치가
WALL==1
이고, 벽을 한 번도 부순 적이 없다면(break==0)
벽을 부수어 이 지점을 방문한다if (map[nx_y][nx_x] == WALL && brk==0) { visited[nx_y][nx_x][brk + 1] = true; q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk+1, cnt+1))); }
- 다음 위치가
PATH==0
이고, 이 점을 방문한 적이 없다면 이 지점을 방문한다else if (map[nx_y][nx_x] == PATH && visited[nx_y][nx_x][brk] == false) { visited[nx_y][nx_x][brk] = true; q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk, cnt + 1))); }
#include <iostream> #include <queue> #include <vector> using namespace std; const int MAX = 1000; const int WALL = 1; const int PATH = 0; vector<vector<int>> map; int visited[MAX][MAX][2]; int n, m; int dy[4] = { 0,0,1,-1 }; int dx[4] = { 1,-1,0,0 }; int bfs() { queue<pair<pair<int, int>, pair<int, int>>> q; q.push(make_pair(make_pair(0, 0), make_pair(0, 1))); visited[0][0][0] = true; while (!q.empty()) { int cur_y = q.front().first.first; int cur_x = q.front().first.second; int brk = q.front().second.first; int cnt = q.front().second.second; q.pop(); if (cur_y == n - 1 && cur_x == m - 1) return cnt; for (int i = 0; i < 4; i++) { int nx_y = cur_y + dy[i]; int nx_x = cur_x + dx[i]; if (nx_y < 0 || nx_x < 0 || nx_y >= n || nx_x >= m) continue; if (map[nx_y][nx_x] == WALL && brk==0) { visited[nx_y][nx_x][brk + 1] = true; q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk+1, cnt+1))); } else if (map[nx_y][nx_x] == PATH && visited[nx_y][nx_x][brk] == false) { visited[nx_y][nx_x][brk] = true; q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk, cnt + 1))); } } } return -1; } int main() { cin >> n >> m; map = vector<vector<int>> (n, vector<int > (m)); for (int i = 0; i < n; i++) { string tmp; cin >> tmp; for (int j = 0; j < m; j++) { int tmp2 = tmp[j] - '0'; map[i][j] = tmp2; } } cout << bfs() << endl; return 0; }
Author And Source
이 문제에 관하여(<Baekjoon> #2206 BFS_벽 부수고 이동하기 c++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmy/Baekjoon-2206-BFS벽-부수고-이동하기-c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)