[cpp 알고리즘] 백준 13565 침투

[백준] 13565 침투 cpp 풀이

알고리즘: 그래프 이론, 그래프 탐색, 너비우선탐색(bfs), 깊이우선탐색(dfs)

https://www.acmicpc.net/problem/13565

문제 요약

- 2차원 격자가 주어지고, 각 격자는 0(전류 흐름)과 1(전류 차단)로 구성되어있다.

- 각 전류는 상하좌우로 이동할 수 있다.

- 이 때, 격자의 위쪽(outer side)에서 아래쪽(inner side) 까지 전류가 올 수 있는지 YES/NO를 출력해주면 된다.

풀이 정리

- 완전 기본적인 dfs 문제였다. M*N 격자 안에 있고 아직 방문하지 않은 점이면서 전류가 흐를 수 있는 0의 칸이라면 dfs로 더 탐색해주었다.

- 상하좌우 4방향에 dx와 dy배열을 이용했다.

- 격자의 맨 위(행=0)인 지점에서 모두 시작했고, 마지막 행(M-1)번째에 0이 하나라도 있으면 전류가 다 흘렀다고 판단했다.

백준 13565 풀이

C++ 코드

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

int N, M;
int arr[1001][1001];
int visited[1001][1001];

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

void dfs(int y, int x){
    visited[y][x] = 1;
    
    for(int i=0; i<4; i++){
        int ny = y+dy[i]; int nx = x+dx[i];
        
        if(ny<0 || ny>=M || nx<0 || nx >=N) continue;
        if(visited[ny][nx] == 0 && arr[ny][nx] == 0) dfs(ny, nx);
    }
}

int main(){
    
    cin >> M >> N;
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            char c; cin >> c;
            arr[i][j] = c-'0';
        }
    }
    
    for(int j=0; j<N; j++){
        dfs(0, j);
    }
    
    bool cango = false;
    for(int j=0; j<N; j++){
        if(visited[M-1][j] == 1){
            cout << "YES\n";
            return 0;
        }
    }
    
    cout << "NO\n";
    
    
    return 0;
}