Memo
로직 설명
•
인접 리스트 형태로 저장합니다.
•
간선의 비용이 모두 동일하므로, BFS로 구현이 가능합니다.
•
{다음 노드의 번호, 누적 이동 거리}를 큐에 넣고, 다음 노드의 번호가 b가 되면 (누적 이동거리 + 1)을 출력합니다.
•
큐가 빌 때 까지 b가 나오지 않는다면, 치환이 불가능 한 것이기 때문에 -1을 출력합니다.
어려웠던 부분
•
처음 다익스트라로 구현했을 때, 메모리 초과가 발생하였습니다. → bfs로 바꿨습니다.
Code
제출 날짜
@5/14/2021
메모리
2296 KB
시간
4 ms
#include <iostream>
#include <vector>
#include <queue>
std::queue<std::pair<int, int> >q;
std::vector<std::vector<int> >graph;
bool visited[1001];
int a,b,N,M, ans = -1;
void io_faster()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
int x, y;
io_faster();
std::cin >> a >> b >> N >> M;
graph.resize(N + 1);
for (int i = 0 ; i < M ; i++)
{
std::cin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
}
void bfs()
{
int node, d;
if (a == b)
{
ans = 0;
return;
}
q.push({a, 0});
visited[a] = 1;
while (!q.empty())
{
node = q.front().first;
d = q.front().second;
q.pop();
for (size_t i = 0 ; i < graph[node].size() ;i++)
{
if (visited[graph[node][i]])
continue;
if (graph[node][i] == b)
{
ans = d + 1;
return ;
}
visited[graph[node][i]] = 1;
q.push({graph[node][i], d + 1});
}
}
}
void solve()
{
bfs();
}
void print_val()
{
std::cout << ans;
}
int main()
{
input();
solve();
print_val();
return (0);
}
C++
복사