[백준 / JAVA] 5014. 스타트링크

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

5014번: 스타트링크

 

---

💻 풀이 결과

 

💯 최종 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

// 리팩토링한 코드 !!
class Node {
	int floor, cnt;

	Node(int floor, int cnt) {
		this.floor = floor;
		this.cnt = cnt;
	}
}

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int F = sc.nextInt(); // 건물 총 층 수
		int S = sc.nextInt(); // 강호 현재 위치
		int G = sc.nextInt(); // 스타트링크 위치
		int U = sc.nextInt(); // 위로 U층 가는 버튼
		int D = sc.nextInt(); // 아래로 D층 가는 버튼

		Queue<Node> queue = new LinkedList<>();
		boolean[] visited = new boolean[F + 1];
		boolean flag = false;

		// cnt : 다음 층으로 가기 위해 눌러야 하는 버튼의 수라는 점에 유의 !!
		queue.add(new Node(S, 0));
		visited[S] = true;

		while (!queue.isEmpty()) {
			Node curr = queue.poll();

			// 탈출 조건
			if (curr.floor == G) {
				System.out.println(curr.cnt);
				flag = true;
				queue.clear();
				break;
			}

			int up = curr.floor + U;
			int down = curr.floor - D;

			if (up <= F && !visited[up]) {
				queue.add(new Node(up, curr.cnt + 1));
				visited[up] = true;
			}
			if (down > 0 && !visited[down]) {
				queue.add(new Node(down, curr.cnt + 1));
				visited[down] = true;
			}
		} // while문 끝

		if (!flag) {
			System.out.println("use the stairs");
		}
	}
}

💬 풀이 과정

• 건물의 총 층 수인 범위 내에서 U버튼과 D버튼을 각각 눌렀을 때를 BFS 돌린다.
• 눌러야 하는 버튼의 수의 최솟값을 구하기 위해 visited 방문 처리를 해준다.

💡 깨달은 점

1. 노드의 카운팅 요소

• BFS를 돌릴 때 노드에 저장하는 cnt 요소의 시작점이나 카운팅 지점에 유의해야 한다.