[코드트리] 두 방향 탈출 가능 여부 판별하기 , python 문제 풀이

안녕하세요 오늘은 파이썬으로 푸는 간단한 DFS 문제를 소개해드립니다. DFS자체가 간단한 알고리즘은 아니지만 이해하신 분들에게는 쉬우며 아직 이해 도중에 있는 분들은 연습 삼아 풀어볼 만한 문제인 것 같네요.

---

문제

n * m 크기의 이차원 영역의 좌측 상단에서 출발하여 우측 하단까지 뱀에게 물리지 않고 탈출하려고 합니다. 이동을 할 때에는 반드시 아래와 오른쪽 2방향 중 인접한 칸으로만 이동할 수 있으며, 뱀이 있는 칸으로는 이동을 할 수 없습니다. 예를 들어 <그림 1>과 같이 뱀이 배치되어 있는 경우 실선과 같은 경로로 탈출을 할 수 있습니다. 이때 뱀에게 물리지 않고 탈출 가능한 경로가 있는지 여부를 판별하는 코드를 작성해보세요.

입력 형식

첫 번째 줄에는 n과 m이 공백을 사이에 두고 주어지고,

두 번째 줄부터 (n+1)번째 줄까지는 각 행에 뱀이 없는 경우 1, 뱀이 있는 경우 0이 입력으로 공백을 사이에 두고 주어집니다. 시작 칸과 끝 칸에는 뱀이 주어지지 않는다고 가정해도 좋습니다.

• 2 ≤ n, m ≤ 100

출력 형식

좌측 상단에서 출발하여 우측 하단까지 뱀에게 물리지 않고 탈출 가능한 경로가 있으면 1, 없으면 0을 출력합니다.

입출력 예제

예제 1

입력:

5 5
1 0 1 1 1
1 0 1 0 1
1 0 1 1 1
1 0 1 0 1
1 1 1 0 1

 

출력:

0

 

예제 2

입력:

5 5
1 0 1 1 1
1 0 1 0 1
1 1 1 0 1
1 0 1 1 1
0 1 1 0 1

 

출력:

1

---

코드

def dfs(x, y):

    visited[x][y] = True
    dxs, dys = [1, 0], [0, 1]

    for dx, dy in zip(dxs, dys):
        new_x , new_y = x + dx, y + dy
        if can_go(new_x,new_y):
            dfs(new_x,new_y)

def in_range(x,y):
    return 0 <= x and x < n and 0 <= y and y < m

def can_go(x,y):
    if not in_range(x,y):
        return False
    
    if visited[x][y] or grid[x][y] == 0:
        return False
    
    return True

n , m = tuple(map(int,input().split()))
grid = [
    list(map(int,input().split()))
    for _ in range(n)
]
visited = [[False for _ in range(m)]for _ in range(n)]

dfs(0 ,0)

if visited[n-1][m-1] == True:
    print(1)
else:
    print(0)

최대한 깔끔한 가독성을 위해 노력했습니다. 감사합니다.