김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 1726 로봇 파이썬(Python)

문제 링크

BFS 문제.
트리키한 점은 직진을 최대 3칸까지 한번에 갈 수 있다는 점, 그때 목적지 뿐 아니라 중간이 막혀 있으면 갈 수 없다는 점, 회전을 좌우로만 할 수 있다는 점 정도가 있다.
첫 번째 부분은 step = range(1, 4)를 선언해서 방향에 대한 각 스텝의 경우를 모두 확인했다.
두 번째 부분은 board[x+dx][y+dy]가 막혀 있으면 continue가 아니라 break를 함으로써 해결했다. 스텝은 낮은 수부터 시작하므로 중간이 막혀 있으면 더 큰 스텝을 확인하지 않고 탈출한다.
세 번째 부분은 turn = ((2, 3), (0, 1))을 선언하고 turn[d//2]를 참조해서, d in (0, 1)(동 또는 서)인 경우는 다음 방향으로 (2, 3)을, 그렇지 않은 경우는 다음 방향으로 (0, 1)을 선택하도록 만들었다.
그 외엔 다른 BFS 문제와 크게 다르지 않다.
특이하게도, Python 정답자 1등(60ms)의 답안이 다익스트라 알고리즘을 활용하는 걸로 되어 있던데, board 격자 그래프상에서 명령어 개수 상의 최단거리를 구하고 방향은 그냥 도는 데 필요한 코스트를 계산해서 케이스 별로 처리한 코드인 듯 하다. 아무래도 회전을 탐색에 포함시키는 대신 하드코딩해서 빠른 게 아닐까 생각한다.

#!python

from sys import stdin
from collections import deque
input = stdin.readline

# visited[i][j][k]: (i, j)에서 k 방향인 노드의 방문 여부
m, n = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(m)]
visited = [[[False for _ in range(4)] for _ in range(n)] for _ in range(m)]

# 인덱스는 0부터 시작하므로 1씩 빼줬다
src = list(map(lambda x: int(x) - 1, input().split()))
dst = list(map(lambda x: int(x) - 1, input().split()))

# q: BFS 위한 큐
# go: 직진시 갈 수 있는 4방향
# step: 직진할 때 갈 수 있는 거리
# turn[0]: 동(0) 또는 서(1)인 상태에서 다음 방향, 즉 남(2), 북(3)
# turn[1]: 남(2) 또는 북(3)인 상태에서 다음 방향, 즉 동(0), 서(1)
q = deque([src + [0]])
go = ((0, 1), (0, -1), (1, 0), (-1, 0))
step = range(1, 4)
turn = ((2, 3), (0, 1))

# BFS 수행
while q:
    x, y, d, c = q.popleft()
    if visited[x][y][d]:
        continue
    if [x, y, d] == dst:
        print(c)
        break
    visited[x][y][d] = True

    # 회전하는 경우
    for dd in turn[d//2]:
        q.append((x, y, dd, c + 1))

    # 직진하는 경우
    for s in step:
        dx, dy = go[d][0] * s, go[d][1] * s
        if not (0 <= x + dx < m and 0 <= y + dy < n) or board[x+dx][y+dy]:
            break
        q.append((x + dx, y + dy, d, c + 1))

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