BOJ 백준 5014: 스타트링크

Table of contents

들어가며

이 문제는 그래프 탐색 문제입니다.
그래프 탐색 방법 중 BFS를 이용한 문제입니다.
이 문제가 BFS 문제라는 걸 인지하면 상당히 쉽게 풀리는 문제입니다.
즉, 발상이 어렵다고 할 수 있겠죠? 🥲 BOJ 백준 1697: 숨바꼭질문제와 발상이 똑같다고 보면 됩니다 ㅎㅎ (저도 이 문제 푼 기억이 나서, 처음에는 투 포인터로 접근하면서 끙끙대다가 풀었습니다.)

풀이 과정

처음에는 F가 최대 백만이고, U와 D 눌린 횟수의 합이 최소인 것을 구한다고 생각을 해서, $O(N)$ 만에 처리가 되고 U와 D를 가리키는 포인터를 두어서 문제를 해결할 수 있는 투포인터 기법으로 문제를 풀려고 했습니다.
그런데 포인터(st)의 상한선을 정할 수 없어서, TLE를 받겠다 싶었고, 이 문제를 1차원 좌표계로 놓고, BFS를 쓰면 풀리겠다는 생각이 들었습니다.
그래서 바로 BFS로 풀었고, AC를 받았습니다.
하기 코드는 AC를 받은 코드입니다.

import sys
from collections import deque

input = sys.stdin.readline


def OOB(x):
    if x < 1 or x > F:
        return True
    return False


def bfs(start):
    q = deque()
    dist[start] = 1
    q.append(start)
    while q:
        cx = q.popleft()
        for dx in DX:
            nx = cx + dx
            if OOB(nx):
                continue
            if dist[nx] > 0:
                continue
            dist[nx] = dist[cx] + 1
            q.append(nx)


if __name__ == "__main__":
    F, S, G, U, D = map(int, input().rstrip().split())
    dist = [0 for _ in range(F + 1)]
    DX = [U, -D]
    DX = [*filter(lambda x: x != 0, DX)]
    bfs(S)
    if dist[G] > 0:
        print(dist[G] - 1)
    else:
        print("use the stairs")

아 그리고 심심해서 vim으로 풀었는데, 역시 sublime keymap이 편하다… vim은 정말 순수 재미용으로만 쓰자 ㅋㅋ