[백준] 5014번: 스타트링크 - Python

링크: https://www.acmicpc.net/problem/5014

5014번: 스타트링크

아이디어

• f - 총 층수
• s - 현재 층
• g - 스타트링크의 층
• u - 위로 u칸 가는 버튼
• d - 아래로 d칸 가는 버튼
• bfs로 위와 아래로 가는 경우로 나눠 그래프를 그린다.
• 방문처리와 깊이를 동시에 판별하는 배열을 사용
• g에 방문처리가 됐으면 방문처리 배열의 값을 반환

구현(틀림)

import sys

input = sys.stdin.readline

# f - 총 층수
# s - 현재 층
# g - 스타트링크의 층
# u - 위로 u칸 가는 버튼
# d - 아래로 d칸 가는 버튼

f, s, g, u, d = list(map(int, input().split()))
depth = [0] * (f+1)
from collections import deque

q = deque()
q.append(s)

while(q):
    now = q.popleft()
    if depth[g] != 0:
        print(depth[g])
        exit()

    for i in [u, -d]:
        next = now + i
        if 0< next and next<=f:
            if depth[next] == 0:
                q.append(next)
                depth[next] = depth[now] + 1 

print("use the stairs")

흠..

틀린 원인 분석

• 첫 시작지점을 방문처리를 하지 않았다.
• 위처럼 깊이와 방문처리를 같이하는 배열에는 미리 첫 시작지점에 방문했다는 표시를 할 수 없으니 새로운 방문처리 배열을 만들어줬다.

구현(정답)

import sys

input = sys.stdin.readline

# f - 총 층수
# s - 현재 층
# g - 스타트링크의 층
# u - 위로 u칸 가는 버튼
# d - 아래로 d칸 가는 버튼

f, s, g, u, d = list(map(int, input().split()))
if s==g:
    print(0)
    exit()
depth = [0] * (f+1)
check = [False] * (f+1)
check[s] = True
from collections import deque

q = deque()
q.append(s)

while(q):
    now = q.popleft()
    if depth[g] != 0:
        print(depth[g])
        exit()

    for i in [u, -d]:
        next = now + i
        if 0< next and next<=f:
            if not check[next]:
                q.append(next)
                depth[next] = depth[now] + 1 
                check[next] = True

print("use the stairs")

예스~!

마무리

• 방문처리와 깊이를 동시에 신경쓰는 문제는 꼭 첫 시작지점을 방문했다고 할지 말지를 잘 생각하자