[Code Tree][Python] DFS / 두 방향 탈출 가능 여부 판별하기

Overview

• 체감 난이도: ★★☆☆☆
• 문제 유형: DFS
• 풀이 상태: 답안참고 / 스스로 해결
• 추후: 다시 풀어보기 / 간단 복습 / 완벽 이해 

---

[문제]

https://www.codetree.ai/missions/2/problems/determine-escapableness-with-2-ways/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

[코드]

동작 방식

1. dfs(x, y)가 호출되면, 함수는 현재 위치에서 인접한 방향(아래쪽, 오른쪽)으로 이동 가능한지 검사

2. 이동이 가능할 경우, 해당 위치를 방문처리하고 다시 dfs(new_x, new_y)를 호출하여 탐색을 이어간다. 

3. 탐색이 전부 끝나면 visited 배열에 방문한 경로가 기록되어 있어, 경로의 탐색 결과를 확인할 수 있다. 

 

dfs 함수에서 return을 하지 않아도 되는 이유

: DFS 가 단순히 방문을 기록하며 경로를 탐색하는 역할을 하기 때문이다. 

→ 함수가 값을 반환하지 않고 visited 배열의 값을 변경함으로써 탐색의 결과가 저장된다. 

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  # 이동가능한 경우


def dfs(x, y):
    dxs, dys = [1, 0], [0, 1]
    
    # 아래 및 오른쪽 방향에 대하여 탐색 
    for dx, dy in zip(dxs, dys):
        new_x, new_y = x + dx, y + dy

        # 각 위치로 이동할 수 있는지 여부 확인 후 DFS 탐색 
        if can_go(new_x, new_y):
            visited[new_x][new_y] = 1
            dfs(new_x, new_y)


# main
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
visited = [[0] * m for _ in range(n)]

visited[0][0] = 1
dfs(0, 0)

print(visited[n-1][m-1])