n X m 크기의 배열(미로)이 주어질 때,
(0, 0)에서 (n - 1, m - 1)까지의 최단 이동 횟수를 출력하는 문제이다.
2차원 배열, 그래프 문제이기 때문에 DFS/BFS를 사용하면 되는데..
최단 거리와 관련되어 있으므로 BFS로 접근하면 된다.
탐색하려는 다음 좌표가 배열의 범위인지 신경 썼고,
코드(정답)는 다음과 같다.
# 2178
import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split())
graph = []
for _ in range(n):
graph.append(list(map(int, sys.stdin.readline().rstrip())))
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
queue = deque([(0, 0)])
while queue:
x, y = queue.popleft()
for i in range(4):
next_x = x + dx[i]
next_y = y + dy[i]
if next_x >= 0 and next_x <= n - 1 and next_y >= 0 and next_y <= m - 1:
if graph[next_x][next_y] == 1:
queue.append((next_x, next_y))
graph[next_x][next_y] = graph[x][y] + 1
print(graph[n - 1][m - 1])정답을 구하는 것과는 별개이긴 한데..
사용자 입력이 아래와 같을 때 위의 코드를 실행시키면,
4 6
101111
101010
101011
111011graph[0][0] 값이 3이다.
graph[x][y]가 (x, y)까지의 최단 거리이니 입력에 상관없이 항상 graph[0][0] == 1이 나와야 하지 않나?
if graph[next_x][next_y] == 1:
queue.append((next_x, next_y))
# 어떤 위치에서 graph[0][0]의 값이 증가되는가?
if next_x == 0 and next_y == 0:
print(x, y)
graph[next_x][next_y] = graph[x][y] + 1위와 같은 코드를 추가하면..
(x, y) == (1, 0)일 때 윗 방향으로 탐색이 가능하고,
graph[1][0] == 2이므로 graph[0][0] = 2 + 1이 된다.
만약 graph[n - 1][m - 1]만 구하는 게 아니라,
값이 1인 모든 좌표까지의 최단 거리 그래프를 출력하려면 아래와 같이 코드를 수정할 수 있다.
물론 이 코드도 정답이다.
# 2178
import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split())
graph = []
for _ in range(n):
graph.append(list(map(int, sys.stdin.readline().rstrip())))
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
queue = deque([(0, 0)])
while queue:
x, y = queue.popleft()
for i in range(4):
next_x = x + dx[i]
next_y = y + dy[i]
if next_x >= 0 and next_x <= n - 1 and next_y >= 0 and next_y <= m - 1:
if graph[next_x][next_y] == 1:
queue.append((next_x, next_y))
# 다음 좌표가 (0, 0)이 아닌 경우만 값을 업데이트
if next_x != 0 or next_y != 0:
graph[next_x][next_y] = graph[x][y] + 1
# print(graph)
print(graph[n - 1][m - 1])헷갈리는 부분 정리
입력이 12345일 때, 아래 두 코드의 차이점?
1) list(map(int, sys.stdin.readline().rstrip())) # [1, 2, 3, 4, 5]
2) list(map(int, sys.stdin.readline().split())) # [12345]1)
rstrip()은 오른쪽 공백 제거
-> '12345' (리스트가 아니라 그대로 문자열!)
map()은 두 번째 인자(리스트, 문자열 등)의 각 요소를 첫 번째 타입(int 등)으로 변환
-> 여기선 문자열의 각 문자를 순회하며 정수로 변환
-> '1', '2', '3', '4', '5'가 각각 1, 2, 3, 4, 5로 변환
-> 1, 2, 3, 4, 5가 저장된 map 객체
list()는 해당 객체를 리스트로 변환
-> [1, 2, 3, 4, 5]
2)
split()은 공백을 기준으로 문자열을 분리한 뒤 '리스트'로 반환
-> ['12345']
map()은 두 번째 인자(리스트 등)의 각 요소를 첫 번째 타입(int 등)으로 변환
-> 12345가 저장된 map 객체
list()는 해당 객체(map 등)를 리스트로 변환
-> [12345]
DFS, BFS는 어떤 상황에서 구분해서 쓸 수 있을까?
DFS가 유리한 경우
- 재귀적인 특징과 백트래킹을 이용하여 모든 경우를 하나씩 전부 탐색하는 경우
- 그래프의 크기가 클 경우
- 최적의 답을 찾는 경우가 아닌 경우
- 경로의 특징을 저장해야 하는 경우(경로의 가중치, 이동 과정에서의 제약 등)
BFS가 유리한 경우
- 최단 거리, 최단 횟수를 구하는 경우
- 최적의 답을 찾는 경우(BFS는 제일 먼저 발견되는 값이 최적이다!)
- 탐색의 횟수를 구해야 하는 경우
참고
