[백준] 5014 - 스타트링크

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

 

알고리즘

BFS (최단거리 탐색)

 

풀이 

F: 전체 건물의 층 수 (정점의 최댓값)

S: 시작점

G: 목표지점

S -> G까지 가려면 몇번 시도해야하는지 구하는 문제이다. 최단거리 탐색이므로 BFS 사용

 

체크배열에 누적한 값을 저장해둔다.

 

입력이 10 1 10 2 1 일 때 과정을 설명해보면

 

1. 큐 = [1],

now = 1, 큐 = [] 

체크배열 = [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

for nxt in (1+2, 1-1):

nxt가 3인 경우 -> 큐 = [3], 체크배열 = [0, 1, 0, 2, 0, 0, 0, 0, 0, 0, 0]

nxt가 0인 경우 -> 유효 좌표 X 

 

2. 큐 = [3],

now = 3, 큐 = [] 

for nxt in (5, 2):

nxt가 5인 경우 => 큐 = [5], 체크배열 = [0, 1, 0, 2, 0, 3, 0, 0, 0, 0, 0]

nxt가 2인 경우 => 큐 = [5, 2], 체크배열 = [0, 1, 3, 2, 0, 3, 0, 0, 0, 0, 0]

 

3. 큐 = [5, 2]

now = 5, 큐 = [2]

for nxt in (7, 4):

nxt가 7인 경우 => 큐 = [2, 7], 체크배열 = [0, 1, 3, 2, 0, 3, 0, 4, 0, 0, 0]

nxt가 4인 경우 => 큐 = [2, 7, 4], 체크배열 = [0, 1, 3, 2, 4, 3, 0, 4, 0, 0, 0]

 

4. 큐 = [2, 7, 4]

now = 2, 큐 = [7, 4]

for nxt in (4, 1):

nxt가 4인 경우: 이미 체크 

nxt가 1인 경우: 이미 체크 

 

5. 큐 = [7, 4]

now = 7, 큐 = [4]

fot nxt in (9, 6):

nxt가 9인 경우 => 큐 = [4, 9], 체크배열 = [0, 1, 3, 2, 4, 3, 0, 4, 0, 5, 0]

nxt가 6인 경우 => 큐 = [4, 9, 6], 체크배열 = [0, 1, 3, 2, 4, 3, 5, 4, 0, 5, 0]

 

6. 큐 = [4, 9, 6]

now = 4 

for nxt in (6, 3):

nxt가 6, 3인 경우: 이미 체크

 

7. 큐 = [9, 6]

now = 9

for nxt in (11, 8):

nxt가 11인 경우: 유효 좌표 아님

nxt가 8인 경우 => 큐 = [6, 8], 체크배열 = [0, 1, 3, 2, 4, 3, 5, 4, 6, 5, 0]

 

8. 큐 = [6, 8]

now = 6

for nxt in (8, 5):

nxt가 8, 5인 경우: 이미 체크 

 

9. 큐 = [8]

now = 8

for nxt in (10, 7):

nxt가 10인 경우 => 큐 = [10], 체크배열 =  [0, 1, 3, 2, 4, 3, 5, 4, 6, 5, 7]

nxt가 7인 경우: 이미 체크 

 

10. 큐 = [10]

now = 10

now가 G와 같기 때문에 return chk[10] -1 (=6)

 

따라서 정답은 6! 

 

전체 코드 

# 스타트링크
# F: 전체 건물의 층 수, S: 현재, G: 목표 지점 

from collections import deque

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

chk = [0] * (F+1)

def is_valid_coord(x):
    return 0 < x <= F

def bfs(now):
    dq = deque()
    dq.append(now)
    chk[now] = 1 
    
    while dq:
        now = dq.popleft()
        
        if now == G:
            return chk[now] - 1 
        
        else:
            for nxt in (now+U, now-D):
                if is_valid_coord(nxt) and not chk[nxt]:
                    chk[nxt] = chk[now] + 1 
                    dq.append(nxt)
    
    return 'use the stairs'

print(bfs(S))

 

체크배열을 방문하면 True or 1, 방문하지 않으면 False or 0으로만 다뤄봤는데, 앞에 방문한 횟수를 누적하는 방식이 독특해서 기억에 남을듯! 그리고 운좋게 '1697 - 숨바꼭질' 문제를 풀어봤는데 유사한 유형이었다.