KPU CE

다익스트라 알고리즘은 출발 노드로부터 각 노드들의 최단거리를 구하는 알고리즘이다. 다익스트라 알고리즘을 이해하기 위해서는 일단 인접 리스트에 대해서 먼저 공부해야 이해할 수 있으므로 인접 리스트에 대해서 공부해오자. 예를 들어서 설명해보겠다. 위와 같은 가중치가 있는 그래프가 있다. 여기서 출발지가 1이라고 했을 때 각 노드들로 가는 최단경로를 구하는 것이 다익스트라 알고리즘이다. 1 2 3 4 5 infy infy infy infy infy 위와 같이 최단거리를 저장해두는 배열 dist를 생성한다. 초기값은 무한으로 해둔다. 다익스트라 알고리즘은 다음 노드의 dist 값과 현재노드의 dist값+가중치를 비교하여 더 작은 값이 다음 노드의 dist가 되는 알고리즘이다. 1을 출발선이라고 하고 위의 설명과..

문제 www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 해결 1. BFS를 이용해서 탐색을 할 때 방문할 노드가 개방 가능 조건에 있다면 border배열을 true로 해준다 2. true로 되어 있는 노드를 하나 방문 후 연결되어 있는 모든 true노드를 방문한다. 3. 방문할 때마다 cnt++ 을 해줘서 몇 개의 노드를 방문해 줬는지와 sum+=map [y][x]를 해줌으로써 방문한 노드들의 평균값을 구할 수 있다. 4. 방문을 마친 노드..

문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 www.acmicpc.net 문제해결 1. DFS를 이용해서 가장 경로가 큰 노드를 찾는다. 2. 가장 큰 노드를 루트로 하고 다시 DFS를 해준다. 코드 ide.goorm.io/shared_files/sksj0111_9c7f680ec5975ba4aae255f776fdbd4c1605924147580 1167.cpp - goorm 구름IDE에서 공유된 소스코드를 볼 수 있는 페이지입니다. ide.goorm.io..

문제 https://www.acmicpc.net/problem/1761 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net 문제해결 1.벡터에 정점과 가중치를 입력받는다. 2.DFS를 통해서 각 노드들마다 부모와 깊이를 알아낸다. 3.LCA알고리즘을 실행한다 3-1. 만약 두 노드가 같으면 출력한다 3-2. 두 노드가 같지 않고 깊이가 같으면 두 노드 다 깊이-1로 이동한다. 3-3 한 노드가 다른노드보다 깊이가 크면 큰 노드가 깊이-1로 이동한다. 4. 두 노드가 같아 질때까지 반복한다. 코드 ide...

문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 이 문제는 최소 스패닝 트리 알고리즘을 사용하면 바로 풀리는 문제이다. 문제해결 1.vector v 를 사용하여 가중치,노드1,노드2 순으로 입력받는다. 2.가중치에 대하여 오름차순으로 정렬한다. 3.parent배열을 모두 parent[i] = i로 초기화 한다 (처음에는 모두 부모가 자기 자신이다 -> 모두 다 끊어진 상태로 시작한다,최소스패닝..

문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 이 문제는 최소 스패닝 트리 알고리즘을 사용하면 바로 풀리는 문제이다. 문제해결 1.vector v 를 사용하여 가중치,노드1,노드2 순으로 입력받는다. 2.가중치에 대하여 오름차순으로 정렬한다. 3.parent배열을 모두 parent[i] = i로 초기화 한다 (처음에는 모두 부모가 자기 자신이다 -> 모두 다 끊어진 상태로 시작한다,최소스패닝 알고리즘이다) 4.만약 두 노드가 연결되지 않은 노드라면 연결하고 가중치를 result에 더해간다. ->두 노드가 연결된 유무는 find..

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 문제해결 1. 2차원 배열에 데이터 입력받음 2. 가장 모서리는 항상 빈공간이므로 (0,0) 에서 BFS를 이용하여 치즈 바깥쪽을 9라고 해놓은다. 3. 치즈를 차례차례 하나씩 방문하면서 2개 이상 9하고 인접하면 1에서 0으로 바꾼다. 4. 위 방법을 치즈가 완전히 다 없어 질때 까지 반복한다. 코드 ide.goorm.io/shared_files/sksj0111_91856d3b48581..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제해결 1. 데이터를 2차원배열에 입력받는다. 2. 재귀를 이용하여 모든 경우의 수의 놓일 수 있는 벽을 세운다. 3. 벽을 3개 세우면 bfs을 통해 바이러스를 퍼뜨린다. 4. 바이러스를 퍼뜨린 후 남아있는 안전구역을 센다. 5. 2~4번을 반복하면서 안전구역이 가장 많은 경우를 찾는다. 이 문제는 벽을 세우는게 가장 핵심 포인트다. 나도 처음에는 백트래킹을 잘 몰라서 못풀었는데 백준 문제 중에 N과M이라..

www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 코드 ide.goorm.io/shared_files/sksj0111_1a7d90396ccad3d7866f148cdb1af83f1604063857986

문제해결 1.최단거리를 저장할 최대힙을 만들어준다. 2.최대힙의 사이즈가 k보다 작으면 무조건 push 3.최대힙의 사이즈가 k이고 top의 값이 new_val보다 크면 pop후 new_val를 push 한다. 4.이런 식으로 다익스트라 알고리즘을 응용한다. 코드 (코드의 주석이 상세하게 적혀있어 보시면 이해가 바로 되고 도움되실거예요!) ide.goorm.io/shared_files/sksj0111_250e20fbfd92552322517b1b09da0ed61603463344960 1854(3).cpp - goorm 구름IDE에서 공유된 소스코드를 볼 수 있는 페이지입니다. ide.goorm.io:443