너비우선탐색

1. 개요 안녕하세요. 이 문제의 유형은 너비 우선 탐색 + 경로 추적입니다. 대부분은 2차원 배열이나 그래프 자료구조를 가지고 너비 우선 탐색을 수행하지만 이 문제의 경우 1차원 배열에서 너비 우선 탐색을 돌려야합니다. 사실 3차원 배열에서 너비 우선 탐색을 돌리는 것과 마찬가지로 이동 배열 하나를 두고 수행하시면 쉽게 풀이할 수 있습니다. 2. 문제 풀이2 - 1. 너비 우선 탐색 저는 이전에 숨바꼭질 시리즈를 풀어본 적이 있는데 그 때마다 순간이동에 대한 처리를 어려워했습니다. 물론 구현이 어렵지는 않지만 깔끔하게 작성할 수 있는 방법을 찾다가 포기했었죠. 이번엔 C++의 함수 포인터 배열을 사용하여 구현해보았습니다. 각 이동마다 함수를 선언해야한다는 불편함이 있지만 이동 방법이 많지 않아 괜찮아..

1. 개요 안녕하세요. 이 문제의 유형은 너비우선탐색입니다. 값이 변하기 전과 후가 주어집니다. 그리고 나누어진 영역 중 하나의 여역만 값이 변했는지 판단하면 됩니다. 저는 너무 어렵게 생각한 나머지 돌고 돌다가 풀이했습니다. 이전 문제를 골드 1 bfs를 풀어서 그랬던 것 같습니다. 유형 파악도 중요하지만 접근 방식은 단순하게 가져가는 것이 중요한 것 같습니다. 2. 문제풀이 값이 변하기 전 배열을 A, 변한 후 배열을 B라고 해봅시다. 완전탐색으로 배열을 순회하면서 A[i][j] != B[i][j]인 곳을 찾아 (i, j)에서부터 너비우선탐색을 수행합니다. (i, j)가 포함되어 있는 A의 영역값을 모두 B[i][j]로 수정한 다음, 순회를 종료합니다.A == B라면 YES를 A != B라면 NO를 ..

1. 개요 안녕하세요😊 이 문제의 유형은 너비우선탐색(BFS)입니다. 문제 설명은 단순합니다. 직육면체가 여러 개 쌓여있는 곳에 수영장을 만들고, 사용한 물의 개수를 구하는 것이 요구사항입니다. 수영장을 만들 곳의 크기는 N * M의 직사각형으로 주어지네요. 우리가 알 수 있는 정보는 각 칸에 쌓여있는 직육면체의 높이입니다. 문제를 풀이하기 전 서술되어 있는 조건을 나열해 보겠습니다.물은 항상 높이가 더 낮은 곳으로만 흐른다.직육면체 위의 표면에는 물이 없다.땅의 높이는 0이고, 땅은 물을 무한대로 흡수할 수 있다. 3번째 조건을 확인하시면 배열의 범위를 벗어나는 곳은 땅이라고 유추할 수 있습니다. 물을 부울 수 있는 곳은 직육면체가 이루는 테두리 안쪽임을 확인할 수 있습니다. 너비우선탐색을 하면서 현..

1. 개요 안녕하세요. 이번에 푼 문제의 유형은 너비우선탐색입니다. 하지만 그래프 모델링을 할 때 발상이 필요합니다. 그 이후에는 단순 너비우선탐색입니다. 저도 안일하게 그래프 모델링을 해 MLE를 받았었습니다. 2. 문제 풀이2 - 1. Naive한 그래프 모델링 그래프 모델링을 고민해봅시다. naive하게 구현하자면 각 station을 정점으로 하는 그래프를 준비합니다. 하이퍼튜브로 연결된 각 station들을 이중 for loop로 간선을 추가하면 끝입니다. 하지만 이는 MLE가 발생합니다. 튜브는 최대 1,000개이 각 튜브 내에 1,000개의 station을 모두 연결하게되면 하나의 튜브에서 간선이 1,000,000개가 생성이 되고 최종적으로 그래프의 간선의 개수는 1e9개가 됩니다. 문제의 메..

1. 문제 풀이 너비우선탐색을 응용한 시뮬레이션 문제입니다. 동서남북에 대한 식별 번호들이 문제 설명에 주어져있습니다. 이로 인해 방향을 전환하는 명령어 수행에 어려움이 있을 수 있습니다. 따라서 초반에 주어진 입력된 방향값만 조정하여 풀이하는 것이 가장 깔끔한 풀이일 것 같습니다. 저는 문제에서 주어진 방향에 대한 식별 번호를 그대로 가져와 처리하느라 조금 시간이 소요되었습니다. 이외 주의할 점은 회전에 대해서도 가중치를 주어야 하는 점 밖에 없습니다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; ty..

1. 문제 풀이문제 유형은 그래프 탐색입니다.매개 변수 roads를 통해 인접리스트 형식으로 변환거리 배열 d를 -1로 초기화 후 목적지(destination)에 대해서만 0으로 갱신큐에 dst 삽입 후 너비 우선 탐색 수행sources를 순회하면서 d[sourcese[i]] 값을 벡터에 삽입 후 반환 2. 코드#include using namespace std;queue q;vector adj[100'005];int d[100'005];vector solution(int n, vector> roads, vector src, int dst) { for(auto edge : roads) { adj[edge[0]].push_back(edge[1]); adj[edge[1]].pu..

1. 문제 풀이 문제 유형은 너비 우선 탐색입니다. multi-source bfs를 진행하여 풀이하는데 주의할 점은 물이 차있는 지역에 대한 정보를 먼저 큐에 삽입해야 합니다. 그 뒤에 고슴도치 위치 정보를 삽입하여 물인지 고슴도치인지 판별하여 다른 작업을 수행해 주면 됩니다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typedef vector vpi; typedef vector vpl; typedef ..

1. 문제 풀이 이분 그래프인지 판별하는 문제였습니다. 그래프가 비연결 그래프일 때 처리하는 방법에서 애를 먹는 바람에 시간이 조금 걸렸습니다. 너무 안일하게 문제를 읽은 것 같습니다. 너비우선탐색을 사용해서 적대 관계와 우호 관계로 나눌 때, 인접한 두 정점이 같은 관계가 되는지 안되는지 판별해 문제를 풀이했습니다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typedef vector vpi; typed..