https://www.acmicpc.net/problem/14953 백준 14953번 Game Map 문제입니다. dfs로 탐색하고 dp배열에 최대로 갈 수 있는 노드의 합을 저장해 놓습니다. 한번 계산한 최대값은 변하지 않으므로 다른 노드에서 계산할 때 이용합니다. 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include using namespace std; int dfs(vector& graph, vector& neighbor, vector& dp, int cur) { if (dp[cur]) return dp[cur];//이미 계산한 경우예요 int cnt = 1;//나 자신 for ..
https://www.acmicpc.net/problem/3653 백준 3653번 영화 수집문제입니다. 세그먼트 트리를 활용해서 트리에 선택한 DVD위에 놓여있는 DVD의 갯수를 합으로 저장해 놓습니다. DVD를 뽑았다면 맨위에 두는 것을 업데이트 해가면서 문제를 풀면됩니다. 배열을 n+m(DVD갯수 + 옮길 DVD갯수)로 만들고 세그먼트트리도 같은 갯수로 만듭니다. 각 DVD의 위치를 저장해놓을 배열도 만듭니다. 각DVD의 값을 1로하는 세그먼트 트리를 만듭니다. DVD를 뽑을 때마다 세그먼트트리의 값을 갱신합니다. 참고한 블로그 (https://lyzqm.blogspot.com/2017/07/segment-tree-3653.html) (http://jaimemin.tistory.com/712) 123..
https://www.acmicpc.net/problem/1162 백준 1162번 도로포장 문제에요! 각 지점에서 도로를 몇번포장했는지 각각 다 체크해주어야하기 때문에 visited배열을 [정점수][포장사용한횟수]로 만들어줘야해요. 마지막에는 visited[정점수]에서 최솟값을 찾아주면 됩니다. *paved를 사용하면 paved++, 그냥이동(비용0) 사용하지않으면 기존의 다익스트라 알고리즘사용. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768#include #include #include #include using names..
백준 5214:환승
https://www.acmicpc.net/problem/5214 백준 5214번 문제 환승이예요. 지금까지 풀었던 다익스트라 문제와는 많이 다른문제입니다. 정점끼리도 이어져있고, 하이퍼튜브끼리도 이어져있습니다. 이번문제의 쉬운 풀이법은! 기존의 문제대로 정점끼리 계산을 하되 하이퍼튜브도 정점으로 생각해서 계산해 주는것. 정점 + 하이퍼튜브로 계산하면 기존 다익스트라 문제와 비슷하게 풀 수 있어요! *참고한 블로그 http://degurii.tistory.com/19 이렇게 보시면 1 -> T1 -> 3 -> T3 -> 6 ->T5 -> 9 인 경우와 1 -> T2 -> 5 -> T4 -> 6 ->T5 -> 9 인 경우가 있어요!물론 T1 = N, T2 = N+1 .. 로 매칭된 정점을 이용하겠죠? 튜브..
https://www.acmicpc.net/problem/6118 이번문제는 간단한 다익스트라 알고리즘문제예요. 문제는 최단거리를 계산하지만! 가장먼곳(최장거리)를 계산하면 되는것이에요. 가장 작은번호 출력 주의! 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include #include #include using namespace std; #define INF (static_cast(1e9))#define endl '\n'typedef pair PAIR;int main(void) { ios::sync_with_stdio(false); int N, M; ci..
https://www.acmicpc.net/problem/13424 백준 13424번 비밀 모임이예요. 해리포터 보고싶다 이번 문제는 모든 친구들로부터 가장 짧은 곳을 찾아야하기때문에 각 테스트케이스마다 K번씩 탐색해야해요. 그래서 minimum배열에 각점에 대한 최단경로 정보들을 저장해 두고 마지막에 친구들이 가장 편하게? 올수 있는 방을 골라주면 됩니다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include #include #include #include using namespace..
https://www.acmicpc.net/problem/2211 백준 2211번 다익스트라 관련 문제예요. 기본 최소비용탐색 문제에서 회선 정보만 빼오면 되는거예여. prev배열을 만들어서 현재노드와 전 노드를 연결하는 회선 정보를 저장해요. -1이라면 회선이 없는 것. 갯수를 카운팅 해주고 회선 정보를 출력하면 되요. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include #include #include using namespace std; #define INF (static_cast(1e9))#define endl '\n' typede..
https://www.acmicpc.net/problem/14618 백준 14618번 다익스트라 문제입니다. 다른 기본 문제들과 같이 시작점에서 (J점에서) 가장 가까운 점을 찾..으면 안되구요(경험담). A, B로 가는 가장 가까운 길을 찾아야합니다.. 그리고 A, B최단거리길이가 같으면 A를 출력하는 것도 고려해서.. 쿨럭ㅠㅠ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include #include #include #include using namespace std; #define INF (sta..
https://www.acmicpc.net/problem/1261 다익스트라 배열버전이예요.. 배열을 상하좌우로 연결된 그래프라고 보면 편해요. 배열을 다익스트라로 탐색하면되요. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include #include using namespace std;#define endl '\n'#define r first#define c secondconst char dr[4] = { 0,1,0,-1 };const char dc[4] = { -1,0,1,0 }; typedef pair pos;typedef pair PAIR;..
https://www.acmicpc.net/problem/4485 아니요.. 링크라구요 링크!!!...이번문제도.. 다익스트라 문제예요.. 하지만 입력에서는 배열이네요? 그러면 상하좌우로 연결된 그래프라고 생각하면 편합니다아.. 큐에는 좌표가 들어갑니다. (0, 0)에서 (N-1, N-1)까지 최소로 갈 수있는 합을 구하면됩니다.. 그리구 시작비용이 0이아니라! (0, 0)에 있는 값이 되겠네요. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include #include #include using namespace std;#defin..