백준 14940 쉬운 최단거리 문제 풀이
백준 온라인 저지, 14940번: 쉬운 최단거리
도입
쉬운 최단거리 문제는 전형적인 형태의 격자 그래프에서의 BFS/DFS 문제이다. 그래프 탐색이 익숙하다면 쉽게 구현 가능하지만, 충분히 경험하지 못했다면 상태 전이 방법을 고민해야할 수도 있다.
*사실 모든 그래프 탐색 문제는 그래프를 탐색하면서 상태를 함께 전이해야 하므로 이 문제의 특징은 아니다.
문제 풀이
이 문제에서 전이할 상태 값은 각 지점으로부터 목표 지점까지의 최단 거리이다. BFS/DFS를 사용하여 각 지점의 최단거리를 전부 갱신하면 된다.
이 문제에서의 상태 값인 최단 거리는 두 개 시점에서 전이하여 저장할 수 있다.
- 큐에 인접한 위치로 이동을 예약할 때, 인접한 위치의 최단 거리를 현재 위치의 최단 거리 + 1로 갱신한다.
- 큐에 이동을 예약할 때, 상태값을 함께 전달한다. 이후 예약한 값을 큐에서 인출할 때 전달한 상태값을 사용하여 최단 거리를 갱신한다.
1번 방법은 항상 현재 시점과 다음 시점의 값을 저장하는 저장소에 접근할 수 있음이 보장되어야 한다. 아래의 코드에서 result 변수에 해당하는 데이터가 항상 존재하여야 한다.
2번 방법은 큐에 상태값을 함께 전달하므로, 큐에 같은 갯수만큼 탐색을 예약하더라도 더 많은 큐 메모리를 요구한다. 이 문제에 해당하는 내용은 아니지만 필요에 따라 아래의 코드에서 result 변수에 해당하는 데이터를 생성하지 않고도 처리할 수 있다.
1번 방법
1
2
3
4
5
6
7
8
9
10
11
dt = ((1, 0), (-1, 0), (0, 1), (0, -1))
q: deque[tuple[int, int]] # tuple[int, int] = (y, x)
result: list[list[int]] # 최단 거리 결과를 저장하는 2차원 리스트
while q:
y, x = q.popleft()
for dy, dx in dt:
ny, nx = y + dy, x + dx
...
result[ny][nx] = result[y][x] + 1
q.append((ny, nx))
2번 방법
1
2
3
4
5
6
7
8
9
10
11
dt = ((1, 0), (-1, 0), (0, 1), (0, -1))
q: deque[tuple[int, int, int]] # tuple[int, int, int]
result: list[list[int]] # 최단 거리 결과를 저장하는 2차원 리스트
while q:
y, x, step = q.popleft()
result[y][x] = step # 현재 위치의 최단 거리를 갱신
for dy, dx in dt:
ny, nx = y + dy, x + dx
...
q.append((ny, nx, step + 1))
참고: 입력으로 주어진 값에 결과 값 덮어쓰기하여 메모리 절약하기
토마토 문제에서는 메모리를 절약하기 위해 입력으로 주어진 격자 그래프에 상태 값, 토마토가 익은 시점을 덮어쓰기했다.
이 문제에서는 의미가 중복되지 않으면서 겹치는 입력값의 범위와 출력값의 범위가 조금더 많다. 토마토 문제에서는 각 지점의 상태를 -1, 0, 1로 표현하였고 출력에서도 -1, 0 의미를 재사용하기 용이했기 때문에, 입력으로 받아온 값에 그대로 계산 결과를 덮어씌워 처리하는 것에 부담이 없었다.
하지만 이 문제에서는 0, 1, 2를 입력 상태 값으로 사용하였고, 결과 값에서의 0, 1, 2의 의미와 동치이거나 비슷한 것으로 간주하기 어렵다.
따라서 같은 전략을 사용하려면, 결과값을 2씩 시프트하거나 음수 범위에 저장하여 입력과 출력에서의 정의가 서로 겹치지 않도록 조정해야한다. 결과 리스트를 한 개 더 만들어 메모리를 더 사용할지, 결과를 2씩 시프트하거나 음수 범위에 저장한 후 실제 결과를 출력할 때 되돌리는 연산을 더 추가할지 결정할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
field: list[list[int]] # 입력으로 주어진 격자 그래프
# 입력으로 주어진 값과 의미가 겹치지 않게 하기 위해
# 양수 값을 음수 범위에 저장
field[y][x] = -actual_value
# 음수로 변환된 값을 되돌리기하여 출력
print(-field[y][x])
# 입력으로 주어진 값이 0, 1, 2만 사용하므로 2 이상 양수 방향으로 시프트
# *목표지점(2)는 거리가 0이므로 정수값 2는 의미를 중복 부여할 수 있다.
field[y][x] = actual_value + 2
# 시프트한 값을 되돌리기하여 출력
print(field[y][x] - 2)