5014번-스타트링크

처음에 제출한 코드 

/*
F층으로 이루어진 고층 건물, S는 현재 강호 위치, G는 도착지, U는 위로 U층 가는 버튼, D는 아래로 D층 가는 버튼. 
U와 D버튼만으로 도착지까지 이동을 한다.최소 몇 번을 눌러야 하는가?
*/

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

int vis[1000002];

int main() {
	int f, s, g, u, d;
	cin >> f >> s >> g >> u >> d;
	if (s == g) {
		cout << 0;
		return 0;
	}
	queue<int> Q;
	Q.push(s);
	vis[s] = 1;
	while (!Q.empty()) {
		int cur = Q.front(); Q.pop();
		int ux = cur + u;
		int dx = cur - d;
		if (ux == g) {
			cout << vis[cur];
			return 0;
		}
		if (dx == g) {
			cout << vis[cur];
			return 0;
		}
		if (ux > f || ux < 1||vis[ux]>0)continue;
		Q.push(ux);
		vis[ux] = vis[cur]+1;
		
		if (dx > f || dx < 1 || vis[dx] > 0)continue;
		Q.push(dx);
		vis[dx] = vis[cur]+1;
	}
	cout << "use the stairs";

}

위의 코드의 문제는 if 문으로 ux의 조건을 검사하고 continue로 넘어가버리면 dx는 검사조차 할 수 없다는 것이다. 병렬적인 조건이 있을 때는 조심해서 검사하자. 

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

int vis[1000002];

int main() {
	int f, s, g, u, d;
	cin >> f >> s >> g >> u >> d;
	queue<int> q;
	fill(vis+1, vis + f+1, -1);
	q.push(s);
	vis[s] = 0;
	while (!q.empty()) {
		int cur = q.front(); q.pop();
		for (auto nxt : { cur + u,cur - d }) {
			if (nxt<1 || nxt>f || vis[nxt] != -1)continue;
			q.push(nxt);
			vis[nxt] = vis[cur] + 1;
		}
	}
	if (vis[g] == -1)cout << "use the stairs";
	else cout << vis[g];
}

python 풀이

from collections import deque
f,s,g,u,d=map(int,input().split())
vis=[-1 for i in range(f+1)]
q=deque()
q.append(s)
vis[s]=0
while q:
    cur=q.popleft()
    for i in (cur-d,cur+u):
        if i<1 or i>f or vis[i]!=-1:
            continue
        q.append(i)
        vis[i]=vis[cur]+1
if vis[g]==-1:
    print("use the stairs")
else:
    print(vis[g])