코딩 일지

문제 출처https://www.acmicpc.net/problem/2606실버3 유니온 파인드 또는 dfs 문제이다. dfs로 푸는 풀이는 경우가 많지만,이 문제와 같은 경우는 1번 컴퓨터와 연결되어있는지 안되어있는지만 확인하면 되는 문제이므로유니온 파인드를 이용한 풀이도 가능하다.유니온 파인드에 관한 해설은 아래 링크를 참고하면 된다.https://codingul1234.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C-Union-Find [알고리즘] 유니온 파인드 (Union-Find)유니온 파인드유니온 파인드 (Union-Find)란, 합 집합을 만드는..

문제 출처https://www.acmicpc.net/problem/16236 골드3 BFS, 우선순위 큐 문제이다. 상당히 재밌게 푼 bfs 문제이다.shark 구조체에 아기 상어 위치의 행과 열, 그리고 먹은 물고기의 개수, 크기, 움직인 횟수, 그리고 우선순위 큐에서 움직인 횟수, 행의 크기, 열의 크기 순으로 오름차순으로 정렬할 연산자 오버로딩까지 정의해준다.struct shark{ int row; int col; int eatFishCnt; int size; int cnt; bool operator s.col; } return row > s.row; } return cnt > s.cnt; }};..

문제 출처https://www.acmicpc.net/problem/1167 1167번: 트리의 지름트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지www.acmicpc.net골드 2 트리 문제이다. 임의의 두 점 사이의 거리 중 가장 긴 것을 찾으면 되기에 dfs를 사용했다. 정점 1에서 탐색을 했을 때 가장 길이가 긴 정점은 11을 갖는 5이다.정점 2에서 탐색을 했을 때 가장 길이가 긴 정점은 10을 갖는 5이다. 내가 정점 1을 기준으로 가장 긴 길이를 찾아내도록 풀었다면 위 예제는 문제없이 11이라는 답이 제대로 나오지만정점 2를 기준으로 ..

문제 출처https://www.acmicpc.net/problem/1043 1043번: 거짓말지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게www.acmicpc.net골드 4 유니온 파인드 문제이다. 예제 6를 봐보자진실을 아는 사람1, 2 ,71파티3, 42파티53파티5, 64파티6, 85파티8 i12345678parent12345678 parent 배열에 유니온 파인드를 사용하면i12345678parent12335575이 된다.이 상태에서 1파티부터 5파티까지 다시 탐색하며 진실을 아는 사람과 연결되어 있는 사람을 골라 제외하면 된다.   #풀이#include #..