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

Overview

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

---

* 올 것이 왔다. BFS를 제일 어려워하는데 해야지 어쩌겠어. 차근차근 해보자. 익숙해질 때까지 체감 난이도는 계속 높을 예정이다. 🥲

 

[문제]

네 방향 탈출 가능 여부 판별하기

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

 

 

[코드]

BFS 구현 방법 

1. 입력 받기, 방문 기록할 배열 초기화, 큐 생성

2. 격자 내에 있는지 이동 가능한 지 여부 확인 (이동 가능 여부는 문제의 조건에 따라 추가됨)

3. queue에 시작점(초기값)을 append 해준다. 

- 제일 먼저 들어온 원소를 popleft 해주고, 그 좌표를 기준으로 4방향으로 이동할 수 있는지 확인한다. 

- 이동 가능하면 queue에 append 해준다. / 방문 처리도 해준다. 

- queue가 empty가 될 때까지 append, popleft를 반복해준다. (+ 방문 처리)

4. 문제의 출력 조건에 알맞은 답을 출력한다.

- 여기서는 arr[n-1][m-1]에 도달할 수 있는가 이므로 방문 기록 배열을 확인해준다. 

 

DFS랑 이동 가능한 지 여부 구현은 같다. 
다만, DFS는 재귀 함수를, BFS는 Queue를 사용한다는 점이 다르다. 

 

 

(최종 코드)

from collections import deque 

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * 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):
    if not in_range(x, y):
        return False
    
    if visited[x][y] or arr[x][y] == 0:
        return False

    return True


# bfs 탐색
def bfs():

    while q:
        # queue에서 가장 먼저 들어온 원소를 빼준다. (현재 좌표)
        x, y = q.popleft() 

        # 상하좌우 - queue에서 뺀 좌표를 기준으로 4방향 확인 
        dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]

        for dx, dy in zip(dxs, dys):
            nx, ny = x + dx, y + dy

            # 갈 수 있는 곳이라면 queue에 넣어주고 방문 여부 표시한다. 
            if can_go(nx, ny):
                q.append((nx, ny))
                visited[nx][ny] = True

# 시작점을 queue에 넣는다. 
q.append((0, 0))
visited[0][0] = True

bfs()

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