[n13565] 침투 in python

---

dfs로 푼 문제!

그냥 끝까지 탐색하고 더이상 탐색할 수 없으면

다시 돌아오면 그만!

 

바깥쪽에 해당하는 0번째 줄만

dfs문을 돌린다.

 

그리고 맨 마지막줄에 2가 있으면

안쪽까지 탐색이 되는거니까

YES를 출력해주면 되는 문제

 

그런데 이렇게 하니까 시간이 오래걸렸다 (1243ms) ㅠㅠ

 

import sys
sys.setrecursionlimit(3000000)
m, n = map(int, input().split())  # m = 행, n = 열
array = [list(map(int, list(input()))) for _ in range(m)]

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


def dfs(row, col):
    array[row][col] = 2
    for i in range(4):
        nx = row + dx[i]
        ny = col + dy[i]
        if 0 <= nx < m and 0 <= ny < n and array[nx][ny] == 0:
            dfs(nx, ny)


for k in range(n):
    if array[0][k] == 0:
        dfs(0, k)  # 시작점은 바깥쪽 줄

print("YES" if 2 in array[-1] else "NO")

---

위 코드는 모든 경우의 수를 다 돌고나서

마지막에 2가 있는지 체크하는 문제이다.

 

아래는 안쪽에 닿는 즉시 종료되도록 설정하였다.

import sys

sys.setrecursionlimit(3000000)
m, n = map(int, input().split())  # m = 행, n = 열
array = [list(map(int, list(input()))) for _ in range(m)]

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


def dfs(row, col):
    global button
    if row == m - 1:  # 안쪽에 닿은 경우
        button = True
        return True

    array[row][col] = 2
    for i in range(4):
        nx = row + dx[i]
        ny = col + dy[i]
        if 0 <= nx < m and 0 <= ny < n and array[nx][ny] == 0:
            dfs(nx, ny)


for k in range(n):
    if array[0][k] == 0:
        dfs(0, k)  # 시작점은 바깥쪽 줄
        if button:
            print("YES")
            break
if not button:
    print("NO")