1. 문제
https://www.acmicpc.net/problem/5014
2. 풀이 과정
보통 DFS, BFS를 같이 쓸 수 있는 문제가 많아서 대부분 DFS로 풀다가 이번에 오랜만에 BFS 방식으로 풀어서 어색했다. 가능한 경로 중에서 최소 길이를 찾는 문제라서 BFS 방식으로 풀어야 한다.
풀이 방식을 간단하게 설명하면, Queue에 방문할 수 있는 층수를 넣고 Queue의 크기만큼 반복문을 돌며 다음 단계에 방문할 수 있는 층을 찾는다. 이미 방문한 층은 다시 방문할 필요가 없으므로 방문체크로 가지치기를 해주었다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int F, S, G, U, D;
public static void main(String[] args) throws Exception {
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());
int res = bfs();
System.out.println((res == -1) ? "use the stairs" : res);
}
public static int bfs(){
int result = -1;
Queue<Integer> q = new LinkedList();
boolean[] visited = new boolean[F+1];
q.add(S);
while(!q.isEmpty()){
result++;
for(int i=0, size = q.size(); i<size; i++){
int next = q.poll();
if(next == G){
return result;
}
int up = next + U;
if(up <= F && !visited[up]){
visited[up] = true;
q.add(up);
}
int down = next - D;
if(down > 0 && !visited[down]){
visited[down] = true;
q.add(down);
}
}
}
return -1;
}
}
결과
'코딩문제풀이 > Baekjoon' 카테고리의 다른 글
[Java] 백준 1926번 : 그림 (0) | 2023.01.06 |
---|---|
[Java] 백준 19583번 : 싸이버개강총회 (0) | 2023.01.05 |
[Java] 백준 14890번 : 경사로 (0) | 2023.01.03 |
[Java] 백준 2251번 : 물통 (0) | 2023.01.02 |
[Java] 백준 20055번 : 컨베이어 벨트 위의 로봇 (0) | 2023.01.02 |