문제
https://www.acmicpc.net/problem/2178
[실버 1]
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
아이디어
시작점에서부터 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하는 BFS를 통해 구현한다.
경로 길이를 구해야 하기 때문에 단순한 방문처리가 아닌 현재 노드까지의 거리를 합하여 방문처리를 해주어야 한다.
상하좌우로 이동할 때마다 다음 세가지를 고려해야 한다.
1️⃣ 미로 찾기 공간을 벗어났는가
2️⃣ 괴물이 있는 부분인가 (1인가)
3️⃣ 처음 방문하는 노드인가
풀이
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]
# BFS
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 = y + dy[i]
# 미로찾기 공간을 벗어났을 경우 continue(무시)
if nx < 0 or ny < 0 or nx >= n or ny >= m:
continue
# 0:괴물이 있는 부분인 경우 무시
if graph[nx][ny] == 0:
continue
# 1:괴물이 없는 부분이고 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1 # 현재 노드 (거리)값 + 1 하여 다음 노드에 기록
queue.append((nx, ny))
# 탈출구(마지막 칸)까지의 최단 거리 반환
return graph[n-1][m-1]
print(bfs(0, 0))
print(graph)두번째 시도 풀이 및 해설
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):
q = deque()
q.append((x, y))
while q: # q가 빌 때까지
# 현재 노드
x, y = q.popleft()
# print("x, y : " + str(x), str(y))
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
continue
if graph[nx][ny] == 0: # 벽인 경우 continue
continue
if graph[nx][ny] == 1: # 이동할 수 있는 칸인 경우 & 1은 처음 방문함을 뜻함
graph[nx][ny] = graph[x][y] + 1 # 현재 칸 + 1해서 거리 갱신
q.append((nx, ny))
# print(nx, ny)
# for i in range(n):
# print(graph[i])
return graph[n-1][m-1] # 도착 위치의 값 반환
print(bfs(0, 0))주석처리된 부분을 프린트 하면, 너비 우선 탐색 과정이 터미널에 출력된다.
x, y는 현재 노드 좌표이고, nx, ny는 상하좌우로 이동한 노드 중 하나의 좌표이다.
x, y : 0 0 - 큐에서 꺼냄
nx, ny : 1 0 # 하 로 이동 (상 좌 우 막힘), 큐 삽입
[1, 0, 1, 1, 1, 1]
[2, 0, 1, 0, 1, 0]
[1, 0, 1, 0, 1, 1]
[1, 1, 1, 0, 1, 1]
x, y : 1 0 - 큐에서 꺼냄
nx, ny : 0 0 - 상 으로 이동, 큐 삽입
[3, 0, 1, 1, 1, 1]
[2, 0, 1, 0, 1, 0]
[1, 0, 1, 0, 1, 1]
[1, 1, 1, 0, 1, 1]
nx, ny : 2 0 - 하 로 이동 (좌 우 막힘), 큐 삽입
[3, 0, 1, 1, 1, 1]
[2, 0, 1, 0, 1, 0]
[3, 0, 1, 0, 1, 1]
[1, 1, 1, 0, 1, 1]
x, y : 0 0 - 큐에서 꺼냄
nx, ny : 1 0 - 하 로 이동 (상 좌 우 막힘), 값이 1이 아니므로(이미 방문했으므로) 큐 삽입X
[3, 0, 1, 1, 1, 1]
[2, 0, 1, 0, 1, 0]
[3, 0, 1, 0, 1, 1]
[1, 1, 1, 0, 1, 1]
x, y : 2 0 - 큐에서 꺼냄
nx, ny : 1 0 - 상 으로 이동, 큐 삽입X
[3, 0, 1, 1, 1, 1]
[2, 0, 1, 0, 1, 0]
[3, 0, 1, 0, 1, 1]
[1, 1, 1, 0, 1, 1]
nx, ny : 3 0 - 하 로 이동, 큐 삽입
[3, 0, 1, 1, 1, 1]
[2, 0, 1, 0, 1, 0]
[3, 0, 1, 0, 1, 1]
[4, 1, 1, 0, 1, 1]
x, y : 3 0 - 큐에서 꺼냄
nx, ny : 2 0
[3, 0, 1, 1, 1, 1]
[2, 0, 1, 0, 1, 0]
[3, 0, 1, 0, 1, 1]
[4, 1, 1, 0, 1, 1]
nx, ny : 3 1 - 우 로 이동, 큐 삽입
[3, 0, 1, 1, 1, 1]
[2, 0, 1, 0, 1, 0]
[3, 0, 1, 0, 1, 1]
[4, 5, 1, 0, 1, 1]
x, y : 3 1
nx, ny : 3 0
[3, 0, 1, 1, 1, 1]
[2, 0, 1, 0, 1, 0]
[3, 0, 1, 0, 1, 1]
[4, 5, 1, 0, 1, 1]
nx, ny : 3 2
[3, 0, 1, 1, 1, 1]
[2, 0, 1, 0, 1, 0]
[3, 0, 1, 0, 1, 1]
[4, 5, 6, 0, 1, 1]
x, y : 3 2
nx, ny : 2 2
[3, 0, 1, 1, 1, 1]
[2, 0, 1, 0, 1, 0]
[3, 0, 7, 0, 1, 1]
[4, 5, 6, 0, 1, 1]
nx, ny : 3 1
[3, 0, 1, 1, 1, 1]
[2, 0, 1, 0, 1, 0]
[3, 0, 7, 0, 1, 1]
[4, 5, 6, 0, 1, 1]
x, y : 2 2
nx, ny : 1 2
[3, 0, 1, 1, 1, 1]
[2, 0, 8, 0, 1, 0]
[3, 0, 7, 0, 1, 1]
[4, 5, 6, 0, 1, 1]
nx, ny : 3 2
[3, 0, 1, 1, 1, 1]
[2, 0, 8, 0, 1, 0]
[3, 0, 7, 0, 1, 1]
[4, 5, 6, 0, 1, 1]
x, y : 1 2
nx, ny : 0 2
[3, 0, 9, 1, 1, 1]
[2, 0, 8, 0, 1, 0]
[3, 0, 7, 0, 1, 1]
[4, 5, 6, 0, 1, 1]
nx, ny : 2 2
[3, 0, 9, 1, 1, 1]
[2, 0, 8, 0, 1, 0]
[3, 0, 7, 0, 1, 1]
[4, 5, 6, 0, 1, 1]
x, y : 0 2
nx, ny : 1 2
[3, 0, 9, 1, 1, 1]
[2, 0, 8, 0, 1, 0]
[3, 0, 7, 0, 1, 1]
[4, 5, 6, 0, 1, 1]
nx, ny : 0 3
[3, 0, 9, 10, 1, 1]
[2, 0, 8, 0, 1, 0]
[3, 0, 7, 0, 1, 1]
[4, 5, 6, 0, 1, 1]
x, y : 0 3
nx, ny : 0 2
[3, 0, 9, 10, 1, 1]
[2, 0, 8, 0, 1, 0]
[3, 0, 7, 0, 1, 1]
[4, 5, 6, 0, 1, 1]
nx, ny : 0 4
[3, 0, 9, 10, 11, 1]
[2, 0, 8, 0, 1, 0]
[3, 0, 7, 0, 1, 1]
[4, 5, 6, 0, 1, 1]
x, y : 0 4
nx, ny : 1 4 - 하 로 이동, 큐 삽입
[3, 0, 9, 10, 11, 1]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 1, 1]
[4, 5, 6, 0, 1, 1]
nx, ny : 0 3 - 좌 로 이동, 이미 방문 큐 삽입X
[3, 0, 9, 10, 11, 1]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 1, 1]
[4, 5, 6, 0, 1, 1]
nx, ny : 0 5 - 우 로 이동, 큐 삽입
[3, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 1, 1]
[4, 5, 6, 0, 1, 1]
x, y : 1 4
nx, ny : 0 4
[3, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 1, 1]
[4, 5, 6, 0, 1, 1]
nx, ny : 2 4 - 큐 삽입
[3, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 13, 1]
[4, 5, 6, 0, 1, 1]
x, y : 0 5
nx, ny : 0 4 - 이미 방문
[3, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 13, 1]
[4, 5, 6, 0, 1, 1]
x, y : 2 4
nx, ny : 1 4
[3, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 13, 1]
[4, 5, 6, 0, 1, 1]
nx, ny : 3 4 - 큐 삽입
[3, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 13, 1]
[4, 5, 6, 0, 14, 1]
nx, ny : 2 5 - 큐 삽입
[3, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 13, 14]
[4, 5, 6, 0, 14, 1]
x, y : 3 4
nx, ny : 2 4
[3, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 13, 14]
[4, 5, 6, 0, 14, 1]
nx, ny : 3 5 - 큐 삽입
[3, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 13, 14]
[4, 5, 6, 0, 14, 15]
x, y : 2 5
nx, ny : 3 5
[3, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 13, 14]
[4, 5, 6, 0, 14, 15]
nx, ny : 2 4
[3, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 13, 14]
[4, 5, 6, 0, 14, 15]
x, y : 3 5
nx, ny : 2 5
[3, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 13, 14]
[4, 5, 6, 0, 14, 15]
nx, ny : 3 4
[3, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 13, 14]
[4, 5, 6, 0, 14, 15]
15 - 큐가 비었으므로 종료 후 도착 위치 값 반환Comment
음료수 얼려 먹기 문제와 마찬가지로 그래프 자체에 방문처리를 하는 문제였다. 특이하다 할 수 있는 부분은 단순한 방문처리가 아닌 거리값으로 갱신하는 것인데, 현재 노드 값에 1을 더하여 다음 노드 값을 저장하여 탈출구까지의 최단거리를 구한다.
상하좌우 이동에 대한 구현에 대해 기억하자.
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]로 정의한 후 반복문을 통해 좌표를 움직이자.
덧붙여 풀이 마지막줄에 탐색이 끝난 그래프를 출력해보았고, 결과는 아래와 같다.
[[3, 0, 5, 0, 7, 0],
[2, 3, 4, 5, 6, 7],
[0, 0, 0, 0, 0, 8],
[14, 13, 12, 11, 10, 9],
[15, 14, 13, 12, 11, 10]]먼저 시작점 (1,1)의 값이 1이 아닌 3으로 되어 있다. 이는 (1,2)에서 처음 방문한다고 인지한 후 값을 2+1로 갱신한 것이고, 결과값에는 크게 상관이 없다.
2차 풀이 후 comment
풀이를 보지 않고 풀으려니 의문점이 드는 부분이 많았다.
- 먼저 NM 크기의 배열에서 x, y좌표 개념을 반대로 생각하고 있었다.
if문 조건 중 탐색 범위를 벗어났는지 확인하는 부분에서 dx >= m, dy >= n 이라고 생각했는데
34 크기의 배열에서 graph[2][1]이라 하면
○○○○
○○○○
○●○○
이므로 dx >= n, dy >= m이 맞다.
-
또한 파이썬 입력받는 부분도 조금 헷갈렸다. 이 부분은 따로 포스팅을 하려고 한다.
-
이미 풀어본 내용이어서 그런지 대략적인 구성은 알았으나 로직이 헷갈렸다. 사실 모르는 거겠지 ..
큐에서 가장 먼저 들어간 노드를 꺼내고, 그 노드(현재 노드라고 하겠다.)에서 상하좌우를 움직이며 1. 탐색범위를 벗어났는가 2. 벽인가 3. 뚫려있으면 처음 방문하는가 확인하고, 3번에 해당하는 경우 최단거리 값을 갱신한 후, 큐에 삽입한다.
큐가 빌 때까지 위의 내용에 대해 반복하고, 반복이 끝나면(큐가 비면) 도착위치의 값을 반환한다.
