[문제 풀이 23] 코드 트리 - n x m 표 이동 5

n x m 표 이동 5

 

• 문제 유형 : BFS
• 사용언어 : Python
• 난이도 : 실버 1
• 출처 : 코드 트리

 

https://www.codetree.ai/training-field/search/problems/move-n-x-m-table-5?&utm_source=clipboard&utm_medium=text

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

 

from collections import deque

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

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

# 최소 이동 횟수를 저장할 배열
visited = [
    [0 for _ in range(m)]  # 0은 방문하지 않았음을 의미
    for _ in range(n)
]

def bfs():
    q = deque()
    q.append((0, 0))
    visited[0][0] = 1  # 시작점을 방문 처리 (칸 수를 포함하므로 1로 시작)

    # 네 방향 이동 (상, 하, 좌, 우)
    dxs, dys = [0, 1, 0, -1], [1, 0, -1, 0]

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

            # 이동 가능하고 방문하지 않았다면
            if 0 <= nx < n and 0 <= ny < m and a[nx][ny] == 1 and visited[nx][ny] == 0:
                visited[nx][ny] = visited[x][y] + 1
                q.append((nx, ny))

bfs()

# (n-1, m-1) 위치의 방문 횟수 출력
print(visited[n-1][m-1])