https://www.acmicpc.net/problem/13905 13905번: 세부 첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄 www.acmicpc.net 난이도 : 골드 4 태그 : 자료 구조, 그래프 이론, 그래프 탐색, 분리 집합, 최소 스패닝 트리 설명 한 섬에서 다른 섬으로 가지만, 다리(간선)가 버틸 수 있는 문제가 한정되어 있어, 가중치의 최솟값이 최대가 되야 합니다. 가중치의 최솟값이 최대가 되야 한다... 이게 무슨 말인가 싶긴 하지만, 위 그래프를 예시로 들 때, 1번 집에서 5번 집으로 가..

https://www.acmicpc.net/problem/14868 14868번: 문명 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 세계의 크기를 나타내는 정수 N(2 ≤ N ≤ 2,000)과 문명 발상지의 수 K(2 ≤ K ≤ 100,000)가 주어진다. 다음 K줄에는 한 줄에 하나씩 문명 발상지 www.acmicpc.net 난이도 : 플래티넘 4 태그 : 자료 구조, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 분리 집합 설명 문명은 인접한 칸으로 세력을 넓힙니다. 세력을 넓히면서 한 칸을 서로 차지하려 할 때 혹은 서로 맞닿을 때 두 문명은 합쳐집니다. 한 칸을 서로 차지하려 할 때는 BFS 탐색 중 쉽게 알 수 있으나, 인접할 경우에는 4방향 BFS를 한 번 더 돌려 확인할 수 있습니다..

https://www.acmicpc.net/problem/17114 17114번: 하이퍼 토마토 첫 줄에는 문제의 설명에서 창고의 크기를 나타내는 자연수 m, n, o, p, q, r, s, t, u, v, w가 주어진다. 단, 1 ≤ mnopqrstuvw ≤ 106 이다. 둘째 줄부터는 창고에 저장된 토마토들의 정보가 주어진다. 창 www.acmicpc.net 난이도 : 골드 1 태그 : 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색 설명 2차원이였던 7576 토마토와 https://uknowblog.tistory.com/30 [백준 7576번] [Kotlin] 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 ..

https://www.acmicpc.net/problem/1944 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 난이도 : 골드 1 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 최소 스패닝 트리 설명 문제를 보고, BFS로 각 키-키, 로봇-키의 최단거리를 얻어야겠다는 생각은 빨리 떠올랐는데, 최소 이동거리를 어떻게 구해야 하나 고민을 좀 했던 문제였습니다. 결국 태그를 슬며시 눌러봤는데, '최소 스패닝 트리' 키워드를 보고 아 맞네...!를 외쳤습니다...ㅎㅎ.....

https://www.acmicpc.net/problem/17270 17270번: 연예인은 힘들어 첫 번째 줄에는 약속 장소 후보의 수 V와 약속 장소를 연결하는 총 길의 수 M이 주어진다. (2 ≤ V ≤ 100, 1 ≤ M ≤ 1,000) 그리고 다음 M개의 각 줄에는 a, b, c 가 주어진다. a, b는 길의 시작과 끝이 www.acmicpc.net 난이도 : 골드 3 태그 : 구현, 그래프 이론, 데이크스트라, 플로이드–워셜 설명 다익스트라 혹은 플로이드 워셜을 응용해 풀 수 있는 문제입니다. 계속 틀렸습니다를 받아서 질문게시판을 들여다봤는데, 아니나 다를까 지문이 불친절하다는 의견이 잔뜩 있었습니다... 질문게시판들을 둘러보며 지문을 몇 번이고 다시 읽어봤는데, 해당 조건을 하나씩 적용하면서 ..

