[BOJ] 13565 침투 알고리즘 스터디 11월 21일

오늘 풀 문제는 침투 

--> 백준에서 가져왔고 아래 주소가 있습니다. 

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

침투

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	1654	628	477	40.979%

문제

인제대학교 생화학연구실에 재직중인 석교수는 전류가 침투(percolate) 할 수 있는 섬유 물질을 개발하고 있다. 이 섬유 물질은 2차원 M × N 격자로 표현될 수 있다. 편의상 2차원 격자의 위쪽을 바깥쪽(outer side), 아래쪽을 안쪽(inner side)라고 생각하기로 한다. 또한 각 격자는 검은색 아니면 흰색인데, 검은색은 전류를 차단하는 물질임을 뜻하고 흰색은 전류가 통할 수 있는 물질임을 뜻한다. 전류는 섬유 물질의 가장 바깥쪽 흰색 격자들에 공급되고, 이후에는 상하좌우로 인접한 흰색 격자들로 전달될 수 있다.

김 교수가 개발한 섬유 물질을 나타내는 정보가 2차원 격자 형태로 주어질 때, 바깥쪽에서 흘려 준 전류가 안쪽까지 침투될 수 있는지 아닌지를 판단하는 프로그램을 작성하시오.

(a) The current percolates.	(b) The current does not percolate.

예를 들어, Figure 1(a) 에서는 바깥쪽에서 공급된 전류가 안쪽까지 침투하지만, Figure 1(b)에서는 그렇지 못한다.

입력

첫째 줄에는 격자의 크기를 나타내는  M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않는 검은색 격자임을 뜻한다.

출력

바깥에서 흘려준 전류가 안쪽까지 잘 전달되면 YES를 출력한다.

그렇지 않으면 NO를 출력한다.

예제 입력 1 

5 6
010101
010000
011101
100011
001011

예제 출력 1 

NO

예제 입력 2 

8 8
11000111
01100000
00011001
11001000
10001001
10111100
01010000
00001011

예제 출력 2 

YES

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2016 G번

• 데이터를 추가한 사람: doju
• 문제를 번역한 사람: medic_programmer

문제 해석 : 

* 맨 윗줄 0 으로 채워진 칸들에서 출발하여 좌, 우, 상, 하로 옮겨 다닐 수 있다.

* 1 으로 막힌 칸에는 전기가 옮겨지지 않는다.

* 맨 아랫줄 중, 0 으로 채워진 칸이 있다면, 윗 줄에서 번져온 전기가 닿으면 YES 

* 모든 0 으로 채워진 칸을 위에서 부터 번져 나가도 아랫줄 0 으로 채워진 곧에 닿지 못하면 NO

문제 풀기 : 

#include <cstdio>
#include <deque>
#include <iostream>
#include <algorithm>
#include <memory.h>
#include <utility>
using namespace std;
pair <int ,int > pr;
deque < pair < int, int > > que;
int M, N;
int mp[1001][1001]={0,};
int ck[1001][1001]={0,};
int dy[4] = {1,-1,0,0};
int dx[4] = {0,0,1,-1};
int main(){
    int answer = 0;
    scanf("%d %d", &M, &N);
    que.clear();
    memset(ck,0,sizeof(ck));
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            scanf("%1d", &mp[i][j]);
            if(mp[i][j] == 0 && i == 0)
                que.push_back({i,j});
        }
    }
    
    while(!que.empty()){
        int ny = que.front().first;
        int nx = que.front().second;
        if(ny == M-1){
            answer = 1;
            break;
        }
        //ck[nny][nnx] = 1; // 체크해야할 부분을 처음 짤때 생각을 하지 못해서 계속 무한 반복 했다.
        que.pop_front();
        
        for(int i=0; i<4; i++){
            int nny = ny + dy[i];
            int nnx = nx + dx[i];
            if(nny < 0 || nnx < 0 || nny >= M || nnx >= N || ck[nny][nnx] == 1 || mp[nny][nnx] == 1) continue;
            ck[nny][nnx] = 1;   // 이미 확인 된 장소들은 4번 돌면서 같은 자리를 확인하고 큐에 들어가기 때문에 무한정 큐에 삽입 될
            que.push_back({nny, nnx}); // 가능성이 있어서 제대로 돌지 않았다..
        }
    }
    if(answer == 1)
        printf("YES\n");
    else
        printf("NO\n");
}
 

오답 이유 : 

1. bfs 를 머리 속으로 생각하고 직접 짰을때, 체계적으로 생각하지 않은 듯 하다.

2. 방문한 곳을 확인하고, 큐에 넣지 말았어야 하는데 dfs 처럼 와일문 바로 아래 방문 기록을 표시하는 에러를 발생시킴.

.... ** 앞으로 코드를 작성할때, 알고리즘 구상도를 생각해보고 만들어야 겠다.