문제접근
•
전형적인 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);
}
C++
복사
