◼︎ 미로탈출
문제
N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.
입력
첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.
출력
첫째 줄에 최소 이동 칸의 개수를 출력한다.
입력 예시
5 6
101010
111111
000001
111111
111111
출력 예시
10
◼︎ 나의 풀이
# 미로 정의
n,m = map(int, input().split())
graph = []
for _ in range(n):
graph.append(list(map(int,input())))
# dfs 함수 정의
def bfs(graph, start_x,start_y):
visited = [] # 방문노드의 인덱스를 튜플로 저장
queue_x = [start_x] # 큐에 있는 노드들의 x좌표를 저장
queue_y = [start_y] # 큐에 있는 노드들의 y좌표를 저장
while queue_x: # 큐에 노드가 있을 동안 반복
current_x = queue_x.pop() # 현재노드의 x좌표
current_y = queue_y.pop() # 현재노드의 y좌표
visited.append((current_x, current_y)) # 방문노드에 추가
for node in [(current_x+1, current_y),(current_x, current_y+1)]: # 현재 노드의 오른쪽, 아래쪽 노드 확인하기
if (node[0] <= n) and (node[1] <= m): # 그래프 범위 내에 있고
if (node not in visited) and (graph[node[0]-1][node[1]-1] != 0): # 아직 방문 전이고 괴물이 없다면
queue_x.append(node[0]) # 큐에 추가한다
queue_y.append(node[1])
return visited
print(len(bfs(graph,1,1)) # 방문 노드의 개수를 출력◼︎ 어떻게 풀었나?
- graph: 2차원 리스트로 구현
- 외워둔 bfs 함수 로직을 일단 쓰고 수정했다.
- 책에 나와있는 각 노드에 1씩 더해나가는 아이디어는 떠올리지 못했다
- 대신 큐에 저장된 인덱스에 해당되는 노드마다 1, 0을 체크하며, 1일 경우에만 방문하고 visited에 추가하였다.
상세 풀이
- 일단 아래와 같이 기본 bfs함수를 작성했다.
def bfs_stack(adjacent_graph, start_node):
queue = [start_node]
visited = []
while queue:
current_node = queue.pop()
visited.append(current_node)
for adjacent_node in adjacent_graph[current_node]:
if adjacent_node not in visited and :
queue.append(adjacent_node)
return visited- 쓰고 보니 해당 함수는 1차원 노드에 버전이라, 2차원 그래프 노드버전으로 쪼개줬다
- start_node는 start_x와 start_y로
- current_node는 current_x와 current_y로
- queue는 queue_x와 queue_y로 쪼갰다
- visited에 저장하는 것도 정수가 아닌, (x위치,y위치)꼴의 튜플로 변경했다
def bfs(graph, start_x,start_y):
current_x = queue_x.pop()
current_y = queue_y.pop()
queue_x = [start_x]
queue_y = [start_y]
visited.append((current_x, current_y))◼︎ 시행착오
- adjacent_node 부분은 문제마다 다르게 설정해야하는 듯. 여기서는 현재 노드의 주변 노드 인덱스를 리스트 꼴로 adjacent_node자리에 넣어주었다. * 근데 사실 이 방법은 좀 비효율적이다. dx, dy에 각각 리스트를 넣어주는 꼴을 앞으로는 연습해보자.
for node in [(current_x+1, current_y),(current_x, current_y+1)]:- 계속해서 index 에러가 뜬다면, 그래프의 행과 열에 대한 범위를 설정했는지 확인해야겠다! for문의 반복 범위는 문제 없는 것 같은데 뭐가 문제인지 모르겠어서 시간이 좀 들었다.
if (node[0] <= n) and (node[1] <= m):- 내 코드에 몇가지 수정해야하는 것들이 보인다. 방문 노드 리스트를 저장할 때 큐를 사용해야 하며, 오른쪽과 아래쪽 뿐 아니라 상하좌우로 이동할 수 있도록 수정해야 한다.
고칠점 1. 이동할 4가지 방향 정의하기
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]고칠점 2. 4가지 방향에 있는 노드에 대해 큐 넣/말 결정하기
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]고칠점 3. 방문 노드 리스트(대기열 또는 큐)에는 deque사용
여기서 x,y는 시작점의 솔루션이다.
queue = deque()
queue.append((x, y))고칠점 4. if~continue 잘 사용하기
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue기타 사항 1. 튜플을 이용한 변수 할당에 익숙해지기
x,y = queue.popleft()기타 사항 2. queue 대기열 업데이트 하는 거 잊지 말기!
◼︎ 책 솔루션
from collections import deque
# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# BFS 소스코드 구현
def bfs(x, y):
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()
queue.append((x, y))
# 큐가 빌 때까지 반복하기
while queue:
x, y = queue.popleft()
# 현재 위치에서 4가지 방향으로의 위치 확인
for i in range(4):
nx = x + dx[i]
ny = 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]
# BFS를 수행한 결과 출력
print(bfs(0, 0))
.