mintuchel mintuchel

맨처음에는 모든 정점을 BFS로 돌렸다 하지만 BFS로 돌릴 시 아래와 같은 경우에3을 먼저 방문하고 4까지 방문해서4가 visited 처리가 되면2번에서 4번에 방문하지 못한다  따라서 1 -> 4는 사실 2인데1 -> 4 가 201로 되서 4까지 못간다고 판단한다 따라서 각 N개의 노드에서 다른 노드로 가는 최적경로를 모두 구하고각 N개의 노드에서 타 노드로 R만큼의 거리 이내에서 갈 수 있는지 판단하는 식으로 풀어야한다 따라서 플로이드 워셜로 풀면 된다 #include #include #define SIZE 101using namespace std;int dp[SIZE][SIZE];int item[SIZE];int N, M, R;int main(){ ios::sync_with_stdio(0);..

벨만포드에 대한 정확한 이해와 원리를 알아야 풀 수 있다 그리고 벨만포드 내 사이클의 유무를 넘어사이클과 최적경로간의 관계에 대한 고민을 해야하는 문제이다 오민식의 고민과 같이 풀어보면 좋다 [벨만포드 적용 시 고려해봐야할 것들] 1. 벨만포드를 돌면서 최적경로 노드 순서를 어떻게 구할 것인가?-> 자신이 업데이트 되었을때의 간선 시작노드를 저장한다 2. 사이클 유무를 어떻게 파악할 것인가?> N-1번 돌린 뒤 한번 더 돌린다 3. 사이클과 최적경로의 관계는 몇개가 있는가?> 2개 4. 사이클을 구성하는 노드는 어떻게 저장할 것인가?> unordered_set으로 5. 사이클이 최적경로에 영향을 미칠 수 있다는 것을 어떻게 확인할 것인가?> 4번에서 구한 노드들 가지고 BFS를 돌린다 https://ww..

우선 이 문제는 굉장히 중요한 문제다. 최단거리 문제로 dijkstra 랑 floydwarshall을 이용해서 풀 수 있는데 둘 다 시간초과 나지 않고 풀 수 있다. 그리고 floydwarshall로 풀때는 일반적인 floydwarshall 써서 그대로 풀어주면 되는데 dijkstra는 살짝 새로운 접근방식으로 풀어야한다 일단 내 첫번째 풀이인 floydwarshall 부터 보고 내가 게시판을 보고 깨달은 dijkstra 풀이법도 보자 [1. floydwarshall solution] 우선 두 가지를 파악할 수 있다 1. X 마을로 오고 가야함 2. 최단거리로 오고 가야함 이러면 최단거리 알고리즘인 다익스트라 벨만포드 플로이드 워셜 중 하나를 택하면 됨 ㅇㅇ 근데 시간이 무조건 양수이므로 일단 벨만포드를..

최근 다시 푸니 결과는 더 좋은거 같은데접근 방식이 아예 달라서 둘 다 기록해 놓는다 1. 방향 그래프 + DFS + DP 사용 우선 높이가 낮은 곳에서 높은 곳으로 밖에 못올라가므로방향 그래프로 저장해준다그 이후 각 노드를 시작점으로 하여 dfs를 통해각 노드를 시작점으로 삼았을 시 얼마나 올라갈 수 있는지 계산해준다이때 dfs를 재귀적으로 돌때 이미 계산이 된 노드들은 다시 계산이 안되도록dp 배열을 통해 기록해놓는게 핵심이다 #include #include #include #define SIZE 5001using namespace std;int N, M;int height[SIZE];int ans[SIZE]; // visited를 ans가 -1인 것으로 판단가능함vector> graph(SIZE);..

우선 막 여러개의 조건들이 . 여기서 문제들의 우선순위에 대한 상관관계가 있다. 즉 방향성이 있는 관계들이다. 또한 가능하면 쉬운 문제들부터 풀어야한다고 한다. 즉 번호가 작은 것부터 풀면 된다. 그래서 어떤 문제를 풀때마다 상황이 계속 바뀐다는 것을 알 수 있다. A풀고 C풀어야되는데 A풀고 C를 바로 안풀어도 된다 A풀고 C보다 더 쉬운 문제인 B를 풀고 C로 넘어가도 된다. 따라서 우선순위큐를 사용해야한다. 매순간이 그리디적인 상황이기 때문이다 이렇게 생각해놓고 보니 위상정렬 문제라는 것을 알 수 있었다. 즉 진입차수를 중심으로 우선순위큐를 사용해서 풀면 된다. 매번 하나 풀고 pq 원소들을 최신화 시켜주면 된다 #include #include #include #define SIZE 32001 us..

다익스트라 연습 문제이다. 길에서 마주치는 소를 가중치라고 보면 된다. 다익스트라는 양방향 그래프에서도 적용되는데 이유는 생각해보면 간단하다. #include #include #include #include #include #include #define SIZE 50001 using namespace std; int N, M; // // arr[i]는 i노드와 연결된 경로들 vector vector arr(SIZE); // priority_queue pq; bitset visited; vector ans(SIZE); int Dijkstra(int start, int end) { for (int i = 1; i ans[start]) continue; // pq에서 나왔다는 것은 최소값 확정이라는 뜻 vis..

그냥 최소 신장 트리 구한 다음에 가장 큰 간선만 빼주면 된다. MST 구했다는게 우선 모든 노드가 연결된 트리가 나왔다는 것이므로 여기서 간선 하나만 빼주면 문제가 원하는대로 2개로 분할된 도시가 나오기 때문이다. 간선 가중치 합이 10억 이하이므로 int로만 돌려도 감당ㄱㄴ #include #include #include #define SIZE 100001 using namespace std; int N, M; int parent[SIZE]; // 우선 전체 kruskal을 구하고 // 그 중 가장 큰 간선 값만 빼주면 됨 // 그게 이분할 되는거니까 int findParent(int a) { if (parent[a] == a) return a; else return parent[a] = findPa..

그래프 이론 중 가장 대표적인 유형인 최소 신장 트리 문제 여기서 중요한 것만 간략히 말하자면 1. unordered_map으로 우선 간선과 정점 정보를 받고 vector로 변환해서 정렬하려고 하면 안됨 처음에는 key-value 형식으로 받은 후에 vector로 바꿔서 정렬 후에 함수 인자로 넣어서돌리려고 했는데 이러면 문제가 발생함. 만약 간선의 가중치가 같으면 map 특성 때문에 계속 해당 간선 key값이 최신화됨. 예시를 들자면 1-2 cost = 3 이 있었는데 만약 3-5 cost = 3 이 들어오면 1-2 는 없어지고 3-5 에 대한 정보만 남는다는 거임.그래서 그냥 vector로 다 받아주면 된다. 그러니까 이렇게 하면 안된다는 뜻임.unordered_map> info;//for문info[..

사실 이 문제는 알고리즘이 필요가 없다. 모든 가중치는 1이라 봐도 무방하고 모든 국가를 여행하기 위한 비행기 종료의 최소 개수 == 간선 수 이므로 최소신장트리의 간선수는 정점개수 N -1이므로 답이 그냥 N-1이다. #include #include #define SIZE 1001 using namespace std; int T, N, M; vector arr; int parent[SIZE]; // 최소 스패닝 트리 // 모든 간선의 가중치가 1이므로 정렬필요없음 int findParent(int node) { // 자기자신이 부모노드이면 if (parent[node] == node) return node; // 자기자신이 부모노드가 아니면 // 자신의 부모를 찾고 그걸로 자신의 부모값을 최신화 시켜주..