[C++]백준 25416번 빠른 숫자 탐색

📌문제 링크

---

https://www.acmicpc.net/problem/25416

📌문제 설명

---

5x5 격자에서 시작 좌표와 목표 좌표를 입력받아 BFS를 사용해 최단 경로를 찾는 문제를 해결합니다. mp는 격자의 상태를 저장하며, visited는 방문 여부를 기록합니다. 시작 위치에서 BFS로 탐색하며, 장애물(-1)을 피하고 목표 지점(1)에 도달하면 이동 횟수를 출력합니다. 목표에 도달하지 못하면 -1을 출력합니다.

📌코드

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
bool visited[6][6];
int mp[6][6], xx, yy;
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};

struct comp{
    int x, y, cnt;
};

void input(){
    for(int i = 0; i < 5; i++){
        for(int j = 0; j < 5; j++){
            cin >> mp[i][j];
        }
    }
    cin >> xx >> yy;
}

void bfs(){
    queue<comp> q;
    q.push({xx, yy, 0});
    visited[xx][yy] = true;
    while(!q.empty()){
        auto [x, y, cnt] = q.front();
        q.pop();
        if(mp[x][y] == 1){
            cout << cnt;
            return;
        }
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 0 || nx >= 5 || ny < 0 || ny >= 5 || visited[nx][ny]){
                continue;
            }
            if(mp[nx][ny] == -1){
                continue;
            }
            visited[nx][ny] = true;
            q.push({nx, ny, cnt + 1});
        }
    }
    cout << -1;
}

void solve(){
    input();
    bfs();
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}