[백준] 13565번 침투 파이썬

문제

인제대학교 생화학연구실에 재직중인 석교수는 전류가 침투(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

예제 입력

8 8
11000111
01100000
00011001
11001000
10001001
10111100
01010000
00001011

예제 출력 2

YES

제출 답안

• 중간 dfs에서 result가 True이면 바로 빠져나가도록 해야 시간이 줄어든다.
• 그리고 입구부터 무조건 연결되어 있어야 해서 이중 for문대신 바로 y자리에 0을 대입하면 된다.

'''
1. 아이디어
-  for && 연결된 노드가 마지막 노드랑 일치하는지
2. 시간 복잡도
O(V+E)
- V : m*n
- E : 4v
- (m*n) + 4(m*n) = 5(m*n) = 5(1000*1000) = 5,000,000 < 2억
3. 자료구조
- int [][]
- bool [][]
'''

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

m, n = map(int, input().split())
graph = [list(map(int, input().strip())) for _ in range(m)]
visited = [[False] * n for _ in range(m)]
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
result = False
def dfs(y, x):
    global result
    # 이 검사 부분이 있어야 없을 때보다 시간이 5분의 1로 감소된다. 
    if result:
        return
    for k in range(4):
        ny = y + dy[k]
        nx = x + dx[k]
        if 0<=ny<m and 0<=nx<n:
            # 만약 ny가 m-1이라면 마지막 출구까지 도달한 것이기에 True로 변경하고 빠져나간다.
            if ny == (m-1):
                result = True
                return
            if graph[ny][nx] == 0 and not visited[ny][nx]:
                visited[ny][nx] = True
                dfs(ny, nx)

for i in range(n):
    # 마찬가지로 이미 완료된 dfs가 완료되었으면 추가적으로 for를 돌지 않아도 된다.
    if result:
        break
    if graph[0][i] == 0 and not visited[0][i] and not result:
        visited[0][i] = True
        dfs(0, i)

if result:
    print("YES")
else:
    print("NO")