백준 14497번 주난의난 C++

문제

www.acmicpc.net/problem/14497

 

코드1 (BFS 로 4ms 걸림)

#include<bits/stdc++.h>

using namespace std;
const int max_n = 301;

int n, m, yPos1, xPos1, yPos2, xPos2, ret, visited[max_n][max_n];
int dy[4] = { -1, 0, 1, 0 }, dx[4] = {0, 1, 0, -1};
char map_[max_n][max_n];
queue<pair<int, int>> q;

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    scanf("%d %d", &n, &m);
    scanf("%d %d %d %d", &yPos1, &xPos1, &yPos2, &xPos2);
    
    yPos1--;
    xPos1--;
    yPos2--;
    xPos2--;

    for (int i = 0; i < n; i++)
    {
        scanf("%s", map_[i]);
    }

    q.push({ yPos1, xPos1 });
    visited[yPos1][xPos1] = 1;
    int cnt = 0;

    while (map_[yPos2][xPos2] != '0')
    {
        cnt++;
        queue<pair<int, int>> qTemp;
        while (q.size())
        {
            int y = q.front().first;
            int x = q.front().second;
            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;

                if (map_[ny][nx] == '0')
                {
                    q.push({ ny, nx });
                }
                else
                {
                    map_[ny][nx] = '0';
                    qTemp.push({ ny, nx });
                }

                visited[ny][nx] = cnt;
            }
        }
        q = qTemp;
    }

    cout << visited[yPos2][xPos2] << "\n";

    return 0;
}

코드2 (DFS로 48ms 걸림)

#include<bits/stdc++.h>

using namespace std;
int m, n, isVisited[301][301], jump, posX1, posX2, posY1, posY2;
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 };
bool flag = false;
char arr[301][301];

void dfs(int y, int x)
{
    isVisited[y][x] = 1;
    if (y == posY2-1 && x == posX2-1)
    {
        flag = true;
        return;
    }

    if (arr[y][x] == '1')
    {
        arr[y][x] = 0;
        return;
    }

    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 || isVisited[ny][nx])
            continue;

        dfs(ny, nx);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    cin >> posY1 >> posX1;
    cin >> posY2 >> posX2;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {

            cin >> arr[i][j];
        }
    }

    while (1)
    {
        fill(&isVisited[0][0], &isVisited[0][0] + 301 * 301, 0);

        dfs(posY1-1, posX1-1);
        jump++;
        if (flag)
            break;
    }

    cout << jump << "\n";

    return 0;
}