[Python/BOJ] 13565. 침투

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

13565번: 침투

문제

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

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

 

 

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

입력

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

출력

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

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

풀이

Code

import sys
from collections import deque
input = sys.stdin.readline

def solution(m, n, graph) :
    # 1. bfs 함수 정의
    def bfs(x, y) :
        # 1-1. 현재 위치 큐에 삽입
        queue = deque()
        queue.append((x, y))
        # 1-2. 현재 위치 방문 처리
        visited[x][y] = True
        # 1-3.
        while queue :
            # 위치 인덱스 반환
            x, y = queue.popleft()
            for dir_x, dir_y in [(-1, 0), (1, 0), (0, -1), (0, 1)] :
                # 다음 위치 정의
                nx, ny = x + dir_x, y + dir_y
                # 예외 처리
                if nx < 0 or nx >= m or ny < 0 or ny >= n : continue
                # 해당 위치가 벽이 아니면서 방문하지 않은 경우
                if not graph[nx][ny] and not visited[nx][ny] :
                    # 다음 위치가 마지막 해일 경우 YES 반환 후 시스템 종료
                    if nx == m - 1 :
                        print('YES')
                        exit()
                    # 방문 처리
                    visited[nx][ny] = True
                    # 큐에 다음 위치 삽입
                    queue.append((nx, ny))
    # 2. 방문 여부 리스트 생성
    visited = [[False] * n for _ in range(m)]
    # 3.
    for j in range(n) :
        # 3-1. 해당 열이 빈 공간이면서 방문 처리가 안 된 경우
        if not graph[0][j] and not visited[0][j] :
            # bfs 실행
            bfs(0, j)
    # 4. NO 출력
    print('NO')

if __name__ == "__main__" :
    m, n = map(int, input().split())
    graph = [list(map(int, input().rstrip())) for _ in range(m)]
    solution(m, n, graph)