알고리즘 풀이(Problem Solving)/그래프, 트리 검색 결과

해당 글 42건

알고리즘 풀이 - 백준 16948(데스 나이트, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 체스의 데스 나이트를 새로 만들어서 이동이 가능할 때, NxN 체스판에서 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 횟수를 구하는 문제 2. 풀이 제일 간단한 수준의 BFS 문제이다. 각 이동 가능한 경우를 배열로 저장하고 이동 가능한 경우 이동시키면서 각 위치에 최소 이동 횟수를 저장하고 목표 지점에 도달하면 탐색을 중지하면 되는 문제이다. 쉬운 문제이므로 코드를 통해 이해하자. 3. 코드 아래의 코드를 통해 정답을 알아보자. import java.io.*; import java.ut..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 28. 20:16

알고리즘 풀이 - 백준 16928(뱀과 사다리 게임, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 주사위를 굴려 1에서 100번째 위치로 최소한의 이동으로 이동하는 횟수를 구하는 문제(사다리, 뱀에 의해 위치는 조정될 수 있음) 2. 풀이 BFS를 통해 최소 이동 횟수를 구하는 문제이다. 초반에는 (0, 1)을 탐색 완료로 표시하고 주사위를 굴려서 1~6까지 Position 값을 더해서 구한 뒤 해당 위치에 맞는 index 값을 계산하여 탐색을 수행하면 된다. 게임판 크기가 10x10이므로 간단하게 index를 구할 수 있다. 예를 들어 72번 위치라면 행(y) 번호의 index는 72를 10으로 나눈 몫..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 28. 20:14

알고리즘 풀이 - 백준 1967(트리의 지름, 트리/그래프(DFS))

관련글 트리 관련 포스팅은 여기를 참조 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 트리의 지름을 구하는 문제 2. 풀이 트리의 지름 : 현재 트리 상의 모든 노드 간의 거리 중 가장 그 거리가 긴 것을 의미 트리의 지름을 찾는 방법은 간단하다. 특정 노드에서 가장 멀리 위치한 노드를 찾고 해당 노드에서 다시 가장 멀리 위치한 노드를 찾으면 지름을 구할 수 있다. 즉, 특정 하나의 노드에서 가장 먼 정점을 BFS 또는 DFS로 찾고 해당 가장 먼 노드에서 다시 BFS 또는 DFS를 통해 가장 멀리 위치한 노드를 찾아서 그 거리를 구하면 되는 문제이다. 3. 코..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 17. 22:25

알고리즘 풀이 - 백준 1167(트리의 지름, 트리/그래프(DFS))

관련글 트리 관련 포스팅은 여기를 참조 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 트리의 지름을 구하는 문제 2. 풀이 트리의 지름 : 현재 트리 상의 모든 노드 간의 거리 중 가장 그 거리가 긴 것을 의미 트리의 지름을 찾는 방법은 간단하다. 특정 노드에서 가장 멀리 위치한 노드를 찾고 해당 노드에서 다시 가장 멀리 위치한 노드를 찾으면 지름을 구할 수 있다. 즉, 특정 하나의 노드에서 가장 먼 정점을 BFS 또는 DFS로 찾고 해당 가장 먼 노드에서 다시 BFS 또는 DFS를 통해 가장 멀리 위치한 노드를 찾아서 그 거리를 구하면 되는 문제이다. 3. 코..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 17. 22:24

알고리즘 풀이 - 백준 11725(트리의 부모 찾기, 트리/그래프(BFS, DFS))

관련글 트리 관련 포스팅은 여기를 참조 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 루트 없는 트리의 구조가 주어졌고 1이 루트라고 지정되었을 때, 각 노드의 부모를 구하는 프로그램 작성하기 2. 풀이 이 문제는 단순히 트리를 그래프 형태로 구현한 뒤, BFS / DFS를 통해 탐색을 수행하며 각각의 노드의 부모 노드를 지정하여 그 결과를 출력하는 문제이다. 코드를 통해 간단히 이해할 수 있다. 3. 코드 아래의 코드를 통해 정답을 알아보자. ① BFS로 풀기 import java.io.BufferedReader; import java.io.InputStrea..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 17. 22:15

알고리즘 풀이 - 백준 2250(트리의 높이와 너비, 트리)

관련글 트리 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 트리의 너비 중 가장 넓은 너비와 해당 너비를 갖는 레벨을 구하는 문제 2. 풀이 이 문제는 트리를 우선 구성하고 중위 순회를 통해 좌측 부터 하나씩 위치를 채워나가는 문제이다. 위치를 채워나가고 나면 각 층위(level)에서의 간격의 최대 / 최소값을 구한 뒤 그 차이가 가장 큰 레벨과 그 간격을 구하여 출력하면 되는 문제이다. 자세한 내용은 코드를 통해 확인하자 3. 코드 아래의 코드를 통해 정답을 알아보자. import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; ..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 17. 22:10

알고리즘 풀이 - 백준 1991(트리 순회, 트리)

관련글 트리 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 이진 트리를 전위, 중위, 후위 순회하는 결과를 출력하는 문제 2. 풀이 이진 트리를 Class 형태로 구성하여 각 정점을 연결시킨 후, 트리의 순회 방식에 따라 각각 순회하여 그 결과를 나타내는 문제이다. 각각의 노드 정보는 알파벳이 기준이므로 그 index를 활용하여 배열로 저장하였다. 기초 문제이므로 별도의 설명은 없고 트리에 대한 내용은 상단의 링크를 통해 확인하자. 3. 코드 아래의 코드를 통해 정답을 알아보자. import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOExcept..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 17. 21:49

알고리즘 풀이 - 백준 1261(알고스팟, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 NxM 크기의 미로에 (1, 1) → (N, M)으로 이동하고자 한다면 벽을 최소 몇 개를 부셔야 하는지 구하는 문제 2. 풀이 이 문제는 NxM 크기의 미로에 벽과 벽이 아닌 곳이 있으므로 각 위치를 그래프 형태로 탐색만 수행하면 된다. 탐색은 최소의 경우를 구하는 문제이므로 BFS로 탐색을 수행한다. 하지만 벽으로 연결되지 않은 부분 부터 모두 탐색을 완료하고 벽이 있는 부분을 탐색 해야 한다. 왜냐하면, 아래와 같은 예외 상황이 있을 수 있기 때문이다. 위와 같이 빨간색으로 이동 시에는 벽을 3개를 부수..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 16. 20:31