백준 13565(침투) - Python(파이썬) - DFS

13565번: 침투

예제 풀이

outer side
0⬇️	1	0⬇️	1	0⬇️	1
0⬇️	1	0➡️	0➡️	0⬇️	0
0❌	1	1	1	0❌	1
1	0	0	0	1	1
0	0	1	0	1	1
inner side

이렇게 outer side에서 시작해서 inner side로 나가야하지만 중간에 전류가 통하지 않는 물질땜에 멈추게 된다.

outer side
1	1	0	0	0⬇️	1	1	1
0	1	1	0	0➡️	0⬇️	0	0
0	0	0	1	1	0⬇️	0	1
1	1	0	0	1	0⬇️	0	0
1	0	0	0	1	0➡️	0⬇️	1
1	0	1	1	1	1	0⬇️	0
0	1	0	1	0	0	0⬇️	0
0	1	0	1	0	0	0⬇️	0
inner side

반면, 예제 2번의 경우 outer side부터 inner side까지 이런 식으로 이동하여 안쪽까지 침투할 수 있습니다.

문제 풀이(DFS)

① DFS 방식을 이용하여 하지만 함수에 r>=n인 경우 ->에는 flag =True가 되도록 만든다.
② 시작하는 점을 행이 0이고 함수가 전류가 잘 통하는 흰색인지 확인해본다.

💻Python(파이썬)

import sys
sys.setrecursionlimit(10 ** 6)
n,m = map(int,sys.stdin.readline().split())
array = [list(map(int,sys.stdin.readline().strip())) for _ in range(n)]
visted = [[False]*m for _ in range(n)]

d = [[1,0],[0,1],[-1,0],[0,-1]]
def dfs(r,c):
    global flag
    if r>=n:
        flag=True
    if 0<=r<n and 0<=c<m and not visted[r][c] and array[r][c]==0:
        visted[r][c]=True
        for drc in d:
            dr = r + drc[0]
            dc = c + drc[1]
            dfs(dr,dc)

flag = False
for c in range(m):
    if array[0][c]==0:
        dfs(0,c)

if flag:
    print('YES')
else:
    print('NO')