백준 알고리즘 풀이 5014번 - 스타트링크

- bfs 알고리즘

 

-시간 복잡도-

O(|V|+|E|)

 

- 알고리즘 -

 

1. 처음 내가 있는 위치를 queue에 넣는다.  

2. U, D을 사용해서 bfs를 돌린다.

3. 원하는 위치에 들어왔다면 종료 후 그 배열 값에 저장된 값을 출력한다.

 

- 예외 조건 -

 

1. bfs를 다 돌렸는데도 G를 방문하지 못했다면 계단으로 가도록 한다.

2. node에 방문하지 않는 조건을 visited [now]가 0일 때로 했으므로 처음에 들어가는 값의 visited는 1로 넣어주고 답에서 1을 빼주어야 한다.

 

계속 메모리 초과가 나와서 이유를 알 수 없었는데, queue에 넣는 조건을 visited [now]가 1일 때로 지정해 놓아서 메모리 오류가 나고 있었다.

새로 알게 된 사실인데 변수 이름을 g, d, u, f, s로 지으면 에러가 나온다. 시스템 변수와 겹치는 걸로 보인다.

 

-소스 코드-

 

#include <iostream>
#include <queue>
#define MAX 1000010

using namespace std;

int F,S,G,U,D;
int visited[MAX]={0,};
queue<int> q;

int bfs()
{
	q.push(S);
	visited[S]=1;
	while(!q.empty()){
		int now=q.front();
		if(now==G) return visited[now]-1;
		q.pop();
		int nextFloor[2]={now+U,now-D};
		for(int i=0;i<2;i++){
			if(1<=nextFloor[i] && nextFloor[i]<=F ){
				if(visited[nextFloor[i]]==0){
					visited[nextFloor[i]]=visited[now]+1;
					q.push(nextFloor[i]);
				}
			}
		}
	}
	return -1;
}

int main()
{
	cin>>F>>S>>G>>U>>D;
	int ans=bfs();
	if(ans==-1){
		cout<<"use the stairs";
	}
	else {
		cout<<ans;
	}
}