[baekjooon] 5014. 스타트링크

---

로직 설명

1. 한 단계씩 나아가면서 cnt +=1을 하고, q에 G가 들어있으면 stop

  ex. 1 - 3 - 2 - 1

                   - 4

              - 5 - 4

                   - 7

   cnt :   1   2   3

코드

import collections

F, S, G, U, D = map(int, input().split())

def bfs():
    if S > G and D == 0:
        return "use the stairs"

    elif S < G and U == 0:
        return "use the stairs"

    q = collections.deque([(S, 0)])
    visit = [0 for _ in range(F + 1)]
    visit[S] = 1

    while q:
        x, cnt = q.popleft()
        if x == G:
            return cnt

        if x + U <= F and not visit[x + U]:
            q.append((x + U, cnt + 1))
            visit[x + U] = 1

        if x - D >= 1 and not visit[x - D]:
            q.append((x - D, cnt + 1))
            visit[x - D] = 1

    return "use the stairs"

print(bfs())

 

주의할 점

[ 처음작성한 코드.. ]

F, S, G, U, D = map(int, input().split())

def bfs():
    if S > G and D == 0:
        return "use the stairs"

    elif S < G and U == 0:
        return "use the stairs"

    cnt = 0
    q = [S]

    while q:
        cnt += 1
        for x in range(len(q)):
            x = q.pop(0)
            if x == G:
                return cnt - 1

            if x + U <= F:
                q.append(x + U)

                if x - D >= 1:
                    q.append(x - D)

            else:
                continue

    return "use the stairs"

print(bfs())

1. while문에서 같은 라인에서 if(=), if(up), elif(down) 해서하면 up한거 가지고 down을 하러간다.

   up, down 다 확인해서 두 방향으로 다 나아가야함

   

2. 코드를 이렇게 짜면, 5, 2, 1, 1, 0일 때, while문만 돌리면 무한루프로 돈다

    -> why? q가 cnt에 따라 한번에 다 빠지는게 아니라 cnt += 1일 때, [1] -> [3] -> [5, 2] -> [2, 7, 4]로 나옴

    -> 내가 원하는 건  [1] -> [3] -> [5, 2] -> [7, 4, 4, 1]

 

음,, 어카지,,,

 

* 해결방안 : cnt를 q랑 같이 묶어서 진행하게 한다! -> 7569, 7576 토마토처럼!