[백준 5014번] 스타트링크 (C++)

문제링크 : https://www.acmicpc.net/problem/5014

 

#include <bits/stdc++.h> 
using namespace std;

int f, s, g, u, d;
queue<int> q;
int elevator[1000001];


void bfs()
{
	int dx[2] = { u, -d }; //위, 아래
	q.push(s);
	elevator[s] = 1;  //첫 시작점을 1로 초기화

	while (!q.empty())
	{
		int cur = q.front(); q.pop();
		for (int i = 0; i < 2; i++)
		{
			int nx = cur + dx[i];  //다음 좌표
			if (nx < 1 || nx > f) { continue; } //범위 조건
			if (elevator[nx]!=0) { continue; }  //다음 값의 위치에 또 가는 것을 방지
			if (nx == g) //다음 위치와 도착지가 같을 경우
			{  
				cout << elevator[cur]; //처음에 1(다음 위치 미리 저장)로 시작했기에 현재값 출력
				return;
			}
			else { elevator[nx] = elevator[cur] + 1; q.push(nx);  } //아닐 경우 층수 1 증가 		
		}
	}
	cout << "use the stairs";  //못 찾았을 경우
}

int main()
{
	cin >> f >> s >> g >> u >> d; 
	if (s == g) { cout << 0; return 0; } //출발지와 도착지가 같으면 이동할 필요가 없음
	bfs();
}

움직이는 방향이 위아래로 두군데 뿐이다.

스킵 조건을 잘 설정하지 않으면, 갔던데를 또 계속 가는 바람에 메모리초과 날 수 있다.