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..

https://uknowblog.tistory.com/364 [알고리즘] 그래프 탐색 - 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 그래프 탐색 정점(Node, Vertex)과 간선(Edge)로 이루어진 그래프. 이 그래프를 탐색하는 방법에는 대표적으로 두 가지 방법이 있습니다. 깊이 우선 탐색(DFS, Depth-First Search)와 너비 우선 탐색(BFS, Bread uknowblog.tistory.com 위 DFS/BFS 글을 쓰기 위해 자료조사를 하고 있을 때 였습니다. DFS의 예시로 좋은게 뭐가 있을까 찾던 중에 한 충격적인 영상을 보게 되었습니다. https://www.youtube.com/watch?v=0kaHIfrB3T4&ab_channel=DaveStephens DFS를..

그래프 탐색 정점(Node, Vertex)과 간선(Edge)로 이루어진 그래프. 이 그래프를 탐색하는 방법에는 대표적으로 두 가지 방법이 있습니다. 깊이 우선 탐색(DFS, Depth-First Search)와 너비 우선 탐색(BFS, Breadth-First Search) 입니다. 물론 다른 그래프 탐색 알고리즘도 존재하나, 이 둘이 가장 유명한 방법이지 않을까 싶네요. 깊이 우선 탐색 (DFS, Depth - First Search) DFS는 깊이 우선이라는 이름처럼 깊이를 우선적으로 탐색합니다. 한 노드의 연결된 노드를 먼저 탐색한다는 의미죠. 해당 그래프를 DFS로 탐색한다면 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 순서로 탐색합니다. 한 노드를 탐색할 때, 해당 노드와 연결된 ..

https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net 난이도 : 골드 5 태그 : 그래프 이론, 그래프 탐색, 트리, 너비 우선 탐색, 깊이 우선 탐색 설명 가중치가 있는 그래프(트리)에서, 두 노드간 거리를 구하는 문제입니다. DFS/BFS를 사용해 그래프(트리)를 탐색하여 풀 수 있을 것 같은데요. 저는 BFS를 사용해 풀이하였습니다. 소스코드 데이터용 클래스 Node Node는 to (목표 노드), cost(목표 노드로 가는..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 난이도 : 골드 4 태그 : 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 설명 얼음을 녹이면서 덩어리가 두개가 되는 시점을 찾는 문제입니다. 얼음을 녹이는 구현 부분에 약간의 시뮬레이션 요소가 들어갔다고 볼 수 있을 것 같네요. 얼음이 몇 덩어리인지 확인하는 부분은 DFS / BFS 를 사용할 수 있을 것 같은데, 저는 DFS를 사용해 풀이하였습니다. 접근 방법 1...

https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 난이도 : 골드 3 태그 : 구현, 그래프 이론, 그래프 탐색, 너비우선탐색, 시뮬레이션, 깊이우선탐색 설명 삼성 기출 문제로 유명한 마법사 상어 시리즈 중 '마법사 상어와 파이어스톰' 문제입니다. 시뮬레이션 문제로써, 1. 파이어스톰을 n번 시전 2. 모든 파이어스톰 시전 후 가장 큰 덩어리 찾기 크게 두 파트로 나눌 수 있습니다. 파이어스톰 시전 과정은 단순 구현이지만 모든..

https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 난이도 : 실버 2 태그 : 그래프 이론, 그래프 탐색, 정렬, 깊이 우선 탐색 설명 이름 처럼 깊이 우선 탐색 (DFS, Depth First Search)의 연습문제 입니다. 그래프를 탐색하는데는 여러 방법이 있습니다. 그 중 꽤 유명한 탐색방법인 DFS를 연습해봅시다. DFS는 트리 or 그래프에서 최대한 깊이 탐색한 ..

https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 난이도 : 골드 2 태그 : 그래프 이론, 그리디 알고리즘, 그래프 탐색, 깊이 우선 탐색 설명 첫째 열에서 시작해 서로 교차하거나 중첩되지 않으면서 마지막 열로 가는 경로를 찾는 문제입니다. 1번 예제 같은 경우는 최대 두 가지 경로를 그릴 수 있습니다. 2번 예제 같은 경우는 아래와 같이 최대 5개의 경로(파이프 라인)이 있습니다. 파이프라인은 왼쪽에서 오른쪽 방향으로 놓을 수 있으며, 오른쪽 대각선 위, 오..

https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 난이도 : 골드 2 태그 : 그래프이론, 그래프탐색, 깊이 우선 탐색, 트리 설명 해당 문제 같은 경우는 DFS + Inorder(중위순회) 를 통해 구현할 수 있겠습니다. 위와 같은 노드가 있다고 가정해봤을때, 이를 인오더로 탐색하면 어떻게 될까요? 7-4-8-2-1-5-3-6-9 순으로 방문을 하게 됩니다. 즉, 좌-부모-우 순으로 탐색을 하기 때문에 좌측에 노드가 있을 경우..

https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 난이도 : 골드 2 태그 : 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 깊이 우선 탐색 설명 0,0 부터 시작하여 해당 칸에 적힌 숫자만큼 상하좌우 중 한 방향으로 이동한다 했을 때, 최대 몇 번 이동할 수 있는지 구하는 문제입니다. 단순히, DFS로 가장 깊은 depth가 어디인지 확인하면 될 것 같았습니다. 네. 아니였습니다. 시간초과가 나버렸으니 시간을 단축시킬 수 있는 테크닉이 필..