devbelly

문제 https://www.acmicpc.net/problem/5214 알고리즘 BFS 풀이 역들을 잇는 하이퍼튜브들이 주어질 때, $N$역으로 가기 위해 거쳐야하는 최소 역의 수를 구하는 문제입니다. 하이퍼튜브마다 일일이 역들을 연결하게 되면 메모리초과가 발생합니다. 대신에 하이퍼튜브마다 임의의 정점을 하나씩 만든 후, 각 역과 새로 만든 임의의 정점끼리 연결하여 메모리를 절약하였습니다. 위 그림은 문제에서 주어진 첫번째 예시에서 첫번째 하이퍼튜브와 두번째 하이퍼튜브를 시각화한 것입니다. 저는 튜브마다의 임의의 정점을 100005+$i$로 하였습니다. 검은 실선을 가중치 1로 설정하여 풀고난 후, 마지막에 반을 나누어 실제로 거친 역의 수를 구했습니다. 코드 #include #define rep(i, ..

문제 https://www.acmicpc.net/problem/10652 알고리즘 Dijkstra, BFS 풀이 Bessie와 Elsie가 돌아다닐때 드는 에너지와 Piggy Back 상태에서 드는 에너지가 주어졌을 때, $N$까지 도달하기 위한 최소에너지는 구하는 문제입니다. 3인통화 문제와 굉장히 유사합니다. 도착지도 하나의 소처럼 취급을 하여 세 마리의 소에서 각각 다익스트라를 사용하면 문제가 해결됩니다. 다만, 각 소마다 그래프를 이동할 때 드는 비용은 동일하므로 다익스트라 대신 BFS를 사용하면 더 빠르게 문제를 풀 수 있습니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for (int i = 1; i..

문제 www.acmicpc.net/problem/14169 알고리즘 BFS 풀이 레이저를 시작점에서 농장까지 비추도록 거울을 설치해야 합니다. 이때 필요한 최소의 거울 수를 묻고 있습니다. 좌표가 작다면 이 문제처럼 2차원 배열을 만든 후 BFS를 수행하면 됩니다. 하지만 이 문제는 좌표의 범위가 10억 이하이므로 배열을 선언할 수 없을 뿐더러 거울을 설치할 수 있는 장소의 개수인 $N$이 최대 10만이므로 좌표압축을 해도 2차원 배열안에는 넣을 수 없습니다. 핵심은 주어진 좌표를 BFS를 사용할 수 있도록 적절하게 자료구조에 넣는 것 입니다. 이를 위해 $adj$를 사용했습니다. 인접한 좌표끼리 연결할 때(인접하는 것은 x좌표가 동일한 좌표끼리 묶고 y좌표가 동일한 좌표끼리 묶는 것 입니다), 바로 근..

문제 www.acmicpc.net/problem/19606 알고리즘 BFS 풀이 격자판마다 양수가 쓰여있습니다. 양수를 V라고 가정할 때, r X c = V 에 해당하는 (r, c)로 이동이 가능합니다. (1, 1)에서 시작하여 (M, N)으로 이동 가능한지 판별하는 문제입니다. (1,1)에서 BFS를 수행하려면 조금 까다롭습니다. 가능한 (r, c)를 조사를 해야하는데 이 과정이 시간이 걸립니다. 역으로 (M, N)에서 (1,1)로 이동하면 비교적 간단해집니다. V값을 담고 있는 좌표들을 조사하는 방법으로 수행하면 되기 때문입니다. V마다 좌표를 담기 위해 2차원 배열을 사용했고 BFS를 수행해 나가면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i < n..

문제 www.acmicpc.net/problem/15587 알고리즘 BFS 풀이 Bessie가 트리 형태의 목장에서 탈출하려 합니다. 이때 이 탈출을 제지해야하는 최소의 농부 수를 구하는 문제입니다. 탈출구는 리프노드입니다. 만일 한 농부가 $u$노드까지의 거리가 베시보다 가까우면서 다른 농부들보다도 가깝다면 다른 농부들을 카운트할 필요는 없습니다. 이를 위해 다양한 source로부터(여기서는 리프노드, 농부들의 시작점) bfs를 수행할 것입니다. $dist$의 상태에는 3가지가 있습니다. 아직 방문하지 않은 상태인 -1, 농부가 방문한 상태인 0, bessie가 도착한 int_max의 상태입니다. 아래 코드에서 가장 눈여겨 볼 점은 bessie에 해당하는 노드를 queue에 넣을 때, 농부들보다 뒤에 ..