KPU CE

인접 행렬 위와 같이 무방향으로 노드들이 이어져 있다. 이제 이 그래프를 저장하는 2차원배열 ary[6][6]를 만들어준다. 그리고 노드a과 노드b가 이어져있다는 것을 배열로 표현해준다면 ary[a][b] = true, ary[b][a] = true 로 표현해줄 수 있다. 하지만 여기서 단방향 그래프로 만들고 싶으면 예를 들어 a->b인 노드이면 ary[a][b] = true 라고만 해주면 된다. 이렇게 표현하게 된다면 위의 그림은 ary[6][6]의 크기의 배열이 필요하다(ex. ary[5][4] = 1) 이걸 배열로 나타낸다면 아래와 같다. [0] [1] [2] [3] [4] [5] [1] 0 1 0 0 0 [2] 1 0 1 0 0 [3] 0 1 0 0 1 [4] 0 0 0 0 1 [5] 0 0 1 ..

다익스트라 알고리즘은 출발 노드로부터 각 노드들의 최단거리를 구하는 알고리즘이다. 다익스트라 알고리즘을 이해하기 위해서는 일단 인접 리스트에 대해서 먼저 공부해야 이해할 수 있으므로 인접 리스트에 대해서 공부해오자. 예를 들어서 설명해보겠다. 위와 같은 가중치가 있는 그래프가 있다. 여기서 출발지가 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/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이라..

문제해결 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

https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있�� www.acmicpc.net 문제해결 1. 다익스트라 알고리즘을 통해 목적지까지의 최단 거리를 구한다. 2.최단거리를 구하면서 최단거리의 이전노드들을 trace 벡터에 저장하면서 구한다. 3.trace의 있는 노드의 간선들을 재귀를 통해서 제거한다. 4.다시 한번 다익스트라 알고리즘을 돌려서 최단거리를 구한다. 5.코드에 주석 열심히 달았어요 보면은 이해 될 거예요. 코드 ide.goorm...

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 1.루트노드르르 찾는다. 2.벡터를 이용해서 트리를 만들어준다. 3.dfs를 이용해서 탐색을 한다 3-1. 자식 노드가 0개, 1개, 2개이상일때의 경우를 나눈다음 구현한다. 코드 #include #include #include #include #define max 52 using namespace std; vector tree[max]; int visit[max] = {0,}; int..