[BAEKJOON]5014 스타트링크

문제 요약

• 알고리즘 분류: bfs
• 난이도:Silver1
• 문제내용:
  • F 전체층, S 시작층, G 도착층, U  현재 위치에서 U칸 만큼 위로 감, D 현재 위치에서 D칸 만큼 아래로 감
  • 시작층에서 도착층까지 최소  몇번 버튼을 눌려야 되는지 출력해라 
  • 만약 도착 못하면 'use the stairs'을 출력해라

• 사이트: https://www.acmicpc.net/problem/5014

5014번: 스타트링크

문제풀이

 이번 문제는 BFS 탐색 문제이다.  BFS 탐색 알고리즘에 관한 자세한 설명은 여기에서 확인 해보면 알 수 있다.

 기존 BFS는 각 노드간의 탐색인데 이번에는 2차원 배열로 응용한 BFS 탐색이다. 노드 대신 1차원 배열로 변경 된것만 생각하면 된다.

문제 접근 방법

 이번 문제는 BFS와 배열 안의 위치 이동이다. 다만 노드로 탐색 할때는 방문 여부만 했지만 배열안에 넓이 탐색은 배열 범위 안에 탐색할수 있는 조건만 추가하면된다.

  위 그림은 엘레베이터의 버튼 이동을 그림 으로 포현한 것이다. i 위치에서 이동 할수 있는 범위는 I + U, I - D 층 2가지만 이동이 가능 한다. 그럼 어떻게 BFS 알고리즘으로 풀 것이라면 처음에는 모든 배열의 방문 여부를 확인 하는 배열 필요한데 그럼 이동횟수 배열이랑 따로 만들기에는 귀찮다 그래서 모든 배열은 -1로 초기화를 한다. 그다음 S층을 0으로 시작해서 BFS 탐색을 한다. 탐색 할때 범위 안에 있고 방문 안했을때 탐색한 층은 꺼낸 값에 + 1만 해주기만 하면 끝이다. G층에 도착하면 출력하면되고 아니면 도착 못했다는 메세지를 출력하면된다.

정리

1. 이동횟수를 저장한 배열을 -1로 초기화한다.
2. S층을 0으로 지정한다.
3. BFS 탐색 한 범위이고 방문하지 않은 층은 꺼낸 값의 층에 +1을 해준다.

Code

python

from collections import deque

def bfs():
    queue = deque([S])
    elevator[S] = 0
    while queue:
        floor = queue.popleft()
        if floor == G: 
            print(elevator[G])
            return
        for next_floor in(floor + U , floor - D):
            if 0 < next_floor <= F and elevator[next_floor] == -1:
                elevator[next_floor] = elevator[floor] + 1
                queue.append(next_floor)
    print('use the stairs')

F, S, G, U, D = map(int, input().split())
elevator = [-1] * (F + 1)
bfs()

Java

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

public class Main {
	
	static int[] elevator;
	static int F, S, G, U, D;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		F = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		G = Integer.parseInt(st.nextToken());
		U = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());
		elevator  = new int[F + 1];
		Arrays.setAll(elevator, i -> -1);
		
		bfs();
	}
	
	public static void bfs() {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(S);
		elevator[S] = 0;
		
		int stair;
		while(!queue.isEmpty()) {
			stair = queue.poll();
			
			if(stair == G) {
				System.out.println(elevator[stair]);
				return;
			}
			if (0 < stair + U && stair + U <= F && elevator[stair + U] == -1) {
				elevator[stair + U] = elevator[stair] + 1;
				queue.add(stair + U);
			}
			
			if (0 < stair - D && stair - D <= F && elevator[stair - D] == -1) {
				elevator[stair - D] = elevator[stair] + 1;
				queue.add(stair - D);
			}
		}
		
		System.out.println("use the stairs");
	}
	
}