그래프 검색 결과

해당 글 43건

알고리즘 풀이 - 백준 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

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

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

알고리즘 풀이 - 백준 13549(숨바꼭질3, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 0부터 100,000 중 수빈이가 걷거나 순간이동으로 매초 -1, 1, x2 만큼 움직일 수 있을 때, 동생의 위치에 도달하는 가장 빠른 시간의 경우의 시간 구하는 문제(x2 이동 시에는 0초 소요) 2. 풀이 이 문제는 이전의 문제(여기)와 비슷한데 x2로 이동 시에는 0초가 소요된다. 따라서, 이전과는 조금 다른 접근이 필요하다. 이 문제를 해결할 규칙은 다음과 같다. ① x2 이동을 하게 되는 경우가 0초가 소요되므로 + 방향으로 이동하는 다른 경우 보다는 무조건 우선해서 탐색 해야 한다. ② +1 이동..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 16. 20:02

알고리즘 풀이 - 백준 14226(이모티콘, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 이모티콘을 복사, 붙여넣기, 1개 삭제가 가능할 때, S개의 이모티콘이 화면에 나타나는데 필요한 최소 시간을 구하는 문제 2. 풀이 이모티콘이 화면에 N개가 주어지게 할 때 실행하는 연산의 최소 경우를 구하는 문제이다. 각 연산 마다 1초가 소요되므로 연산의 수는 시간과 동일하다. 이모티콘은 2가지의 경우가 있다. ① 화면에 출력된 이모티콘의 수 ② 클립보드에 복사된 이모티콘의 수 그러므로, 현재 상태값을 저장할 배열은 2차원으로 구성하여 화면 출력된 수와 복사된 이모티콘의 수를 저장하며 탐색을 수행하면 된다..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 16. 19:49