백준 5014 스타트링크

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

5014번: 스타트링크

📌 해결 과정

https://hwdev.tistory.com/15

[백준] 파이썬 1697 : 숨바꼭질

 

이 문제와 정말 유사한 문제지만, 체크하고 넘어 가야할 것이 있어서 기록한다.

 

숨바꼭질 문제를 풀때와 유사하게 방문처리와 버튼을 누른 횟수를 같이 저장해 둘려고 했는데

여기서, 한가지 문제가 발생한다

 

강호의 시작 위치에 대한 처리에서 문제가 발생하는데,

제일 처음 좌표는 que에 추가만 해야하고 butto_cnt[start_height] 에 +1을 해주면 안된다.

시작 위치는 버튼을 한번도 누르지 않은 상태이기 때문이다.

따라서, 시작위치는 제일 처음 방문한 층임에도 불구하고

if 1 <= nx <= total_height and not button_cnt[nx]:

이렇게 조건문을 쓰면 다시 한번 방문하게 되기 때문에 문제가 발생한다

그래서, 방문하려고 하는 층이 시작 층이 아님을 비교하는 조건을 추가했다

if 1 <= nx <= total_height and not button_cnt[nx] and nx != start_height:

 

📌 코드

import sys
from collections import deque

input = sys.stdin.readline


def bfs(x):
    que = deque()
    que.append(x)

    while que:
        x = que.popleft()
        if x == target_height:
            return button_cnt[target_height]

        for nx in (x + up, x - down):
            if 1 <= nx <= total_height and not button_cnt[nx] and nx != start_height:
                button_cnt[nx] = button_cnt[x] + 1
                que.append(nx)

    return "use the stairs"


if __name__ == "__main__":
    total_height, start_height, target_height, up, down = map(int, input().split())
    button_cnt = [0] * (total_height + 1)
    print(bfs(start_height))

 

🧐 신경 써야할 것

 

요새 알고리즘 문제를 풀때, 변수명에 신경을 쓰면서 풀고 있는데 정말 좋은 방법인것 같다.

변수가 뭘 의미하는지 알고 푸니까 많은 변수를 써야하는 문제도 충돌없이 구분해서 쓸 수 있는 장점이 있고,

내 코드를 다른사람이 봤을때도 뭘 의미하는지 바로 파악할 수 있게끔 해줄 수 있어서 앞으로도 많이 신경 써야겠다.