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

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

5014번: 스타트링크

 

내 코드

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

total,now,dst,u,d= map(int, input().split())
visited = [False for _ in range(total+1)]
cnt = [0 for _ in range(total+1)]

def bfs(s):
    q = deque()
    q.append(s)
    visited[s]=True
    while q:
        s = q.popleft()
        if s == dst:
            return cnt[dst]
        for dm in (s + u, s-d):
            if 1 <= dm <=total and not visited[dm]:
                visited[dm]= True
                cnt[dm] = cnt[s]+1
                q.append(dm)
    if cnt[dst] == 0:
        return 'use the stairs'
        
print(bfs(now))

 

BFS 문제

보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다. U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다. (만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다)

위는 문제의 일부이다. U층을 가는 버튼은 U만큼 +로 움직이는 버튼이고, D는 D만큼 -로 움직이는 버튼이라는 의미이다. 처음 문제를 해석할 때, 이 부분이 헷갈려서 몇 번 읽고 나서 완벽하게 이해를 했던 것 같다.

 

cnt 배열

이 문제를 풀 때는 cnt 라는 배열이 포인트이다. 문제의 답을 cnt배열에 넣어놓고, 조건에 알맞게 출력할 것이기 때문이다.

if s == dst:
            return cnt[dst]

s는 현재를 의미하는 변수이다. 만약 현재 층이 목적지에 도달했다면, cnt[dst]를 반환한다.

if cnt[dst] == 0:
        return 'use the stairs'

그리고 deque 을 한 바퀴 다 돌았는데도 cnt[dst]에 방문한 적이 한 번도 없다면 문구를 출력할 것이다.

 

BFS 문제를 풀 때 조심해야 할 부분

for _ in 움직일 범위

        for dm in (s + u, s-d):
            if 1 <= dm <=total and not visited[dm]:
                visited[dm]= True
                cnt[dm] = cnt[s]+1
                q.append(dm)

우리가 전형적인 bfs 문제를 다룰 때는 보통 dx, dy라는 배열을 만들어서 풀고는 한다. 하지만 만약 이런 식으로 입력받은 수만큼 움직이는 배열을 가지고 있다면, for 문으로 해당 배열 자체를 돌려주면 된다. 

사용법은 일반적인 bfs 문과 다르지 않지만, 처음 접했을 때 혼란스러울 수는 있기 때문에 정확하게 개념을 짚고 넘어가는 것이 좋다.

 

if문 'and'의 우선순위

그리고 정말 조심해야 할 부분은 if문이다. if문의 순서를 바꾸면 "list index out of range" 라는 오류를 만나게 될 수 있다.

if 문의 and는 무조건 앞의 조건을 먼저 실행한다.

그렇기 때문에 만약 visited[] 라는 배열을 전체 크기만큼 선언했다고 치자.

만약 조건문의 순서를 거꾸로 한다면 dm 이라는 수가 같은 줄에 있는 <1보다 크고 total보보다 작은 수> 라는 조건을 지키지 않은 채 up & down을 하며 이동한다.

그래서 오류를 접하게 될 수 있는 것이다.

무조건 조건문의 and를 쓸 때는 지켜야 하는 순서의 우선순위를 고려해서 사용하자.