코딩테스트 2 (6.12)

n x m 격자가 주어집니다. 당신은 격자의 (1, 1)에서 (n, m)으로 이동하려고 합니다.
격자의 각 칸은 평지, 숲, 강 중 하나입니다. 당신은 현재 위치에서
상, 하, 좌, 우로 인접한 평지 혹은 숲으로 이동할 수 있으며, 강으로는 이동할 수 없습니다.
또한 당신은 하루에 최대 k칸만을 이동할 수 있습니다.
야영을 할 경우 다음날에 다시 최대 k칸을 이동할 수 있습니다.
단, 야영은 오직 평지에서만 가능합니다. 야영을 하지 않는다면 다음날에 이동을 할 수 없습니다.
하루에 이동 가능한 칸을 모두 소모하지 않았더라도 원한다면 야영을 할 수 있습니다.

야영을 할 때마다 야영 물자를 소모하기 때문에 당신은 야영횟수를 최소로 하며 (n, m)을 이동하려 합니다.

격자의 정보가 담김 1차원 문자앨 배열 grid, 하루에 이동할 수 있는 칸의 수를 나타내는 정수 k가 매개변수로 주어집니다.
이때 (1, 1)에서 (n, m)으로 이동하기 위해 필요한 최소 아양 횟수를 return 하도록 solution 함수를 완성해주세요.

예시)
k = 4 일때 (1 , 1)에서 (3, 4)로 이동하는 예시

..FF
###F
###.

- 격자의 가장 왼쪾 위가 (1, 1), 가장 오른쪽 아래가 (3, 4) 입니다.
- " . "은 평지, "F"는 숲, "#"은 강을 의미합니다.

(1, 1) -> (1, 2) -> 야영 -> (1, 3) -> (1, 4) -> (2, 4) -> (3, 4)

다른 방법으로도 (3, 4)에 도착할 수 있지만, 야영을 하지 않고 (3, 4)에 도착하는 방법은 없습니다.

문제풀이
구현문제
문제 형태에 대한 예제가 떠오르기 시작한다.
이코테 문제 유형을 좀 더 여러번 보며 익숙하게 해야겠다.

from collections import deque

n, m = map(int, input().split())
graph = []
for i in range(n):
	graph.append(list(map(int, input())))
    
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
	queue = deque()
    queue.append((x, y)
    while queue:
    	x, y = queue.popleft()
    # 현재 위치에서 네 방향으로의 위치 확인
    for i in range(4):
    	nx = x + dx[i]
        ny = x + dy[i]
        # 미로 찾기 공간을 벗어난 경우 무시
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
        	continue
        # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
        if graph[nx][ny] == 1:
        	graph[nx][ny] = graph[x][y] + 1
            queue.append((nx, ny))
     # 가장 오른쪽 아래까지의 최단 거리 반환
     return graph[n - 1][m - 1]
     
print(bfs(0, 0))