https://www.acmicpc.net/problem/2178

🥚문제

---

🥚입력/출력

---

🍳코드

from collections import deque

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

def bfs(x1, y1, x2, y2):
    queue = deque()
    queue.append((x1, y1))
    visited = [[0]*(m) for _ in range(n)]
    visited[x1][y1] = 1
    while queue:
        v_x, v_y = queue.popleft()
        if v_x == x2 and v_y == y2:
            break
        # 상, 하, 좌, 우
        x_movs = [-1, 1, 0, 0]
        y_movs = [0, 0, -1, 1]
        for i in range(4):
            n_x = v_x + x_movs[i]
            n_y = v_y + y_movs[i]
            if 0 <= n_x < n and 0 <= n_y < m:
                if maze[n_x][n_y] == 1 and visited[n_x][n_y] == 0:
                    queue.append((n_x, n_y))
                    visited[n_x][n_y] += visited[v_x][v_y] + 1
    return visited[x2][y2]

print(bfs(0, 0, n-1, m-1))

---

🧂아이디어

• '나이트의 이동' 문제를 푼 뒤 슥삭 풀어낼 수 있었다.

• 2차원 리스트인 visited를 만들어, BFS를 수행하며 좌표 별로 그 위치까지 오는 데 밟은 칸의 총 개수를 저장해 주었다.

• visited[n_x][n_y] += visited[v_x][v_y] + 1
  좌표 (v_x, v_y)에서 상하좌우로 이동한 위치(n_x, n_y)의 칸이 1이고 방문 한 적이 없다면 (n_x, n_y) 칸에 (v_x, v_y)칸에 기록된 값 + 1을 기록한다.