[BOJ/백준] 13565 : 침투 (C++)

[BOJ/백준] 13565번 : 침투

BOJ 13565

문제 해석

• 주어진 상황은 바깥 쪽에서 전류가 섬유 물질을 침투하여 안쪽으로 들어오게 하는 상황입니다. 즉 0으로 이루어진 칸이 2차원 격자에서 1행부터 M행까지 연속으로 이루어진 경우에만 안쪽까지 전류가 침투할 수 있다는 말입니다.

풀이

• 저는 그래프 탐색 기법 중 하나인 BFS를 사용하여 풀었습니다. 첫 번째 행에서 0인 지점을 찾아 탐색을하고 마지막 행(M번째 행)에 도달하기만 하면 탐색을 종료시키는 방법으로 풀었습니다.

• 테스트 케이스 예제 입력을 보면 행이 한번에 입력받는 것으로 보여 string으로 입력을 받고 정수값으로 2차원 배열에 저장을 했습니다.

for(int i=1; i<M+1; i++){
        string s;
        cin>>s;
        for(int j=1; j<N+1; j++){
            grid[i][j]=s[j-1]-'0';
        }
    }

• 자세한 설명은 전체 코드를 보며 하겠습니다.

코드

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

int M, N; //2차원 격자 표현을 위한 변수 M: x좌표 N: y좌표로 설정
int dx[]={1,-1,0,0};// 위 아래 오른쪽 왼쪽 방향 탐색을 위한 배열
int dy[]={0,0,1,-1};

vector<vector<int> > grid; // 2차원 격자판을 나타내기 위한 벡터
vector<vector<int> > visited; // 방문한 위치를 방문했음을 처리하기 위한 벡터

bool BFS(int x, int y){ //연속된 0인 지점을 탐색하기 위한 함수 알고리즘 BFS 탐색
    queue<pair<int, int> > mq;
    mq.push(make_pair(x, y));// 탐색을 시작하는 위치를 queue에 넣음
    visited[x][y]=1;//시작 위치 방문 처리

    while(!mq.empty()){
        int cx=mq.front().first;//현재 위치를 표현 cx=current x
        int cy=mq.front().second;//current y
        mq.pop();

        for(int i=0; i<4; i++){// 현재 위치에서 위 아래 오른쪽 왼쪽 탐색
            int nx = cx+dx[i];
            int ny = cy+dy[i];
            if(nx>0 && nx<=M && ny>0 && ny<=N && visited[nx][ny]==0 && grid[nx][ny]==0){//격자에 벗어나지 않고 다음 위치가 0이며, 방문하지 않은 위치이면 탐색 진행
                mq.push(make_pair(nx, ny));
                visited[nx][ny]=1;
                if(nx==M) return true; // 마지막 행에 도달하면 true 반환
            }
        }
    }
    return false;// 마지막 행까지 도달하지 못하고 함수가 끝나면 false반환
}

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

    cin>>M>>N;

    grid.resize(M+1, vector<int> (N+1, 0));//격자의 위치를 (1,1)부터 시작하기 위해서 M+1, N+1 로 초기화
    visited.resize(M+1, vector<int> (N+1, 0));

    for(int i=1; i<M+1; i++){//1부터 시작
        string s;
        cin>>s;
        for(int j=1; j<N+1; j++){//string으로 입력받아 정수값으로 저장
            grid[i][j]=s[j-1]-'0';
        }
    }
    for(int i=1; i<N+1; i++){
        if(grid[1][i]==0 && visited[1][i]==0){ // 첫번째 행에서 격자가 0이고 방문하지 않은 곳이면 BFS 탐색 진행
            if(BFS(1,i)){//true가 반환되면 YES 출력
                cout<<"YES\n";
                return 0;
            }
        }
    }
    cout<<"NO\n";//true를 반환한적이 없으면 NO 출력
    return 0;
}