coding-test

<백준> 2178 미로탐색 / C++ 풀이

도멩 2024. 1. 7. 16:11

중점:

1. bfs 알고리즘 사용

2. N, M 좌표까지 vis 값 +1


정답 코드:

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second

string board[105];
int vis[105][105];
int n, m;
int dx[] = {1, 0 , -1, 0};
int dy[] = {0, 1, 0, -1};

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m; //n, m값 입력 받음.

    for (int i = 0; i < n; i++){ //board 값 입력 받음.
        cin >> board[i];
    }

    vis[0][0] = 1;

    queue<pair<int, int> > Q;

    Q.push({0, 0});

    while (!Q.empty()) {
        pair<int, int> cur = Q.front();
        Q.pop();

        for (int dir = 0; dir < 4; dir++){
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];

            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(vis[nx][ny] || board[nx][ny] != '1') continue;

            vis[nx][ny] = vis[cur.X][cur.Y] + 1;
            Q.push({nx, ny});
        }
    }
    
    cout << vis[n - 1][m - 1];
}