[Baekjoon] 5014_스타트링크

Gold V

문제(출처: https://www.acmicpc.net/problem/5014)

---

<스타트링크>

문제 

 

강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다.

스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다.

보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다. U버튼은 위로 U층을 가는 버튼, D 버튼은 아래로 D층을 가는 버튼이다. (만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다)

강호가 G층에 도착하려면, 버튼을 적어도 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오. 만약, 엘리베이터를 이용해서 G층에 갈 수 없다면, "use the stairs"를 출력한다.

 

 

입력

 

첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.

 

출력 

 

첫째 줄에 강호가 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 출력한다. 만약, 엘리베이터로 이동할 수 없을 때는 "use the stairs"를 출력한다.

 

 

문제 풀이

 

 - my solution (Python)

import sys
from collections import deque

if __name__=='__main__':
    f,s,g,u,d=map(int ,sys.stdin.readline().split()) # 가장 높은 층, 현재 있는 층, 이동하려는 층, 위, 아래

    visited=[0]*(f+1) # 방문 여부
    depth=[0]*(f+1) # 눌러야 하는 버튼의 수

    queue=deque([s])

    dx=[u,-d] # 이동할 수 있는 층 수
    visited[s]=1
    flag=0

    while queue:
        temp=queue.popleft()
        for i in dx:
            x=temp+i
            if x<=f and x>0: # 건물 범위 안
                if visited[x]==0: # 아직 방문하지 않은 층
                    visited[x]=1 # 방문
                    depth[x]=depth[temp]+1
                    queue.append(x)
                if x==g: # 도착
                    flag=1
                    break
        if flag==1: # 도착
            break
    if s!=g and depth[g]==0: # 엘리베이터를 이용해서 갈 수 없다면
        print("use the stairs")
    else: # 눌러야 하는 버튼의 수
        print(depth[g])

 

- my solution (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class _5014_스타트링크 {

	public static void main(String[] args) throws IOException{
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		
		String s=bf.readLine();
		int F = Integer.parseInt(s.split(" ")[0]); // 가장 높은 층
		int S = Integer.parseInt(s.split(" ")[1]); // 현재 있는 층
		int G = Integer.parseInt(s.split(" ")[2]); // 이동하려는 층
		int U = Integer.parseInt(s.split(" ")[3]); // 위
		int D = Integer.parseInt(s.split(" ")[4]); // 아래
		
		int visited[]=new int[F+1]; // 방문 여부
		int depth[]=new int[F+1]; // 눌러야 하는 버튼의 수
		
		Queue<Integer>queue=new LinkedList<>();
		queue.add(S);
		
		int dx[]= {U, -D}; // 이동할 수 있는 층 수
		visited[S]=1;
		int flag=0;
		
		while(queue.size()!=0) {
			int temp=queue.poll();
			for(int i=0; i<2; i++) {
				int x=temp+dx[i];
				if (x<=F && x>0) { // 건물 범위 안
					if(visited[x]==0) { // 아직 방문하지 않은 층
						visited[x]=1; // 방문
						depth[x]=depth[temp]+1;
						queue.add(x);
					}
				}
				if (x==G) { // 도착
					flag=1;
					break;
				}
			}
			if(flag==1) { // 도착
				break;
			}
		}
		if (S!=G && depth[G]==0) { // 엘리베이터를 이용해서 갈 수 없다면
			System.out.println("use the stairs");
		}else {
			System.out.println(depth[G]);
		}
	}
}

 

• 가장 높은 층 F, 현재 위치 S, 도착해야 하는 층 G, 위 U, 아래 D 입력
• visited = 방문 여부
• depth = 눌러야 하는 버튼의 수 저장
• dx = 이동할 수 있는 층 ( U, D )
• queue가 빌 때까지 반복 -> 제일 처음 값을 pop -> U, D 이동하여 건물 범위 안이며 아직 방문하지 않은 층이면 방문 및 depth 저장, queue에 저장/ 이동하려는 위치와 도착해야 하는 층이 같으면 break
• 엘리베이터를 이용해서 갈 수 없으면 "use the stairs" 출력, 엘리베이터를 이용해서 갈 수 있으면 depth [G] 출력

 

❓ 엘리베이터를 이용해서 갈 수 없는 곳을 어떻게 판별하는가?

이 부분에 대해서 살짝 고민했었다. 현재 위치와 도착해야 하는 층이 같은 경우도 있다고 생각하여 현재 위치와 도착해야 하는 층이 같지 않으며 depth [G]에 저장한 값이 0이라면 갈 수 없다고 판단하였다. 엘리베이터를 이용하여 갈 수 없다면 depth에는 0 값이 저장되어있기 때문이다. 

---

생각🤔

 

뿌듯합니다. 

 

 

---