미로찾기 + bfs 역추적

#include <iostream>

#include <vector>

#include <iostream>

#include <queue>

using namespace std;

int N, M, K;

int m[101][101];

int dp[101][101];

bool visit[101][101];

int bx[4] = {1, 0, -1, 0};

int by[4] = {0, 1, 0, -1};

vector<pair<int, int>> trace;

pair<int, int> p[101][101];

void bfs()

{

    queue<pair<int, int>> q;

    q.push({0, 0});

    while (!q.empty())

    {

        int ny = q.front().first;

        int nx = q.front().second;

        q.pop();

        for (int i = 0; i < 4; i++)

        {

            int dy = ny + by[i];

            int dx = nx + bx[i];

            if(dy<0) dy=N

            if (dy < 0 || dx < 0 || dy >= N || dx >= M)

                continue;

            if (m[dy][dx] == 0)

                continue;

            if (visit[dy][dx])

                continue;

            visit[dy][dx] = true;

            dp[dy][dx] = dp[ny][nx] + 1;

            q.push({dy, dx});

            p[dy][dx] = {ny, nx};

        }

    }

}

int main()

{

    cin >> N >> M;

    for (int i = 0; i < N; i++)

    {

        string s;

        cin >> s;

        for (int j = 0; j < s.size(); j++)

            m[i][j] = s[j] - '0';

    }

    dp[0][0] = 1;

    bfs();

    vector<pair<int, int>> p2;

    int curx = N - 1, cury = M - 1;

    while (true)

    {

        p2.push_back(make_pair(curx, cury));

        if (curx == 0 && cury == 0)

            break;

        int nx = p[curx][cury].first;

        int ny = p[curx][cury].second;

        curx = nx;

        cury = ny;

    }

    cout << "Print Trace\n";

    for (int i = p2.size() - 1; i >= 0; i--)

    {

        printf("(%d, %d)\n", p2[i].first, p2[i].second);

    }

    cout << dp[N - 1][M - 1] << "\n";

}