(C++) - 백준(BOJ) 13565번 : 침투

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

13565번: 침투

bfs문제였습니다.

 

 

📕 풀이방법

📔 입력 및 초기화

 1. m, n을 입력받습니다. m은 행, n은 열입니다. 

 

 2. m행 n열만큼 이차원 배열인 board변수에 적절히 입력해줍니다.

 

📔 풀이과정

 1. 아직 전류를 흘러보낸적이 없다면 ck = 0, 있다면 ck = 1로 생각합니다.

 

 2. 0행에 해당하는 부분은 outer side에서 전류를 흘려보낸다고 생각할 수 있습니다. 따라서 0행의 모든 열들을 확인하면서 한 번도 전류를 흘려 보낸적이 없다면 bfs를 수행합니다.

  2-1. bfs를 수행하면서 시작좌표 0행 i열에서 시작해서 상하좌우로 모두 전류를 흘려보냅니다.

  2-2. 가장 마지막 행인 m-1에 전류가 흘렀다면 1을 반환 아니라면 0을 반환합니다.

 

📔 정답출력

 bfs의 반환값이 1이라면 inner side까지 전류가 성공적으로 흘렀으므로 SUCCESS로 간 후 YES를 출력합니다.

 아니라면 NO를 출력하고 program을 종료합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;

int ck[1001][1001], board[1001][1001], m, n;
int dr[] = {0,0,1,-1};
int dc[] = {1,-1,0,0};

int bfs(int i, int j){
    queue <pii> q;
    q.push({i,j});
    ck[i][j] = 1;
    while(!q.empty()){
        int r = q.front().first;
        int c = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];
            if(0 > nr || nr >= m || 0 > nc || nc >= n) continue;
            if(ck[nr][nc] || board[nr][nc] == 1) continue;
            ck[nr][nc] = 1;
            q.push({nr,nc});
        }
    }

    for(int i = 0; i < n; i++)
        if(ck[m-1][i]) return 1;

    return 0;
}

int main(){
    cin >> m >> n;
    for(int i = 0; i < m; i++)
        for(int j = 0; j < n; j++)
            scanf("%1d",&board[i][j]);

    for(int i = 0; i < n; i++)
        if(!ck[0][i] && !board[0][i] )
            if(bfs(0,i)) goto SUCCESS;

    cout << "NO"; return 0;

    SUCCESS:
    cout << "YES";

}