문제
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
해결 방법
아 진짜 런타임 오류 20번 봤다... ಥ_ಥ
- n, m 입력 받기
- graph 반복문으로 입력 받기
- BFS
- 방향 벡터로 돌면서 조건에 맞다면 인큐, 카운트
- BFS 마지막 반복문에서 카운트 리턴
이런 흐름으로 짜고 세부적으로 보자
👉 2번
graph = []로 리스트를 만든 후
반복문을 n번만큼 리스트를 삽입한다. = graph.append(list(map(int,input())))
👉 3번 def bfs(x, y):
1. 큐 deque 형태로 만들고 시작점 (x,y) 추가
2. 방향 벡터 (상, 하, 좌, 우)
3. 큐에 들어있는 만큼 반복문
4. 먼저 들어온 값 삭제 queue.popleft()
5. 4방향만큼 돌아보는 반복문
6. n,m의 리스트를 넘거나 값이 0이라면(벽이라면) continue로 바로 다음 반복문 진행
7. 값이 1이라면 카운트 후 인큐
8. 반복문이 다 끝나면 카운트 리턴
✨위의 3번-8이 왜 카운트를 의미할까?
제출
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int,input().split())
graph =[]
for _ in range(n):
graph.append(list(map(int,input().rstrip())))
def bfs(x, y):
queue = deque() #시작점 삽입
queue.append((x, y))
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] #방향벡터
while queue:
x, y = queue.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
if graph[nx][ny] == 0:
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))메모
내가 이 문제를 풀면서 가졌던 궁금증
💡방향 벡터와 BFS를 어떻게 합할까?
방향 벡터를 이용해 상, 하, 좌, 우를 돌다가 갈 수 있는 곳이 나오면 그 지점을 인큐한다.
💡카운트를 어떻게 할까?
처음에는 따로 방문한 곳을 체크할 리스트를 만들까 해봤지만 메모리를 아끼기 위해 기존의 리스를 이용해보자 싶었다.
✨그러면 카운트 할 때 도착해야 하는 목표지점인 graph[n-1][m-1]의 값에 +1을 해주고 마지막으로 더해진 값을 출력하면 된다!!! 그럼 이제 어떻게 더할지 고민해보자.
💡그러면 어떻게 더하냐?
1. graph[nx][ny] = graph[x][y] + 1 2. graph[nx][ny] += 1여기서 제일 많은 시간을 썼다ヾ(⌐■_■)ノ♪
다들 1번처럼 쓰는데 저게 왜... 카운트하는... 걸까... 난... 2번처럼... 생각했는데...
2번이 틀린 이유: 1번은 g[x][y]에 있는 값을 가져와서 1을 더한다는 뜻이다. 2번의 g[nx][ny]는 바뀌는 새로운 위치 값이다. 의미가 완전히 달라진다. 나 바보 🤦♀️
