https://www.acmicpc.net/problem/5214 보통 BFS에서는 정점이 하나의 종류이지만, 이 문제에서는 정점을 두 종류로 나누어 푸는 것이 좋다."역"에 대한 정점과 "하이퍼튜브"를 정점으로 두고 배열을 저장한다.이러면 각 입력의 최댓값인 100,000개와 1,000개가 주어져도 101mb를 차지하기 때문에 메모리 초과를 해결할 수 있다. 정점들을 저장할 때, 시작 역인 1번 역을 포함하는 하이퍼튜브들을 따로 저장한다.문제가 1번 역에서 시작하여 마지막 역에 도착하는 것이니, 무조건 1번 역으로 시작해야 하기 때문이다. 1번 역이 포함된 하이퍼튜브들을 대상으로 BFS를 수행하여 최단 거리를 구한다. BFS 로직방문한 하이퍼튜브를 체크하여 순환이 일어나지 않도록 한다.현재 하이퍼튜브에..
BFS
https://www.acmicpc.net/problem/3197 정석은 분리 집합(Disjoint Set)을 활용해서 푸는 것 같다.나는 직접적으로 분리 집합을 활용하여 풀지는 않았지만, 이론을 비슷하게 사용했기 때문에 풀린 것 같다. 먼저, 분리 집합과 비슷하게 각 물 좌표마다 물 번호를 매겼다.이는 서로 이어져있을 시, 같은 번호를 공유한다. 물을 모두 순회하며, 닿는 빙하들에 자신의 물 번호를 매기고, 큐에 담는다.이러면, 매 날짜마다 해동되는 새 물만이 큐에 담기게 된다. (0번째 날 제외) 물 큐를 순회하며, 각자 BFS를 실행해서 물 번호를 갱신한다.빙하가 녹아 두 물이 합쳐질 수 있게 되면, 여기서 물 번호가 합쳐질 것이다. 두 백조의 물 번호를 비교하여 같으면 종료한다.#include #..
https://www.acmicpc.net/problem/2573 시간마다 빙산을 녹이는 로직 실행 (상하좌우 0이 있으면 1씩 줄이기) 시간이 지난 후, 남아있는 아무 빙산 1개를 시작으로 BFS 실행 BFS로 탐색한 빙하의 수와 맵에 남아있는 빙하의 수가 일치하지 않으면, 시간 리턴 후 종료맵에 빙하가 없으면 0 리턴 후 종료#include #include #include using namespace std;int dy[]{ -1, 0, 1, 0 };int dx[]{ 0, 1, 0, -1 };int N, M;void AddTime(vector>& Map, queue& qy, queue& qx, queue& qn, vector>& Visit){ queue> Remove; int Size = qy.siz..
https://www.acmicpc.net/problem/17070 문제가 그래프로 되어있어서 처음에 생각한 방식인 BFS를 통해 풀었다.풀고 보니, 정석적인 문제 풀이는 DP를 통해 푸는 것이더라. 파이프는 →, ↘, ↓ 방향으로만 갈 수 있다.이는 각 방향 좌표쌍을 순서대로 저장하여 사용한다. 문제 풀이는 단순하게 현재 끝 파이프의 위치에서 →, ↘, ↓ 방향의 좌표를 queue에 넣는 BFS 방식으로 풀었다. 풀이의 핵심은 파이프가 자신의 방향에서 45º씩 밖에 회전할 수 없다는 점이다.즉, 가로의 경우 가로, 대각선으로만 갈 수 있다. (대각선은 가로, 대각, 세로 다 됨)#include #include #include #include using namespace std;// 방향 좌표쌍int d..
https://www.acmicpc.net/problem/11725 각 정점의 부모를 찾는 문제이다. 노드들의 부모-자식 관계를 알 수 없으니, 그래프의 형태로 노드의 연결을 저장한다. 트리의 루트는 항상 1이다.따라서 1의 자식 노드는 항상 부모 노드가 1이다.1의 자식 노드를 n이라고 한다면, n의 자식 노드는 항상 부모 노드가 n이다. 이 과정은 트리의 루트부터 높이가 높아지며 BFS로 검사하는 것과 같다.#include #include #include using namespace std;int N;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N; vector Node(N + 1); // 1..
https://school.programmers.co.kr/learn/courses/30/lessons/250136 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 해당 문제는 일반적인 BFS로 풀면 효율성 검사에서 시간초과가 난다. 한 번 시추한 석유 뭉치는 다른 x축에서 중복으로 검사할 필요가 없다.1번에서 석유 뭉치를 시추하여 8의 결과를 얻었으면, 2번과 3번에서는 해당 석유 뭉치를 발견하면 바로 8임을 알고 넘어갈 수 있다.이렇게 하면, 일단 시간 초과는 해결할 수 있다. 다음으로, y축으로 내려가며 같은 석유 뭉치를 발견한 경우이다.각 석유 뭉치마다 석유 번호를 매겨 이미 검사한 석유 뭉치인지..
https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 일반적인 상하좌우 BFS로 풀었다.#include #include #include #include using namespace std;int dy[]{ -1, 0, 1, 0 };int dx[]{ 0, 1, 0, -1 };vector solution(vector maps) { vector answer; vector> Visit(maps.size(), vector(maps[0].size(), false)); for (int y = 0; y > q..
https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 일반적인 BFS로 풀었다.각 칸(경로)마다의 가중치가 없기 때문에, 방문처리만 하며 가장 빠르게 목적지에 도달하는 경로가 최단 거리이다.#include #include using namespace std;int dy[]{ -1, 0, 1, 0 };int dx[]{ 0, 1, 0, -1 };int solution(vector> maps){ int answer = 1; vector> Visit(maps.size(), vector(maps[0].siz..
