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

코드트리 학습하기 - 알고리즘 입문 : BFS/DFS

• 두 방향 탈출 가능 여부 판별하기 (Python)
  https://www.codetree.ai/missions/2/problems/determine-escapableness-with-2-ways/description

Code

n, m = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]

visited = [list(0 for _ in range(m)) for _ in range(n)]     # 각 격자의 방문 여부를 체크할 2차원 배열

ans = []    # 갈 수 있는 좌표값 (x, y) 를 담을 배열

# 갈 수 있는 격자인지 판별해주는 함수
def can_go(x, y):
    if(x >= n or y >= m or x < 0 or y < 0):         # 범위를 벗어나면 X
        return False
    if(visited[x][y] == -1 or matrix[x][y] == 0):   # 이미 방문한 곳이거나, 뱀이 있는 곳이라면 X
        return False
    return True

# DFS 실행
def dfs(x, y):
    # 아래로 이동, 오른쪽으로 이동
    dx = [1, 0]
    dy = [0, 1]

    for i, j in zip(dx, dy):
        new_x = x + i   # 이동할 X 좌표
        new_y = y + j   # 이동할 Y 좌표

        if(can_go(new_x, new_y)):       # (이동할 X, 이동할 Y)가 갈 수 있는 격자라면 -> 이동
            visited[new_x][new_y] = -1
            ans.append((new_x, new_y))
            dfs(new_x, new_y)

# 초기 시작 (좌측 상단인 (0,0) 에서부터 시작)
visited[0][0] = -1
ans.append((0,0))
dfs(0, 0)

# print(ans)
if((n-1, m-1) in ans):
    print(1)
else:
    print(0)

풀이 및 해설

• 기본 DFS 문제, 재귀적으로 수행
• 이동 여부가 아래, 오른쪽 밖에 없어서 dx, dy 값을 아래와 같이 설정

  # 아래로 이동, 오른쪽으로 이동
  dx = [1, 0]
  dy = [0, 1]

• can_go 함수로 갈 수 있는 격자인지 판별하기