[DFS/BFS/완전탐색] ▲ 5014번 - 스타트링크(BFS)

[백준] 5014번 -  스타트링크

풀이 시간: 15분 이내

 

이 문제는 S층에서 G층으로 가기 위해 눌러야 하는 최소 버튼 수를 구하는 것으로 최단경로 문제에 속하므로 BFS로 풀어야 한다. 이전에 풀었던 문제와 거의 유사하므로 참고하면 좋을 듯 하다.

https://hseungyeon.tistory.com/224

[DFS/BFS/완전탐색] ▲ 16953번 - A → B(BFS)

방문처리를 하는 방법에 따라 2가지 방식으로 풀 수 있다.

 

(풀이1) visited를 집합으로 선언하고 조건을 만족할 때마다 add()로 삽입해주는 방법

1) 문제 해결 아이디어

visited를 0으로 초기화하지 않고 방문할 때마다 해당 층을 추가해주고 나중에 해당 층수가 visited에 있는지 확인하는 방식이다.

 

첫번째 오류. 시간초과

원래는 visited를 리스트로 선언하고 조건을 만족할 때마다 append()를 하는 방식으로 코드를 짰다.

그런데 그렇게 코드를 짜니 시간초과 문제가 있어 아래글을 참고하여 리스트 대신 집합으로 선언하니 문제를 해결할 수 있었다. 그 이유는 바로 방문여부를 검사하는 nx not in visited 의 not in 연산이 리스트에서는 시간복잡도가 O(n)이지만 집합에서는 O(1)이기 때문이다. visited와 같이 중복된 원소를 다루지 않는다면 리스트 대신 집합을 사용하면 시간복잡도를 줄일 수 있다!!!

 

[참고] https://jjangsungwon.tistory.com/35

[ 백준 5014 ] 스타트링크 - Python

[참고] https://lsh424.tistory.com/59

Python 자료형(list,set,dictionary) 메서드 시간복잡도 정리

 

2) 소스코드

from collections import deque

# BFS
def bfs(x):
  queue = deque()
  # 시작 지점 삽입, 방문 처리
  queue.append((x, 0))
  visited = {x}
  
  while queue:
    x, cnt = queue.popleft()
    # 목표 층수에 도달하면 종료
    if(x == g):
      return cnt
    # 위, 아래 탐색
    for i in range(2):
      nx = x + dx[i]
      # 층수가 범위 내이고 방문하지 않은 층이면
      if(1 <= nx <= f and nx not in visited):
        # 삽입, 방문처리
        queue.append((nx, cnt + 1))
        visited.add(nx)
  return "use the stairs"

#f: 총 층수, g: 목표 층수, s: 현재 층수, u: 위로 이동가능 층수, d: 아래로 이동가능 층수
f, s, g, u, d = map(int, input().split())
dx = [u, -d]  # 위, 아래 탐색 방향

print(bfs(s))

 

(풀이2) visited를 0으로 초기화하고 방문하면 1로 처리하는 방법

1) 문제 해결 아이디어

visited를 0으로 초기화하고 방문할 때마다 해당 층수에 대한 값을 1로 변경하여 방문하지 않은 층수(0)일 떄만 방문처리를 하도록 하는 방식이다.

 

2) 소스코드

from collections import deque

# BFS
def bfs(x):
  queue = deque()
  # 시작 지점 삽입, 방문 처리
  queue.append((x, 0))
  visited[x] = 1  
  
  while queue:
    x, cnt = queue.popleft()
    # 목표 층수에 도달하면 종료
    if(x == g):
      return cnt
    # 위, 아래 탐색
    for i in range(2):
      nx = x + dx[i]
      # 층수가 범위 내이고 방문하지 않은 층이면
      if(1 <= nx <= f):
        if(visited[nx] == 0):
          # 삽입, 방문처리
          queue.append((nx, cnt + 1))
          visited[nx] = 1
  return "use the stairs"

#f: 총 층수, g: 목표 층수, s: 현재 층수, u: 위로 이동가능 층수, d: 아래로 이동가능 층수
f, s, g, u, d = map(int, input().split())
visited = [0] * (f + 1)  # 방문 여부
dx = [u, -d]  # 위, 아래 탐색 방향

print(bfs(s))