[백준 13565번] 파이썬 - 침투

백준 13565 - 침투

시간 제한 1초, 메모리 제한 512MB

# 조건

• 인제대학교 생화학연구실에 재직중인 석교수는 전류가 침투(percolate) 할 수 있는 섬유 물질을 개발하고 있다.
• 이 섬유 물질은 2차원 M × N 격자로 표현될 수 있다. 편의상 2차원 격자의 위쪽을 바깥쪽(outer side),
• 아래쪽을 안쪽(inner side)라고 생각하기로 한다.
• 또한 각 격자는 검은색 아니면 흰색인데, 검은색은 전류를 차단하는 물질임을 뜻하고 흰색은 전류가 통할 수 있는 물질임을 뜻한다.
• 전류는 섬유 물질의 가장 바깥쪽 흰색 격자들에 공급되고, 이후에는 상하좌우로 인접한 흰색 격자들로 전달될 수 있다.
• 김 교수가 개발한 섬유 물질을 나타내는 정보가 2차원 격자 형태로 주어질 때, 바깥쪽에서 흘려 준 전류가 안쪽까지 침투될 수 있는지 아닌지를 판단하는 프로그램을 작성하시오.

• 예를 들어 위에 침투하지만, 아래는 침투하지 못한다.

  입력

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

출력

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

# 접근 방법

• BFS를 활용하면 된다.
• 0행부터 1을 발견한 경우 BFS 함수를 수행해준다.
• 이 때, VISITED => 이미 방문한 칸이라면 CONTINUE 해주고 그렇지 않다면 Q에 넣어준다.
• 출력 형식 꼭.!!!! 잘 확인하자.. 맞게 풀었음에도 UPPER CASE가 아닌 Title case로 return 하여 틀렸습니다를 받았다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  

def bfs(bi, bj, visited, arr):  
    q = deque([(bi, bj)])  
    while q:  
        si, sj = q.popleft()  
        if si == N-1:  
            return 1  
        for d in range(4):  
            ni, nj = si + di[d], sj + dj[d]  
            if 0<=ni<N and 0<=nj<M and arr[ni][nj] == '0' and not visited[ni][nj]:  
                q.append((ni, nj))  
                visited[ni][nj] = 1  
    return 0  

def check(arr):  
    global visited  
    visited = [[0] * M for _ in range(N)]  
    for j in range(M):  
        if arr[0][j] == '0' and not visited[0][j]:  
            visited[0][j] = 1  
            flag = bfs(0, j, visited, arr)  
            if flag:  
                return 'YES'  
    return 'NO'  

def main():  
    global N, M  
    N, M = map(int, input().split())  
    arr = [list(input().strip()) for _ in range(N)]  
    print(check(arr))  

if __name__ == "__main__":  
    di, dj = [1, -1, 0, 0], [0, 0, 1, -1]  
    main()