[Algorithm][C++] BOJ 5014 스타트링크

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

5014번: 스타트링크

 

풀이 핵심

1. BFS 활용

2. visited 배열을 이용해 중복 방문 방지

3. 목적 층 G 에 도달하지 못하면 -1 return

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <queue>
using namespace std;

int F, S, G;
int df[2]; // df[0] (UP), df[1] (DOWN)
int ans;

struct elevator {
	int floor, cnt;
};
queue<elevator> q;

int bfs() {
	bool *visited = new bool[F + 1];
	for (int i = 1; i <= F; i++) visited[i] = false;
	q.push({ S, 0 });
	visited[S] = true;
	while (!q.empty()) {
		elevator cur = q.front();
		q.pop();
		if (cur.floor == G) {
			delete[] visited;
			return cur.cnt;
		}
		for (int dir = 0; dir < 2; dir++) {
			int nf = cur.floor + df[dir];
			if (nf < 1 || nf > F) continue;
			if (visited[nf]) continue;
			q.push({ nf, cur.cnt + 1 });
			visited[nf] = true;
		}
	}
	delete[] visited;
	return -1;
}

int main() {
	scanf("%d %d %d %d %d", &F, &S, &G, &df[0], &df[1]);
	df[1] = -df[1]; // Down은 minus 부호로 바꾸어 준다.
	ans = bfs();
	if (ans == -1) printf("use the stairs");
	else printf("%d", ans);
	return 0;
}

 

아쉬운 점

문제 자체는 어렵지 않아 쉽게 풀 수 있었다.

항상 C언어를 이용해 구현하다 보니 STL 사용이 익숙지 않았다.

처음으로 STL queue를 활용해 보았는데 너무 편했다.

공부가 필요할 것 같다. (queue, vector...)

동적으로 할당할 때 한번에 0으로 전체 초기화 하는 방법이 뭐가 있을까? (calloc 말고)