주난의 난

1을 만나기 전까지 계속 탐색할 수 있도록 BFS말고 DFS를 사용해서 풀었다.

처음에 문제 딱보고 아 BFS네 했다가 예시를 다시 보고 다시 로직을 수정하며 구현을 함.

queue를 두개를 사용해서 0을 담을 q1, 1을 담을 q2 나누어서

1이나오면 멈췄다가 q1 = q2이런식으로 바꿔치기 해준다.

기존의 BFS로는 풀 수 없고 BFS의 queue를 두개를 사용을 하면된다.

1인 경우를 담을 q, 0인 경우를 담을 q

1을 만나면 cnt를 올려준다.

내 풀이

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#define endl "\n"
#define MAX 305
int n, m, startX, startY, destX, destY, ret = 0;
char arr[MAX][MAX];
int visited[MAX][MAX];
int dy[4] = {0, 1, 0, -1}, dx[4] = {-1, 0, 1, 0};
vector<pair<int, int>> vec;

bool Cango(int y, int x)
{
    if (y < 0 || x < 0 || y >= n || x >= m) return false;
    return true;
}

void DFS(int y, int x, int jumpCnt)
{
    for (int i = 0; i < 4; ++i)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];

        // 범위 체크
        if (Cango(ny, nx) == false) continue;

        // 방문한 곳인지 아닌지 체크
        if (visited[ny][nx]) continue;

        if (arr[ny][nx] == '1')
        {
            visited[ny][nx] = 1;
            vec.push_back(pair<int, int>({ny, nx}));
        }
        else if (arr[ny][nx] == '0')
        {
            visited[ny][nx] = 1;
            DFS(ny, nx, jumpCnt);
        }
        else if (arr[ny][nx] == '#')
        {
            ret = jumpCnt;
            return;
        }    
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> m;
    cin >> startX >> startY >> destX >> destY;
    
    for (int y = 0; y < n; ++y)
    {
        for (int x = 0; x < m; ++x)
        {
            cin >> arr[y][x];
            if (arr[y][x] == '*')
            {
                startY = y; startX = x;
            }
            else if (arr[y][x] == '#')
            {
                destY = y; destX = x;
            }
        }
    }

    visited[startY][startX] = 1;
    int jump = 0;

    while (1)
    {
        ++jump;
        DFS(startY, startX, jump);
        if (ret != 0)
        {
            break;
        }
        for (pair<int, int> p : vec)
        {
            int y = p.first;
            int x = p.second;
            arr[y][x] = '0';
        }
        memset(visited, 0, sizeof(visited));
        vec.clear();
    }

    cout << ret;

    return 0;
}

강의 풀이

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#define endl "\n"
#define MAX 305
typedef pair<int, int> pii;
int ret;

queue<int> q;
int n, m, Y1, X1, Y2, X2;
char a[MAX][MAX];
int visited[MAX][MAX];
int dy[4] = {0, 1, 0, -1}, dx[4] = {-1, 0, 1, 0};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    cin >> Y1 >> X1 >> Y2 >> X2;
    --Y1, --X1, --Y2, --X2;
    for (int i = 0; i < n; ++i)
    {
        scanf("%s", a[i]);
    }
    q.push(1000*Y1 + X1);
    visited[Y1][X1] = 1;
    int cnt = 0;
    while (a[Y2][X2] != '0')
    {
        ++cnt;
        queue<int> temp;
        while (!q.empty())
        {
            int y = q.front() / 1000;
            int x = q.front() % 1000;
            q.pop();
            for (int i = 0; i < 4; ++i)
            {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if (ny < 0 || ny >= n || nx < 0 || nx >= m || visited[ny][nx]) continue;
                visited[ny][nx] = cnt;
                if (a[ny][nx] != '0')
                {
                    temp.push(1000 * ny + nx);
                }
                else
                    q.push(1000*ny + nx);
            }
        }
        q = temp;
    }

    printf("%d\n", visited[Y2][X2]);

    return 0;
}