이번 문제는 깊이우선탐색을 통해 해결하였다. 기존의 깊이우선탐색 문제와 매우 유사하였기 때문에 쉽게 해결할 수 있었다. 문자열로 입력된 섬유 물질의 정보를 가변 객체인 리스트로 변환하여 저장하고, dfs() 재귀 함수에서 방문한 인덱스의 값을 1로 변경시키며 깊이 우선 탐색을 진행한다. 이때 정답을 저장하는 변수 answer를 global로 선언한 뒤에 만약 y축 인덱스가 m-1까지 도달했을 경우 answer를 'YES'로 변경한 뒤에 함수를 종료하도록 작성하였다.

• 재귀 제한을 늘린다.
• dfs함수를 y, x를 인자로 갖도록 선언한다.
  -> answer를 global로 선언한다.
  -> fiber[y][x]를 1로 갱신한다.
  -> 만약 y가 m-1이라면 answer를 'YES'로 갱신하고 함수를 종료한다.
  -> 4가지 방향을 dy, dx에 짝지어 저장한다.
  -> 4번 반복하는 i에 대한 for문을 돌린다.
  --> ny에 y+dy[i]를 저장한다.
  --> nx에 x+dx[i]를 저장한다.
  --> 만약 ny, nx가 0보다 크거나 같고, ny가 m보다 작고, nx가 n보다 작고, fiber[ny][nx]가 0일 경우, dfs(ny, nx)를 재귀호출한다.
• m,n을 입력받는다.
• 섬유 물질의 정보를 저장할 리스트 fiber를 선언한다.
• 정답을 저장할 변수 answer를 'NO'로 선언한다.
• m번 반복하는 for문을 돌린다.
  -> fiber를 입력받는다.
• n번 반복하는 for문을 돌린다.
  -> 만약 fiber[0][i]가 0일 경우 dfs(0, i)를 호출한다.
• answer를 출력한다.

Code

import sys
sys.setrecursionlimit(10**9)
def dfs(y, x):
    global answer
    fiber[y][x]=1
    if y==m-1:
        answer='YES'
        return
    dy=[0, 0, -1, 1]
    dx=[1, -1, 0, 0]
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if ny>=0 and nx>=0 and ny<m and nx<n and fiber[ny][nx]==0:
            dfs(ny, nx)
m,n=map(int, input().split())
fiber=[]
answer='NO'
for _ in range(m):
    fiber.append(list(map(int, input())))
for i in range(n):
    if fiber[0][i]==0:
        dfs(0, i)
print(answer)