Approach 위 문제와 거의 유사. https://viyoung.tistory.com/365?category=884242 [백준 1162번] [Dijkstra] 도로포장 Approach 위 문제와 유사하다. https://viyoung.tistory.com/335 [백준 14442번] [BFS] 벽 부수고 이동하기 2 Approach https://viyoung.tistory.com/334 [백준 2206번] [BFS] 벽 부수고 이동하기 Approach 표면.. viyoung.tistory.com 위 문제에서 k가 1인 경우를 구하는 것과 완벽하게 동일하다. 백준 1162번과 달리, 차원을 올라갈 수 있는 경우가 항공편이 존재하였을 때이므로 그 부분만 신경써주면 완벽하게 동일한 문제이다. Code ..

Approach 위 문제와 유사하다. https://viyoung.tistory.com/335 [백준 14442번] [BFS] 벽 부수고 이동하기 2 Approach https://viyoung.tistory.com/334 [백준 2206번] [BFS] 벽 부수고 이동하기 Approach 표면적으로 보면 BFS 대표 유형과 유사해보인다. 다만, 일반적인 문제와 달리 1칸 벽을 뚫을 수 있다는 측면을 추가.. viyoung.tistory.com 위 문제와 상황자체는 완벽히 유사하나, 그래프에서 가중치가 존재하기 때문에 BFS가 아닌 다익스트라로 해결해주면 되는 것이다. Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace s..

Approach 최단 경로의 길이를 물어보는 것에서 다익스트라 문제임을 쉽게 파악할 수 있다. 이 문제에서 눈여겨 봐야할 지점은 반드시 거쳐야하는 정점이 있다는 것이다. 잠시 기억을 더듬어서 고등학교 경우의 수 문제에서 최단거리를 구할 때, 특정한 지점을 반드시 지나는 문제를 어떻게 풀었는지를 잘 생각해보자. 아마도 특정한 지점을 기준으로 분할해서 풀었던 기억이 있을 것이다. 마찬가지로 위 문제도 특정한 지점을 기준으로 분할해서 풀어주면 된다. 두 정점을 순서대로 v1, v2라고 하고, d(a, b)를 a부터 b까지 가는데 필요한 최단 경로의 길이라고 정의하자 d(1, N) = min(d(1, v1) + d(v1, v2) + d(v2, N), d(1, v2) + d(v2, v1) + d(v1, N))이다..

Approach 전형적인 다익스트라 문제 Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; typedef pair pii; typedef unsigned long long ull; typedef long long ll; typedef vector ullv1; typedef vector ullv2; const int INF = 987654321; int main() { fastio; int n, m; cin >> n >> m; vector edge[n]; for(int i = 0; i > a >> b >> c; edge[a - 1].push_back({b - 1..

Approach 대표적인 다익스트라 문제이다. w가 양수인 최단 경로를 구하는 상황이므로 다익스트라로 구할 수 있다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii; const int INF = 987654321; int v, e; vector dist; vector edge; bool visited[20000]; int main(void) { fastio; memset(visited, 0, sizeof(visited)); cin >> v >> e; edge = vector(v); dist = vector(v); fill(dist.beg..

Approach 그래프 탐색 관련한 문제라는 것은 문제를 읽자마자 쉽게 파악할 수 있다. 문제 상황에서 가장 크리티컬한 지점은 탐색과정에서 보석을 얼마나 가지고 있는지를 기억해야한다는 것이다. 왜냐하면, 보석을 얼마나 가지고 있는지에 따라서 방문할 수 있는 지역이 달라지기 때문이다. 따라서 BFS를 돌리는 과정에서, 보석을 얼마나 가지고 있는지를 기억하고 있으면 된다. 같은 지역에 있는 보석은 1번만 주울 수 있으므로, 비트마스킹을 통해 1개의 정수로 어느 지역의 보석을 가지고 있는지를 쉽게 저장해놓을 수 있다. 추가적으로 같은 지역을 방문하더라도 보석이 달라지면 경향성이 달라지므로, visited를 2차원 배열로 잡는다. 위 문제와 비슷한 느낌으로 이해해주면 된다. https://viyoung.tist..

Approach 문제에서 이동 횟수의 최솟값을 묻는 상황이므로, BFS를 바로 떠올려주면 된다. 다만, 이 문제에서 되게 독특한 지점은 각 이동하는 상황에서 키를 가지고 있는지 여부가 굉장히 중요하다. 따라서 키를 가지고 있는지 여부를 set으로 넘겨줘도 되지만, 비트마스킹을 활용해주면 숫자 하나로 모든 것을 판단할 수 있게 된다. 추가적으로 visited도 신경써야 하는데, 키가 달라진다면 기존에 방문했던 곳이라도 양상이 달라질 수 있기 때문에 visited를 3차원으로 잡아주면 된다. 다음 문제와 비슷하게 느낌을 받았으면 충분하다. (위 문제도 단순히 같은 위치를 방문한다고 해서 같은 의미는 아니므로 차원을 1개 늘렸다.) https://viyoung.tistory.com/334 [백준 2206번] ..

Approach 문제에서 주어진 힌트를 보고 잘 생각해보면, 채우는 방법은 한번에 2칸, 한번에 4칸, 6칸, .. 2k칸이 존재한다. 그리고 2칸을 채우는 방법만 3가지이고, 나머지의 경우는 2가지 존재한다. 또한 한번에 2칸 채우는 것을 2번 반복한 것과, 한번에 4칸 채우는 것을 1번 반복한 것의 이후 과정은 완벽학게 동일하므로 이를 중복하여 계산하지 말고 DP로 저장해두면 계산 시간을 줄일 수 있다. (물론 n이 되게 작아서 시간 안에는 무조건 들어온다.) dp[i] : i번째 칸까지 채웠을 때 3 x N크기의 벽을 채우는 경우의 수 dp[i] = dp[i + 2] * 3 + dp[j] * 2 for all j s.t j % 2 == 0 & j 2 Code #include #define fasti..