줌코딩의 코딩일기

문제 문제 링크 어떻게 접근할 것인가 이 문제는 BFS를 이용해서 풀 수 있다. 큐에 들어가는 정보는 두 구슬의 좌표와 이동한 횟수이다. 매번 두 구슬은 벽을 만날 때까지 이동시키고 앞서 있는 구슬이 벽에 붙어있는 구슬이 될 것이기 떄문에 이동 후 두 구슬의 좌표가 같다면 이전 위치에서 덜 움직인 구슬을 하나 뒤로...

문제 문제 링크 어떻게 접근할 것인가 이 문제는 negative edge가 존재하는데 이것이 negative cycle을 발생시키는지 보는 문제이다. 벨만포드에서 negative cycle 체크하는 방법을 이용하면 된다. 유의점 및 힌트 처음에 주어지는 M개의 도로의 정보는 양방향이고 뒤의 웜홀 정보는 단방향이다.(이것 때문에 엄청 헤맸다…) 이 문제의 포인트는 시작점은 아무렇게나 해도 된다는 것이다. 그 이유는...

문제 문제 링크 어떻게 접근할 것인가 이 문제는 대놓고 벨만포드를 이용하라고 하는 문제이다. 유의할 점 초기값이 무한대인데 무한대인 경우에는 연산에 들어가지 않도록 배제시켜주자! 코드 #include <cstdio> #include <vector> #define INF 5000000 using namespace std; int main(){ int n, m; scanf("%d %d", &n, &m); vector< vector<long long> > e(m, vector<long long>(3));...

문제 문제 링크 어떻게 접근할 것인가 이 문제는 최단 경로를 구하는데 중간에 cost라는 옵션이 하나 추가된다. 때문에 단순히 다익스트라를 한번 진행하면서 풀기는 쉽지 않다. 이 문제는 우선순위 큐를 이용해서 공항, 비용, 거리 정보를 모두 보내주면서 최종 지점인 n에 도착했을 때 계속해서 최솟값을 찾아준다. 유의점 및 힌트 근데 BFS 이용할 때...

문제 문제 링크 어떻게 접근할 것인가 이 문제는 목적지로 가는 최단 경로에 특정 길이 포함되는지를 확인해야하는 문제이다. s에서 x까지 가는 길 중에서 g와 h를 지나서 가는 최단 경로는 두가지이다. s->g->h->x와 s->h->g->x 이렇게 두가지이다. 이 두 경우를 찾기 위해서 g, h, s를 시작점으로 다익스트라를 진행하여 결과를 저장한다. 이렇게 찾은 s->g->h->x나 s->h->g->x...