[백준] 5014번 : 스타트링크 - 자바[Java]

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

5014번: 스타트링크

풀이

처음에는 DFS를 사용하여 S층에서 G층으로 갈 수 있는 모든 경우를 구하고, 그 경우에서 최솟값을 구하려고 하였다. 하지만 시간초과가 떴다. 그래서 구글링을 한 결과 BFS와 방문배열를 사용하여 문제를 풀었다. 층의 방문 여부를 저장하는 방문 배열을 사용하지 않는다면 메모리 초과가 뜬다.

 

로직

1. BFS를 사용하여 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 구한다. 이 때 한 번 방문한 층을 여러 번 방문하면 안되기 때문에 층의 방문 여부 배열을 boolean[] visited = new boolean[f+1]; 을 선언하고 초기화 한다.

2. Queue를 선언한다. 큐에는 int[]{현재 층, 누른 버튼 수}를 저장한다.

3. 시작 지점을 큐에 넣고, 시작 지점의 visited를 true로 변경한다.

4. 큐가 빈 큐가 될 때까지 다음 과정을 반복한다.

• 큐에서 하나를 뽑아서 현재 층이 G층과 같다면 바로 누른 버튼 수를 리턴한다.
• 현재 위치가 g보다 큰데 아래로 내려갈 수 없는 경우와, 현재 위치가 g보다 작은데 위로 올라갈 수 없는 경우에는 아무것도 하지 않는다.
• 현재 층에서 위층으로 올라갈 수 있으며 아직 한 번도 방문하지 않은 층이라면, visited를 true로 바꾸고 큐에 넣는다.
• 현재 층에서 아래층으로 내려갈 수 있으며 아직 한 번도 방문하지 않은 층이라면, visited를 true로 바꾸고 큐에 넣는다.
• 리턴되지 않고 반복문이 끝났으면 도달할 수 없는 층이므로 -1을 리턴한다.

5. bfs가 종료하고 메인 함수에서 반환 값(cnt)이 -1이라면 "use the stairs"를 출력하고 아니라면 cnt 값을 출력한다.

코드

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
	
	public static int bfs(int f, int s, int g, int u, int d) {
		
		boolean[] visited = new boolean[f+1];
		Queue<int[]> q = new LinkedList<>();
		
		q.add(new int[]{s, 0});
		visited[s] = true;
		
		
		while (!q.isEmpty()) {
			int[] tmp = q.poll();
			if (tmp[0] == g) {
				return tmp[1];
			}

			if (tmp[0] > g && d == 0) // 현재 위치가 g보다 큰데 아래로 내려갈 수 없으면
				continue;
			else if (tmp[0] < g && u == 0) // 현재 위치가 g보다 작은데 위로 올라갈 수 없으면
				continue;
			
			if (tmp[0]+u <= f && !visited[tmp[0]+u]) {
				visited[tmp[0]+u] = true;
				q.add(new int[]{tmp[0] + u, tmp[1] + 1});
			}
				
			if (tmp[0]-d >= 1 && !visited[tmp[0]-d]) {
				visited[tmp[0]-d] = true;
				q.add(new int[]{tmp[0] - d, tmp[1] + 1});
			}
		}
		
		return -1;
	}

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int f = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(st.nextToken());
        int g = Integer.parseInt(st.nextToken());
        int u = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        
        int cnt = bfs(f, s, g, u, d);
        
        
        System.out.println(cnt != -1 ? cnt : "use the stairs");

    }
}

 

참고: https://zoonvivor.tistory.com/144

---

💡 문제가 어떤 경우의 수를 구한다거나 하면 DFS를 사용하고,
최단거리, 또는 최소횟수를 구하라는 문제는 BFS를 사용한다고 보면 좋다.
또한 범위가 굉장히 넓고 큰 수인 경우에는 DFS가 편하더라도 DFS를 사용하지 말고, 효율성이 더 좋은 BFS를 이용해 탐색을 하자.