[코드트리 챌린지] DFS / 두 방향 탈출 가능 여부 판별하기

 

문제

https://www.codetree.ai/missions/2/problems/determine-escapableness-with-2-ways?&utm_source=clipboard&utm_medium=text 

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

 

풀이

DFS 기초를 확인할 수 있는 쉬운 문제였다.

마지막 탈출 격자까지 도달했는지 유무를 더 쉽게 확인할 수 있는 방법을 기억하기 위해 기록한다.

내가 짠 방법 : global result 변수를 사용해 매번 만나는 (x, y) 좌표가 탈출 좌표 이면 result를 변경

더 쉬운 방법 : visited[n-1][m-1]이 '1' 인지 '0' 인지 출력하면 됨. 1이면 그 격자까지 도달한 것이기 때문에.

 

코드

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

dx = [1, 0] # 아래, 오른쪽
dy = [0, 1]
result = 0

def dfs(x, y, visited):
    global result
    visited[x][y] = True    # 방문표시
    if (x, y) == (n-1, m-1):
         result += 1
    for d in range(2):
        nx = x + dx[d]
        ny = y + dy[d]
        
        if nx < 0 or nx >= n or ny < 0 or ny >= m: # 격자를 벗어나면 패스
            continue
        if graph[nx][ny] == 0:  # 뱀이 있는 경우, 패스
            continue
        if not visited[nx][ny]: # 방문하지 않았으면,
            visited[nx][ny] = True 
            dfs(nx, ny, visited)
dfs(0, 0, visited)
print(result)