백준 [5014] 스타트링크 파이썬 - jimoo

백준 문제 링크!!

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

5014번: 스타트링크

'[1697] 숨바꼭질(https://www.acmicpc.net/problem/1697)'과 거의 동일한 문제라고 볼 수 있다.

 

강호가 위치한 층에서 스타트링크 층으로 가장 빠르게 올라가는 방법을 탐색하기 위해 BFS 방식을 사용했다.

 

먼저 이동한 횟수를 저장하기 위해 f층으로 이루어진 고층 건물 사무실크기만큼 배열 matrix를 생성한다.

matrix = [0] * (f+1) 부분에 해당

 

탐색하는 층(c)는 0보다 커야하고 f보다 같거나 작아야한다. 

그리고 not matrix[c]가 True가 될 조건은 matrix[c]가 0 값을 가질 때이다. 이는 한 번 탐색한 층을 탐색하지 않겠다는 조건을 의미한다.

 

그리고 마지막 !!! 숨바꼭질과 다른점은 c != start부분에 해당한다. 이 부분이 없으면 파이썬에서 예제를 돌렸을 때 정답을 확인할 수 있지만 백준 알고리즘에서는 계속 틀렸습니다! 를 얻게 된다.

 

그 이유는 층을 탐색할 때 시작한 층으로 다시 돌아와서 시작 층을 다시 탐색할 필요가 없기 때문이다.

만일 c != start가 없다면 다시 1층으로 돌아왔을 때 matrix[start]는 0 값을 가지고 있고 0<c<=f의 조건을 만족하기 때문에 불필요한 탐색을 한 번 더 하게된다.

 

잘 이해가 되지 않는다면 아래 예시를 들어뒀으니 읽으면 된다.

 

**예제 입력 1을 바탕으로 든 예시

1층에서 시작했을 때

-> 1+2층 (3층)

->1+2-1층 (2층)

-> 1+2-1-1층 = (1층)

 

from sys import stdin
f,s,g,u,d = map(int, input().split())
matrix = [0] * (f + 1) 

def bfs(start):
    queue = [start]
    while queue:
        n = queue.pop(0)
        if n == g :
            return matrix[n]
        for c in (n-d, n+u):
            if 0<c<=f and not matrix[c] and c != start:
                matrix[c] = matrix[n]+1
                queue.append(c)
    return "use the stairs"

print(bfs(s))

해당 포스트에 틀린점이 있거나 궁금한점이 있다면 아래 댓글로 달아주시길 바랍니다.