Search
Duplicate

그대, 그머가 되어

주차
20
문제번호
14496
언어
C++
티어
실버
유형
다익스트라
nj_Blog
nj_상태
이해도
풀이
사람
이해도 2
13 more properties

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++
복사