Approach 문제를 잘 관찰해보면, 위에서 표현한 2차원 각 공간에 있을 수 있는 물의 높이는 다음과 같은 절차를 거쳐서 결정하게 된다. 1. 외부와 직접적으로 마주하고 있는 공간은 구멍의 높이에 맞춰서 무조건 높이가 형성이 된다. 2. 외부와 직접적으로 마주하고 있는 공간과 직접적으로 구멍이 뚫려있는 경우, 뚫린 구멍의 높이와 외부와 직접적으로 마주하고 있는 공간의 높이값 중 최댓값으로 결정된다. (잘 생각해보면 자명하다.) 3. 2의 과정을 반복함으로써 해당 영역에 위치한 물의 높이를 구할 수 있게 된다. 이때, 물이 계속해서 빠져나가는 상황이므로 넘치게 하는 최소 경계값을 구하는 것과 같고, 이는 다익스트라 문제로 회귀할 수 있게 된다. 최소값을 구해나간다는 점에서 dist를 업데이트하고 pq에..

Approach 문제에서 열어야하는 문의 최솟값을 물어보고 있고, 정점과 정점 사이에 이동할 때 벽의 개수가 가중치라고 생각해보면 최단경로(거리)문제로 치환해서 풀 수 있다는 것을 눈치챌 수 있다. 문제에서 예시로 들어준 것을 잘 분석해보면, 2명의 죄수가 바깥으로 나가기 위한 최단경로와 관련이 있다는 것을 알 수 있다. 하지만, 벽을 중복해서 부술 수 있다는 점 때문에 단순하게 다익스트라로는 위 문제를 쉽게 해결할 수 없게 된다. 추가적으로 문제를 더 고민해보면, 결국 모든 상황에서 상근이가 바깥에서 안으로 들어오는 것과 2명의 죄수가 바깥으로 나가기 위한 최단경로는 한 점에서 만날 수 밖에 없다는 점을 착안하면 결국 3번의 최단거리의 합에서 벽일 경우 중복을 제거하기 위해 2를 빼주면 된다. Code..

Approach 문제를 잘 관찰해보면, 현재 방문했던 주유소 중 주유 비용이 가장 싼 것이 무엇인지를 저장해두는 것이 중요하다는 것을 쉽게 파악할 수 있다. 추가적으로, 현재까지의 주유 비용이 가장 싼 것이 어느 것인지에 따라서 특정 점까지 방문하는데 필요한 비용이 다르므로 DP처럼 차원을 1개 더 잡아줘서 다익스트라를 돌려주면 된다. https://viyoung.tistory.com/380 [백준 10217번] [Dijkstra / DP] KCM Travel Approach 잘 생각해보면, 비용 단위로 최단거리를 구해주면 된다. https://viyoung.tistory.com/369 문제와 유사하다. Code #include #define fastio cin.tie(0)->sync_with_stdio..

Approach 라빈-카프 방법으로 접근하였다. 1. 일단 그림의 각 행에 대해서 Rabin fingerprint 해시함수를 활용하여 해싱을 한다. 2. 1에서 구한 해싱값을 이용하여 다시 해싱을 한다. 단, fingerprint_x를 다르게끔 해싱을 한다. 3. 걸작에 대해서도 동일하게 1, 2과정을 반복해준다. 단, 걸작의 크기가 그림의 크기보다 클 수 있으므로 동일한 크기를 기준으로 해싱을 해준다. 4. 믿음과 신뢰를 가지고, 해싱한 값이 같으면 동일한 패턴이 나왔다고 생각해준다 kmp나 야호코라식 등등으로 접근할 수 있다는데, 차후에 다시 풀어보는 것으로.. 라빈-카프 알고리즘에 대해서는 다음 블로그를 참고하도록 하자. https://m.blog.naver.com/kks227/22092727216..

Approach 전형적인 KMP문제 KMP 알고리즘에 대해서는 다음 블로그 글을 참고하도록 하자. https://bowbowbow.tistory.com/6 KMP : 문자열 검색 알고리즘 문자열 검색이 뭐지? 워드프로세서를 사용할 때 찾기 기능을 사용한적 있을 겁니다. 브라우저에서도 Ctrl+F 단축키를 눌러 검색할 수 있습니다. 아래 이미지는 브라우저에서 "테이프"를 검색했 bowbowbow.tistory.com Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; using ll = long long; using pii = pair; using tiii = tuple; int move_x[4] = {-1, 1,..

Approach 전형적인 LCA 문제 Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; using ll = long long; using pii = pair; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; const int MAX = 18; vector adj[100001]; int parent[100001][18]; int depth[100001]; bool visited[100001]; void dfs(int cur, int cur_depth){ visited[cur] = 1; depth[cur] = cur_depth; for(auto &p :..

Approach 정해진 출발점을 기준으로 최단거리가 m보다 작으면 방문할 수 있는 정점이라는 아이디어를 파악했으면 모든 정점을 출발점으로 설정하고, 다익스트라를 통해 최단거리가 m보다 더 작은 모든 정점에 속한 아이템의 수를 다 더해준 뒤 그 중 최댓값을 출력해주면 된다. Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long ll; typedef pair pii; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; const int INF = 1000000000; //ElogV * V int main() { fastio; i..

Approach 다익스트라를 돌리되, parent 배열을 따로 잡아줘서 역추적해주면 된다. Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long ll; typedef pair pii; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; const int INF = 200000000; int main() { fastio; int n, m; cin >> n >> m; vector edge[n]; for(int i = 0; i > a >> b >> c; edge[a - 1].pu..