https://www.acmicpc.net/problem/24484 24484번: 알고리즘 수업 - 깊이 우선 탐색 6 정점 1번에서 정점 4번을 방문한다. 정점 4번에서 정점 3번을 방문한다. 정점 3번에서 정점 2번을 방문한다. 정점 5번은 정점 1번에서 방문할 수 없다. 따라서, ti 값은 1번 정점부터 1, 4, 3, 2, 0이다 www.acmicpc.net 난이도 : 실버 2 태그 : 깊이 우선 탐색, 정렬, 그래프 탐색, 그래프 이론 설명 깊이 우선 탐색 1-2번 + 3-4번을 합친 형태면서, 깊이 우선 탐색 5번의 내림차순 방문 버전입니다. 1~5번을 푸신 분들이라면 별로 어렵지 않게 푸실 수 있을 문제입니다. 1번 노드 2번 노드 3번 노드 4번 노드 5번 노드 6번 노드 순서 1 4 2 ..

https://www.acmicpc.net/problem/24483 24483번: 알고리즘 수업 - 깊이 우선 탐색 5 정점 1번에서 정점 2번을 방문한다. 정점 2번에서 정점 3번을 방문한다. 정점 3번에서 정점 4번을 방문한다. 정점 5번은 정점 1번에서 방문할 수 없다. 따라서, ti 값은 1번 정점부터 1, 2, 3, 4, 0이다 www.acmicpc.net 난이도 : 실버 2 태그 : 그래프 이론, 그래프 탐색, 정렬, 깊이 우선 탐색 설명 깊이 우선 탐색 1번 + 3번이라고 볼 수 있습니다. 방문 순서를 체크하는 1번과 깊이를 체크하는 3번을 잘 풀었다면 쉽게 푸실 수 있을 겁니다. 개념 자체는 1-2번, 3-4번과 동일합니다. 오름차순으로 방문할 경우, 방문 순서는 1 -> 2 -> 4 ->..

https://www.acmicpc.net/problem/24482 24482번: 알고리즘 수업 - 깊이 우선 탐색 4 깊이 우선 탐색 트리는 1, 2, 3, 4번 노드로 구성된다. 1번 노드가 루트이다. 1번 노드의 자식은 4번 노드이다. 4번 노드의 자식은 3번 노드이다. 3번 노드의 자식은 2번 노드이다. 5번 노드는 1번 노드 www.acmicpc.net 난이도 : 실버 2 태그 : 그래프 이론, 그래프 탐색, 정렬, 깊이 우선 탐색 설명 트리의 경우, 탐색의 방문 순서에 관계없이 동일한 깊이를 가지겠지만, 문제에서 주어지는 그래프는 사이클이 있을 수 있는 그래프이기 때문에, 깊이 우선 탐색으로 탐색할 경우 탐색 순서(번호가 작은 노드부터 / 번호가 큰 노드부터)에 따라 각 노드의 깊이가 달라질 ..

https://www.acmicpc.net/problem/24481 24481번: 알고리즘 수업 - 깊이 우선 탐색 3 깊이 우선 탐색 트리는 1, 2, 3, 4번 노드로 구성된다. 1번 노드가 루트이다. 1번 노드의 자식은 2번 노드이다. 2번 노드의 자식은 3번 노드이다. 3번 노드의 자식은 4번 노드이다. 5번 노드는 1번 노드 www.acmicpc.net 난이도 : 실버 2 태그 : 그래프 이론, 그래프 탐색, 정렬, 깊이 우선 탐색 설명 깊이우선탐색 1, 2번이 몇 번째로 방문했는지를 출력하는 것이라면, 깊이우선탐색 3, 4번은 깊이(depth)를 출력하는 문제입니다. 트리의 경우, 탐색 순서가 어떻든간에 각 노드의 깊이는 모두 동일하겠지만, 해당 문제는 사이클이 존재할 수 있는 그래프에서의 D..

https://www.acmicpc.net/problem/24480 24480번: 알고리즘 수업 - 깊이 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 난이도 : 실버 2 태그 : 그래프 이론, 그래프 탐색, 정렬, 깊이 우선 탐색 설명 알고리즘 수업 - 깊이 우선 탐색 1과 비슷한 문제입니다. https://uknowblog.tistory.com/323 [백준 24479번] [Kotlin] 알고리즘 수업 - 깊이 우선 탐색 1 https://www.acmicpc.net/p..