-
(백준 2178번 미로 탐색 C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 3PROGRAMMING/알고리즘 2024. 4. 9. 07:41
bfs 문제도 슬슬 익숙해지는 것 같다! 최단 거리를 구할 때는 역시 bfs!
백준 2178번
https://www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
#include <iostream> #include <vector> #include <queue> #include <string> using namespace std; constexpr int MAX_N = 101; int arr[MAX_N][MAX_N] = { 0 }; bool isInside(int x, int y, int N, int M) { if (x < 0 || y < 0 || x >= N || y >= M) return false; return true; } int bfs(int N, int M) { int dir_x[4] = { -1, 0, 1, 0 }; int dir_y[4] = { 0, 1, 0, -1 }; queue<pair<int, int>> Q; Q.push(make_pair(0, 0)); arr[0][0] = 0; int level = 1; while (!Q.empty()) { int qsize = Q.size(); for (int i = 0; i < qsize; i++) { int currX = Q.front().first; int currY = Q.front().second; arr[currX][currY] = 0; Q.pop(); for (int j = 0; j < 4; j++) { int nextX = currX + dir_x[j]; int nextY = currY + dir_y[j]; if (isInside(nextX, nextY, N, M) && arr[nextX][nextY] == 1) { Q.push(make_pair(nextX, nextY)); arr[nextX][nextY] = 0; if (nextX == N - 1 && nextY == M - 1) return ++level; } } } level++; } return level; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, M; cin >> N >> M; for (int i = 0; i < N; i++) { string st; cin >> st; for (int j = 0; j < M; j++) { arr[i][j] = st[j] - '0'; } } cout << bfs(N, M) << endl; return 0; }
'PROGRAMMING > 알고리즘' 카테고리의 다른 글
(백준 5014번 스타트링크 C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 5 (0) 2024.04.10 (백준 1260번 DFS와 BFS C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 4 (0) 2024.04.10 (백준 7562번 나이트의 이동 C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 27 (0) 2024.04.08 (백준 2644번 촌수계산 C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 1 (0) 2024.04.08 (백준 11724번 연결 요소의 개수 C++) 라이님 블로그 대회 알고리즘 따라잡기 8) DFS 1 (0) 2024.04.04