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

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

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

Code

from collections import deque

n, m = map(int, input().split())    # n, m 입력받기
matrix = [list(map(int, input().split())) for _ in range(n)]    # 2차원 배열 입력받기 (0 == 뱀이 있음, 1 == 뱀이 없음)

visited = [[0 for _ in range(m)] for _ in range(n)]     # 이동한 구역 체크용 2차원 배열
ans = [[0 for _ in range(m)] for _ in range(n)]         # bfs대로 이동 순서 체크용 2차원 배열

# 이동 가능한지 판단하는 함수
def can_go(x, y):
    if(x < 0 or x >= n or y < 0 or y >= m):
        return False
    if(visited[x][y] == 1 or matrix[x][y] == 0):
        return False
    return True

# 큐 선언
q = deque()

# 초기 실행
num = 1     # 방문 순서 기록용
q.append([0, 0])
visited[0][0] = 1
ans[0][0] = num

# 이동 방향 (상, 좌, 하, 우)
dx_list = [-1, 0, 1, 0]
dy_list = [0, -1, 0, 1]

# bfs 탐색 실행
while(q):
    x, y = q.popleft()
    for dx, dy in zip(dx_list, dy_list):
        new_x = x + dx
        new_y = y + dy

        if(can_go(new_x, new_y)):
            num += 1
            ans[new_x][new_y] = num
            q.append([new_x, new_y])
            visited[new_x][new_y] = 1

# print(visited)
# print(ans)

# 정답출력 ) 뱀에게 물리지 않고 탈출 가능한 경로가 있으면 1, 없으면 0을 출력
if(ans[n-1][m-1] == 0):
    print(0)
else:
    print(1)

풀이 및 해설

• 장애물이 주어지고 좌측 상단부터 우측 하단까지의 격자 이동 가능 여부를 BFS로 탐색하여 결과 출력하기
• 코드 틀린게 없었는데 자꾸 제출만 하면 테케에서 걸려서 확인해보니까 “n * m 크기의 2차원 영역” 이었다 … 아놔
  • can_go 함수에서 그래프 초과 기준을 n, n 으로 설정해놔서 n, m으로 수정
  • visited, ans 배열 크기 n * m으로 수정

정답 코드

from collections import deque

# 변수 선언 및 입력
n, m = tuple(map(int, input().split()))

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

visited = [
    [False for _ in range(m)]
    for _ in range(n)
]

q = deque()

# 주어진 위치가 격자를 벗어나는지 여부를 반환합니다.
def in_range(x, y):
    return 0 <= x and x < n and 0 <= y and y < m

# 주어진 위치로 이동할 수 있는지 여부를 확인합니다.
def can_go(x, y):
    return in_range(x, y) and a[x][y] and not visited[x][y]

def bfs():
    # queue에 남은 것이 없을때까지 반복합니다.
    while q:
        # queue에서 가장 먼저 들어온 원소를 뺍니다.
        x, y = q.popleft()
        
        # queue에서 뺀 원소의 위치를 기준으로 4방향을 확인해봅니다.
        dxs, dys = [0, 1, 0, -1], [1, 0, -1, 0]
        for dx, dy in zip(dxs, dys):
            new_x, new_y = x + dx, y + dy
        
            # 아직 방문한 적이 없으면서 갈 수 있는 곳이라면
            # 새로 queue에 넣어주고 방문 여부를 표시해줍니다.
            if can_go(new_x, new_y):
                q.append((new_x, new_y))
                visited[new_x][new_y] = True

                
# bfs를 이용해 최소 이동 횟수를 구합니다.
# 시작점을 queue에 넣고 시작합니다.
q.append((0, 0))
visited[0][0] = True

bfs()

# 우측 하단을 방문한 적이 있는지 여부를 출력합니다.
answer = 1 if visited[n - 1][m - 1] else 0
print(answer)