백준 5014번 스타트링크

🔒[문제 url]

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

🔑알고리즘

탐색 문제에서 최소값을 요한다? 웬만하면 BFS !!
이 문제는 대부분의 문제와 달리 n차원 배열 형식으로 그래프가 주어지지 않는다. 또한 양방향 그래프가 아닌 단방향인 것도 빠르게 캐치해야한다.

• 그렇다면 어떻게 그래프를 만들 수 있을까?
  1. 문제에서 주어진 정보를 바탕으로, vector를 이용한 그래프를 직접 생성해보자.
  2. 한 층에서 갈 수 있는 층은, U층 위와 D층 아래로 두 층만 존재.
  3. 그렇다면 단순 반복문을 통해 각 층에 대한 그래프를 생성해주자.
• 그래프를 완성했다면?
  • BFS를 통해 각 층에 대해 depth를 표시한 후, G층에 대한 depth(visited 배열을 이용해 표시)를 출력해주면 끝! 이때 생각해야하는 케이스는 세 가지이다.
    1. S층과 G층이 같은 경우 == 0 출력
    2. (S층 != G층이나 depth가 0인 경우) == use the stairs
    3. depth가 0이 아닌 경우 == depth 출력

🐾부분 코드

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> f >> s >> g >> u >> d;

	/*
	그래프 만들기.
	각 층을 순회하며 갈 수 있는 모든 층을 연결해준다.
	각 층은 두 개의 층과만 연결된다. U층 위와 D층 아래.
	양방향 그래프가 아님에 주의!!
	*/
	for (int i = 1; i <= f; i++)
	{
		if (i + u <= f) v[i].push_back(i + u); // U층 위
		if (i - d >= 1) v[i].push_back(i - d); // D층 아래
		else continue;
	}
}

<입력 및 그래프 생성 함수>
위에서 설명했듯, 각 층을 순회하며 U층 위와 D층 아래를 연결한다.
물론 범위또한 따져준다!

void BFS()
{
	queue<int> q;
	q.push(s);
	visited[s] = 1; // 0으로 하면 for if문에서 걸림

	while (!q.empty())
	{
		int now = q.front();
		q.pop();
		for (int i = 0; i < v[now].size(); i++)
		{
			if (!visited[v[now][i]])
			{
				visited[v[now][i]] = visited[now] + 1;// 엘레베이터 이동시 depth 추가
				q.push(v[now][i]);
			}
		}

	}
}

<BFS 탐색 함수>
S층을 시작으로 모든 그래프에 depth를 표시해준다.
A층에서 B층으로 이동할 때, B층의 depth는 A층의 depth + 1이 된다.
탐색중 G층을 만난 경우 함수를 바로 종료해도 좋다.

위 코드에서 visited[s]를 1로 시작해야함에 주의하자.

if (s == g) cout << 0;
else if (visited[g]) cout << visited[g] - 1;
else cout << "use the stairs";

<답 출력>
위에 적어둔 세 가지 케이스에 대하여 따로 출력 처리.
visited[s]를 1로 시작했기때문에, 출력은 visited[g] - 1이다.

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <stdio.h>
#include <ctime>
#include <memory.h> // memset
#include <numeric>
#include <stack>
#include <sstream>
using namespace std;

int f, s, g, u, d; // S -> G
vector<int> v[1000001];
int visited[1000001]; // 방문 확인 배열 + depth 표시 배열

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> f >> s >> g >> u >> d;

	/*
	그래프 만들기.
	각 층을 순회하며 갈 수 있는 모든 층을 연결해준다.
	각 층은 두 개의 층과만 연결된다. U층 위와 D층 아래.
	양방향 그래프가 아님에 주의!!
	*/
	for (int i = 1; i <= f; i++)
	{
		if (i + u <= f) v[i].push_back(i + u); // U층 위
		if (i - d >= 1) v[i].push_back(i - d); // D층 아래
		else continue;
	}
}

void BFS()
{
	queue<int> q;
	q.push(s);
	visited[s] = 1; // 0으로 하면 for if문에서 걸림

	while (!q.empty())
	{
		int now = q.front();
		q.pop();
		for (int i = 0; i < v[now].size(); i++)
		{
			if (!visited[v[now][i]])
			{
				visited[v[now][i]] = visited[now] + 1;// 엘레베이터 이동시 depth 추가
				q.push(v[now][i]);
			}
		}

	}
}

void SOLVE()
{
	BFS();

	if (s == g) cout << 0;
	else if (visited[g]) cout << visited[g] - 1;
	else cout << "use the stairs";

}

int main()
{
	INPUT();

	SOLVE();
}

🥇문제 후기

배열 형태가 아닌 그래프 문제를 만나니, 처음으로 이런 유형을 만났을때 헤맸던 기억이 난다. 지금 생각하면 너무 간단한데.. 그만큼 경험이 중요하구나싶다. 또한 단방향 그래프인 것도 문제를 보자마자 떠올린 것이 아닌 코드를 짜다가 떠올랐다. 이번 경험을 통해, 다음에는 문제를 보자마자 떠올릴 수 있으리라 믿는다. 코드를 빠르게 작성했으나, visited[s]를 0으로 초기화해버리는 반복적인 실수를 함으로써 수십분을 낭비했다.
결론: 무지성 초기화는 금물!