[java] 백준 5014 : 스타트링크

문제

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

5014번: 스타트링크

 

 

package main;
import java.io.*;
import java.util.*;

public class Main {

	static int F;
	static int S;
	static int G;
	static int U;
	static int D;
	static int[] visited;
	static int h;
	public static void main(String[] args) throws Exception{

	Scanner sc = new Scanner(System.in);
	

	F=sc.nextInt();
	S=sc.nextInt();
	G=sc.nextInt();
	U=sc.nextInt();
	D=sc.nextInt();

	visited = new int[F+1];
//	DFS(S,0);
	BFS(S);
	
//	if(h>0) System.out.println(h);
//	else System.out.println("use the stairs");

	}
	
	
//	static void DFS( int num, int dep) {
//		
//		visited[num]=true;
//		
//		if(num == G) {
//			h=dep;
//			return;
//		}
//		
//		
//		if(num+U<=G && num+U>=S && visited[num+U]==false ) {
//			System.out.println(dep+": "+ (num));
//			DFS(num+U,dep+1);
//		}
//		if(num-D<=G && num-D>=S &&visited[num-D]==false) {
//			System.out.println(dep+": "+ (num));
//			DFS(num-D,dep+1);
//		}
//
//		
//	}
	
	static void BFS(int num) {
		Queue<Integer> q = new LinkedList<>();
		
		boolean flag=false;
		q.add(num);
		visited[num]=1;
		
		while(!q.isEmpty()) {
			int now = q.poll();
//			System.out.println(now);
			if(now==G) {
				System.out.println(visited[now]-1);
			}
			
			if((now+U)<=F && visited[now+U]==0 ) {
//				System.out.println("now+u: "+(now+U));
				visited[now+U]=visited[now]+1;
				q.add(now+U);
			}
			if((now-D)>0 &&visited[(now-D)]==0) {
//				System.out.println("now-D: "+(now-D));
				visited[(now-D)]=visited[now]+1;
				q.add((now-D));
			}
			
			
			
		}
		
		if(visited[G]==0) 
		{System.out.println("use the stairs");}
	}
	
	
}

고친 과정

1. dfs -> bfs

2. 조건문 f보다 작고 0보다 커야함 

 

 

정리된 코드

package main;
import java.io.*;
import java.util.*;

public class Main {

	static int F;
	static int S;
	static int G;
	static int U;
	static int D;
	static int[] visited;
	static int h;
	public static void main(String[] args) throws Exception{

	Scanner sc = new Scanner(System.in);
	

	F=sc.nextInt();
	S=sc.nextInt();
	G=sc.nextInt();
	U=sc.nextInt();
	D=sc.nextInt();

	visited = new int[F+1];
	BFS(S);

	}
	
	
	
	static void BFS(int num) {
		Queue<Integer> q = new LinkedList<>();
		
		boolean flag=false;
		q.add(num);
		visited[num]=1;
		
		while(!q.isEmpty()) {
			int now = q.poll();

			if(now==G) {
				flag=true;
				break;
			}
			
			if((now+U)<=F && visited[now+U]==0 ) {
				visited[now+U]=visited[now]+1;
				q.add(now+U);
			}
			
			if((now-D)>0 &&visited[(now-D)]==0) {
				visited[(now-D)]=visited[now]+1;
				q.add((now-D));
			}
		
		}
		
		if(flag==false) 
		{System.out.println("use the stairs");}
		else {
			System.out.println(visited[G]-1);
		}
	}
	
	
}