(전공복습) 데이터과학 4. 시각화
차례
백준(BOJ) 14948 군대탈출하기 파이썬(Python)
해병성채에서 탈출하기 위한 BFS 문제.
병영 크기가 \(100 \times 100\)밖에 안 되기 때문에 비효율적으로도 잘 풀린다.
BFS, 다익스트라, 파라메트릭 서치 등 다양한 풀이가 존재하는 것 같다.
여기서는 비효율적이지만 단순하게 풀어보자.
우선, 여느 문제들처럼 상, 하, 좌, 우 한 칸씩 이동이 가능하고, 보드를 넘어갈 수는 없다.
하지만, 탐색 중 딱 한 번, 장비를 사용해 2칸을 움직일 수 있다.
따라서 최댓값을 구하는 배열(리스트)을 장비를 이미 사용한 경우와 그렇지 않은 경우 2개로 나누어 풀면 된다.
아직 장비를 안 쓴 경우 required["normal"]에 답을 저장한다.
반면, 이미 장비를 쓴 경우 required["jump"]에 답을 저장한다.
이번 이동에서 장비를 안 썼다면, normal에서 normal로, 또는 jump에서 jump로 상태가 그대로일 것이다.
반면, 이번 이동에서 장비를 쓰면, normal에서 jump로 상태가 변하고, jump에서는 이미 장비를 썼으므로 사용 자체가 불가능하다.
이제 이렇게 구한 required를 visited 대신에 사용해서 가능한 경우를 모두 탐색해보면 된다(즉, 실제로는 BFS와 달리 같은 지점을 여러 번 탐색할 수 있다.)
다만, 어떤 칸에 대해서 그 답이 그 칸의 원래 레벨보다 작아질 수 없음은 유의하자.
즉, 레벨 10짜리 칸이 있다면, 그 칸은 아무리 적어도 최소한 레벨 10이 있어야 도달할 수 있다는 뜻이다.
이런 지점들에 유의하며 BFS를 수행하면 쉽게 풀 수 있다.
이때, 우선순위 큐를 쓰면 현재 값이 제일 작은 것부터 수행할 수 있고(마치 다익스트라처럼), 따라서 맨 처음 목표 지점에 도달했을 때가 최대 레벨의 최솟값이 된다.
나도 제출하고 깨달았는데, 그냥 큐를 써도 충분히 제한 시간 안에 풀려서 큰 상관은 없을 듯.
참고로, 파라메트릭 서치로 푸는 방법은, 이 문제를 \(x\)레벨일 때 목표지점에 도달할 수 있느냐는 결정 문제로 바꾸고, 이분 탐색으로 알맞은 \(x\)를 찾아내는 것이다.
처음에 \(N\)과 \(M\)의 범위를 제대로 숙지하지 않아서 떠올리지 못했는데, 그랬다면 나도 이 풀이를 먼저 고려했을 듯.
#!python
from sys import stdin
from collections import deque
input = stdin.readline
INF = float("inf")
# bfs 수행하는 함수
def bfs():
q = deque([(0, 0, "normal")])
required["normal"][0][0] = required["jump"][0][0] = level[0][0]
while q:
x, y, status = q.popleft()
# 장비를 쓰지 않으면 1칸 이동
for dx, dy in directions["normal"]:
# 병영을 넘거나 기존에 이미 더 작은 답을 찾았다면 넘어간다
if (
not (0 <= x + dx < n and 0 <= y + dy < m)
or required[status][x][y] >= required[status][x + dx][y + dy]
):
continue
# 큐에 넣고 답을 갱신한다
# 이때, 답은 그 칸의 레벨보다 작을 수 없다
q.append((x + dx, y + dy, status))
required[status][x + dx][y + dy] = max(
required[status][x][y], level[x + dx][y + dy]
)
# status가 "jump"라면 이미 장비를 쓴 것
# status가 "normal"이라면 아직 장비를 쓸 수 있다
if status == "jump":
continue
# 장비를 쓰면 2칸씩 이동
# 세부 동작은 상동
# 다만 장비를 쓰면 상태가 normal에서 jump로 바뀜에 유의
for dx, dy in directions["jump"]:
if (
not (0 <= x + dx < n and 0 <= y + dy < m)
or required["normal"][x][y] >= required["jump"][x + dx][y + dy]
):
continue
q.append((x + dx, y + dy, "jump"))
required["jump"][x + dx][y + dy] = max(
required["normal"][x][y], level[x + dx][y + dy]
)
n, m = map(int, input().split())
level = [list(map(int, input().split())) for _ in range(n)]
# required는 i, j에 도달하기 위한 최소 레벨
required = {}
required["normal"] = [[INF] * m for _ in range(n)]
required["jump"] = [[INF] * m for _ in range(n)]
# directions는 움직일 수 있는 방향과 거리
directions = {}
directions["normal"] = ((1, 0), (0, 1), (-1, 0), (0, -1))
directions["jump"] = ((2, 0), (0, 2), (-2, 0), (0, -2))
# bfs 수행 후 최소 거리를 출력
bfs()
print(min(required["normal"][-1][-1], required["jump"][-1][-1]))
2024
맨 위로 이동 ↑2023
백준(BOJ) 2045 마방진 / 3192 매직 스퀘어 파이썬(Python)
문제 링크 문제 링크
세그먼트 트리
개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...
벨만-포드 알고리즘
개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...
다익스트라 알고리즘
개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...