[백준] 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를 출력한다.

👉 생각

• 깊이 우선 탐색을 하는 함수 DFS를 만들어준다. 주어지는 배열 arr의 첫번째 행에서 깊이우선탐색을 시작해서 제일 마지막 행에 도착할 수 있는지 여부를 판별하는 문제다.
• 처음에는 방문체크를 해주는 배열 visited를 함수 안에 만들어서 매 첫번재 행마다 리셋을 했는데, 이때문에 시간초과가 발생했다.
• 생각해보면 DFS를 돌렸을 때 일단 깊이를 우선으로 모든 곳을 탐색하니까 visited 배열을 글로벌로 만들어서 체크한다면 시간초과를 피할 수 있었다!

from collections import deque
import sys

def dfs(x, y):
    stack = deque([])
    stack.append((x,y))
    visited[x][y] = 1
    while stack:
        x, y = stack.pop()

        if x == m-1:
            return True

        for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and not arr[nx][ny] and not visited[nx][ny]:
                stack.append((nx, ny))
                visited[nx][ny] = 1
    return False

m, n = map(int, input().split())
arr = [list(map(int, sys.stdin.readline().replace('\n', ''))) for _ in range(m)]
visited = [[0] * n for _ in range(m)]
check = False
for i in range(n):
    if not arr[0][i] and dfs(0, i):
        check = True

print('YES' if check else 'NO')