백준 13565번: 침투 (파이썬, DFS)

전류가 통하는 격자는 0, 통하지 않는 격자는 1이다. outder side에서 inner side로 침투하면 성공이므로, 첫번째 행의 원소들에 대해서만 DFS를 하면 된다.

마지막 행에 도달했다는것을 알기 위해 방문을 확인하는 배열을 따로 만들었다. outer side에서만 DFS를 하므로(방문), inner side에 방문을 했다면 침투에 성공한 것이기 때문이다.

 

여담으로 출력을 Yes로 했다가 계속 틀려서 머리가 터지는 줄 알았는데 대소문자 구별을 잘해야 하고 문제 조건을 꼼꼼히 읽어야 한다..

 

import sys
sys.setrecursionlimit(10**9)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def dfs(x, y):
    visited[x][y] = True
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= nx < M and 0 <= ny < N and graph[nx][ny] == 0 and not visited[nx][ny]:
            dfs(nx, ny)


M, N = map(int, sys.stdin.readline().split())

graph = []
for _ in range(M):
    graph.append(list(map(int, sys.stdin.readline().rstrip())))

visited = [[False]*N for i in range(M)]

for y in range(N):
    if graph[0][y] == 0 and not visited[0][y]:
        dfs(0, y)

if True in visited[M-1]:
    print('YES')
else:
    print('NO')