문제 링크 : https://www.acmicpc.net/problem/5014

🔍 문제 요약

1. F층으로 이루어진 건물에서 S층에서 시작하여 G층으로 가야한다.
2. 위층으로 갈때는 U층 위로, 아래층으로 갈때는 D층 아래로 갈 수 밖에 없다.
3. S층에서 G층으로 가기 위해 버튼을 몇번 눌러야 하는가?

입출력 조건

1. 입력 조건 : 건물의 층수, 현재 위치, 목적 위치, 위로 갈수 있는 칸수, 아래로 갈 수 있는 칸수
2. 출력 조건
   2-1. 이동할 수 있는 경우 : 최소 이동 수(버튼 누른 횟수)
   2-2. 이동할 수 없는 경우 : use the stairs

📍 접근 방법

최소 이동 수를 구할 때 dfs로 풀이했을 때는 이동할 수 있는 경우의 cnt를 전부 구하고 또 그 최솟값을 구해야 하기 때문에 비효율적이라고 생각했다.
또한 주어지는 변수의 범위가 매우 크므로 (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) bfs를 이용하여 풀이하였다.

코드 설계

1. 목적지에 도착했는지 확인하는 flag, 이동 수 담을 visit 배열([0]*층수)
2. 현재 위치 담는 deque 생성
3. 방향 배열(up, -down) 사용하여 갈 수 있는 곳 bfs 탐색
4. 다음 위치 확인할때 범위 확인(1<=next<=floor), 방문 확인(v[n]=0)
5. 갈 수 있는 곳이면 v[next] = v[now]+1 , q.append(next)
   6-1. 도착점에 도착하면 flag 켜고 그 위치에 저장된 값 -1 리턴 (처음에 1부터 시작했으므로!)
   6-2. bfs 탐색 끝났는데도 flag가 0이면 use the stairs 출력

처음 오답 풀이

• 도착 확인을 맨 뒤에서 했더니 처음 위치가 도착 위치와 같을 때에도 다음 방향을 탐색해버리면서 오답 출력

from collections import deque

# 건물 층수, 현재 위치, 도착 위치, 위로, 아래로
floor, st, ed, up, down = map(int, input().split())  

visited = [0]*(floor+1)
flag = 0
def bfs():
    global flag
    q = deque()
    q.append(st)
    visited[st] = 1
    while q:
        now = q.popleft()
        for d in (up, -down):
            Next = now + d
            if 1 <= Next <= floor:
                if visited[Next] == 0:
                    visited[Next] = visited[now] + 1
                    q.append(Next)
				# 오답 원인
                if Next == ed:
                    flag = 1
                    return visited[Next] - 1

answer = bfs()

if flag == 1:
    print(answer)
else:
    print('use the stairs')

코드 수정 - 정답 (1)

• 리턴 확인 지점을 while 문 맨 앞으로 바꾸었더니 정답 (512ms)

from collections import deque

# 건물 층수, 현재 위치, 도착 위치, 위로, 아래로
floor, st, ed, up, down = map(int, input().split())  

visited = [0]*(floor+1)
flag = 0
def bfs():
    global flag
    q = deque()
    q.append(st)  # 시작 위치 담고
    visited[st] = 1  # 방문 체크
    while q:
        now = q.popleft()
        if now == ed:  # 도착하면
            flag = 1  # flag 켜기
            return visited[now] - 1  # 시작할 때 1부터 시작했으므로
        for d in (up, -down):  # 위로, 아래로 2방향 탐색
            Next = now + d
            if 1 <= Next <= floor:  # 범위 확인
                if visited[Next] == 0:
                    visited[Next] = visited[now] + 1
                    q.append(Next)

answer = bfs()

if flag == 1:
    print(answer)
else:
    print('use the stairs')

코드 수정 - 정답 (2)

• while문 다 돌았는데도 함수가 return 되지 않았으면 엘레베이터로 이동 할 수 없는 것!
• flag를 없애고 이동할 수 없는 경우의 출력 조건을 함수 맨 마지막에 리턴값으로 작성하였더니 시간을 더 줄일 수 있었다. (496ms)

from collections import deque

# 건물 층수, 현재 위치, 도착 위치, 위로, 아래로
floor, st, ed, up, down = map(int, input().split())  
visited = [0]*(floor+1)

def bfs():
    q = deque()
    q.append(st)  # 시작 위치 담고
    visited[st] = 1  # 방문 체크
    while q:
        now = q.popleft()
        if now == ed:  # 도착하면
            return visited[now] - 1  # 시작할 때 1부터 시작했으므로
        for d in (up, -down):  # 위로, 아래로 두 방향 탐색
            Next = now + d
            if 1 <= Next <= floor:
                if visited[Next] == 0:
                    visited[Next] = visited[now] + 1
                    q.append(Next)

    return 'use the stairs'

print(bfs())

⭐️ 제출 결과

• 함수를 사용할 땐 return을 잘 활용하자!