14496번: 그대, 그머가 되어

문제접근🤔

• 전형적인 bfs로 접근
• visited로 계속 업데이트를 하여 치환횟수를 구할 예정
• 초기화를 -1로 해놓고 업데이트가 안 되어 있으면 치환이 한번도 되지 않았다는 뜻이기 때문에 그대로 -1 출력

놓쳤던 부분😅

• 문제만 보고 단방향으로 생각했지만, 예제2를 보면 양방향으로 보는 것이 맞다..ㅠ

코드😁

2296 KB

0 ms

#include <iostream>
#include <vector>
#include <queue>

int a, b;
int n, m;
std::vector<std::vector<int> > way;
std::vector<int> visited;

void input_setting()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	int input1, input2;

	std::cin >> a >> b;
	std::cin >> n >> m;
	way.resize(n + 1);
	visited.resize(n + 1, -1);
	for (int i = 0; i < m; i++)
	{
		std::cin >> input1 >> input2;
		way[input1].push_back(input2);
		way[input2].push_back(input1);
	}
}

void solution()
{
	std::queue<int> q;

	q.push(a);
	visited[a] = 0;

	while (!q.empty())
	{
		int cur = q.front();
		q.pop();

		if (cur == b)
			break ;
		for (int i = 0; i < way[cur].size(); i++)
		{
			int next = way[cur][i];
			if (visited[next] == -1)
			{
				q.push(next);
				visited[next] = visited[cur] + 1;
			}
		}
	}
}

void print()
{
	std::cout << visited[b];
}

int main(void)
{
	input_setting();
	input();
	solution();
	print();
	return (0);
}