[BOJ 13565] 침투 C++

난이도: Silver 2
번호: 13565
생성일: February 24, 2023 3:37 PM
알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색
언어: C++

C++

BFS

메모리	시간
3980 kb	28 ms

// BOJ 13565 침투
#include <iostream>
#include <queue>
using namespace std;

int N, M;
char map[1002][1002];
bool visited[1002][1002];

const int dX[] = {0, 0, 1, -1};
const int dY[] = {1, -1, 0, 0};

void BFS(int i, int j)
{
    queue<pair<int, int>> Q;
    Q.push({i, j});
    visited[i][j] = true;

    while (!Q.empty())
    {
        auto cur = Q.front();
        Q.pop();

        for (int k = 0; k < 4; k++)
        {
            int x = dX[k] + cur.first;
            int y = dY[k] + cur.second;

            if (visited[x][y] == true || map[x][y] != '0')
                continue;

            visited[x][y] = true;
            Q.push({x, y});
        }
    }
}

int main(void)
{
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);

    cin >> N >> M;

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            cin >> map[i][j];

    for (int j = 1; j <= M; j++)
        if (map[1][j] == '0' && visited[1][j] == false)
            BFS(1, j);

    bool check = false;
    for (int j = 1; j <= M; j++)
        if (visited[N][j])
        {
            check = true;
            break;
        }

    cout << (check ? "YES" : "NO");
    return (0);
}

C++

DFS

메모리	시간
18588 kb	24 ms

// BOJ 13565 침투
#include <iostream>
#include <queue>
using namespace std;

int N, M;
char map[1002][1002];
bool visited[1002][1002];

const int dX[] = {0, 0, 1, -1};
const int dY[] = {1, -1, 0, 0};

void DFS(int i, int j)
{
    visited[i][j] = true;
    for (int k = 0; k < 4; k++)
    {
        int x = dX[k] + i;
        int y = dY[k] + j;
        if (map[x][y] != '0' || visited[x][y])
            continue;
        DFS(x, y);
    }
}

int main(void)
{
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);

    cin >> N >> M;

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            cin >> map[i][j];

    for (int j = 1; j <= M; j++)
        if (map[1][j] == '0' && visited[1][j] == false)
            DFS(1, j);

    bool check = false;
    for (int j = 1; j <= M; j++)
        if (visited[N][j])
        {
            check = true;
            break;
        }

    cout << (check ? "YES" : "NO");
    return (0);
}