[백준2178]미로 탐색 c++

문제링크 https://www.acmicpc.net/problem/2178

int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };

먼저 상하좌우를 탐색하여줄 배열을 선언합니다.
이렇게 선언함으로써 후에 for문을 통하여
현재 위치+ 위,아래,좌,우를 탐색 할 수 있습니다.

int arr[101][101];
bool visitied[101][101] = { false };
int n, m;

전역변수로 확인 배열과 그래프 배열을 선언합니다.

cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++)
        {
            arr[i][j] = s[j] - '0';
        }
    }

n,m을 입력받고 스트링타입으로 문자를 받아서
arr에 넣어줍니다. 여기서 char이므로 아스키코드 0값을 뺀 값을 넣어줍니다.

void bfs(int i, int j)

매개변수로 i j를 입력받고 bfs이므로 void 형을
선언하여 줍니다.

 queue<pair<int, int>>myqueue;
    myqueue.push(make_pair(i, j));

다음으로 큐 형태를 pair로 선언
매개변수 i,j를(0,0)을 큐에 넣어줍니다.

 while (myqueue.empty())
    {
        int a, b;
        a = myqueue.front().first;
        b = myqueue.front().second;
        myqueue.pop();
        visitied[i][j] = true;

이제 큐가 빌때까지 while을 실행하여 줍니다
일반 bfs와 다른점은
a,b로 나눠서 데이터를 꺼낸다는 점 입니다.

 for (int k = 0; j < 4; k++)
        {
            int nextX = a + dx[k];
            int nexty = a + dy[k];

이제는 앞서 위에 선언했던 좌표 배열로
현재의 좌표 a,b에 for문으로 위 아래 옆으로 돌려주며 탐색을 합니다.

if (nextX >= 0 && nexty >= 0 && nextX < n && nexty < m)
       {
          if (arr[nextX][nexty] != 0 && !visitied[nextX][nexty])
             {
               visitied[nextX][nexty] = true;
               arr[nextX][nexty] = arr[a][b] + 1;
               myqueue.push(make_pair(nextX, nexty));
                }코드를 입력하세요

첫번째 if는 유효한 좌표를 검사하는 조건문입니다.
nextx와 nexty가 당연히 0보다 작으면 안되고
n과 m보다 작은건 n,m일시 종료이기 때문입니다..

그 다음 조건문은 이미 방문한 적이 있는가에 대한 일반 bfs적인 검사입니다.
나머지도 비슷합니다.

arr[nextX][nexty] = arr[a][b] + 1;

이부분이 이제 값을 1로 업데이트 해주는 부분이 추가되었습니다.
이렇게 n,m까지 가서 커진 값이 답이 되어집니다.

#include <iostream>
#include <queue>
using namespace std;

int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
int arr[101][101];
bool visited[101][101] = { false };
int N, M;

void BFS(int i, int j) {
    queue<pair<int, int>> myqueue;
    myqueue.push(make_pair(i, j));
    while (!myqueue.empty()) {
     
        int a = myqueue.front().first;
        int b = myqueue.front().second;
        myqueue.pop();
        visited[i][j] = true;
        for (int k = 0; k < 4; k++) {
            int nextx = a + dx[k];
            int nexty = b + dy[k];
            if (nextx >= 0 && nexty >= 0 && nextx < N && nexty < M) {
                if (arr[nextx][nexty] != 0 && !visited[nextx][nexty]) {
                    visited[nextx][nexty] = true;
                    arr[nextx][nexty] = arr[a][b] + 1;
                    myqueue.push(make_pair(nextx, nexty));
                }
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < M; j++) {
            arr[i][j] = s[j] - '0';
        }
    }

    BFS(0, 0);
    cout << arr[N - 1][M - 1] << "\n";
}

전체 코드입니다.

결국은 1로된부분을 연결된 그래프라 생각하여
1씩 추가하며 계속 탐색해나가며 n,m에 도착하고
도착한 시점의 값이 답이 됩니다.