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

해당 글 42건

알고리즘 풀이 - 백준 16929(Two Dots, 그래프(DFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 문제 설명은 위의 더보기를 클릭 2. 풀이 이 문제는 단순한 DFS 문제임에도 엄청 많이 틀렸다. 알고 보니 "Yes"라고 출력해야 하는데 "YES"로 출력하고 있어서 틀렸다.. 부디 다른 분들은 이런 실수 하지 않기를 바라며... 이 문제는 같은 색상으로 이루어진 정점을 4개 이상 탐색하였을 때, Cycle이 발생하면 "Yes"를 출력하고 아니면 "No"를 출력한다. 우선 Cycle을 찾아내기 위해서는 기존에 이미 방문된 정점을 다시 한 번 방문하는 절차가 필요하다. 즉, DFS를 탐색을 수행하며 현재 탐색..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 3. 21:17

알고리즘 풀이 - 백준 7562(나이트의 이동, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 IxI 크기의 체스판 위 특정 위치에 나이트가 있을 때, 나이트가 이동하여 주어진 위치로 최소의 경우로 이동할 수 있는 움직임의 수를 구하는 문제 2. 풀이 이 문제는 나이트가 이동하며 특정 위치로 도달하기 위한 최소 이동 경로를 찾는 문제이다. 최소 이동 경로를 찾을 때는 DFS를 통해서 수행하면 최소의 경우를 보장할 수 없어 BFS 탐색을 통해 문제를 해결해보자. BFS 탐색은 모든 인접 정점을 최소 이동 횟수로 보장해주는 탐색 방식이다. 현재 정점 위치를 저장하고 그 위치에서 8개의 방향으로 이동하며 목..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 1. 22:53

알고리즘 풀이 - 백준 7576(토마토, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 NxM 크기의 창고에 토마토를 보관 시, 익은 토마토의 인접 토마토는 1일 후 익을 때, 모든 토마토가 익는데 걸리는 일 수를 구하는 문제 2. 풀이 익은 토마토와 인접한 토마토가 익는 다는 것을 이용하여 인접한 정점을 탐색해나가는 그래프 탐색 문제이다. 이 문제는 익어 있는 상태의 토마토를 모두 미리 저장하고 주변의 토마토를 익혀가며 탐색을 수행해야 한다. 그러므로 인접한 것들을 탐색해가며 범위를 넓혀야 하므로 BFS 방식의 탐색을 수행해야 한다. 우선 미리 현재 익은 상태인 위치의 토마토를 Queue 자료..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 1. 22:45

알고리즘 풀이 - 백준 2178(미로 탐색, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 NxM크기의 미로가 주어질 때, 1은 이동 가능하고 0은 불가하다면 (1, 1) 에서 (N, M)으로 이동 시 지나야 하는 최소의 칸 수를 구하는 문제 2. 풀이 이 문제는 NxM 크기의 지도가 하나의 미로로 주어진다. (1, 1)에서 (Index라면 0, 0) 이동을 시작하여 주어진 값 (N, M)으로 이동해야 하되 최소로 이동하는 경우를 구한다. 그러므로 현재 위치에서 부터 탐색을 시작하여 각 위치를 최소로 이동할 수 있는 경우를 찾은 뒤 결국 마지막에 원하는 장소에 도달했을 때, 그 이동 횟수를 반환하면..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 1. 21:21

알고리즘 풀이 - 백준 4963(섬의 개수, 그래프(DFS, BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 지도에 섬, 바다가 표시되어 있을 때, 섬의 개수를 구하는 문제. 같은 섬의 기준은 상하좌우대각선으로 연결된 경우 2. 풀이 h x w 크기의 지도가 주어질 때, 1로 표시된 곳은 섬이고 0으로 표시된 곳은 바다이다. 그러므로 현재 탐색 위치의 인접한 섬을 모두 찾아낸다면 그것이 하나의 큰 섬이 된다. 인접한 섬을 찾아낼 수 있는 자료구조는 그래프이다. 인접 행렬로 지도를 저장하고 각각의 위치에서 탐색을 시작하여 이어진 섬 전체의 개수를 찾아내면 된다. 그래프를 탐색해야 하므로 DFS, BFS의 구조를 통해 ..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 1. 20:52

알고리즘 풀이 - 백준 2667(단지번호붙이기, 그래프(DFS, BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 정사각형 모양의 지도에 1은 집이 있고 0은 없는 곳이다. 좌우 / 상하로 이어진 경우에 연결된 모든 집들은 하나의 단지라고 할 때, 각 단지에 있는 집의 수를 오름차순으로 정렬하여 출력하는 문제 2. 풀이 이 문제는 인접한 모든 아파트를 찾아서 하나의 단지로 묶어내야 하는 문제이다. 따라서, 주어진 값이 하나의 행렬 형태로 주어지므로 인접 행렬로 정보를 저장한 뒤 서로 인접한 모든 정점을 찾아 그 개수를 저장한다. 정점을 찾을 때는 DFS 또는 BFS를 이용하여 그래프 탐색을 수행하면 된다. 각 위치에서 탐..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 2. 27. 23:02

알고리즘 풀이 - 백준 1707(이분 그래프, 그래프(DFS, BFS))

관련글 그래프 관련 포스팅은 여기를 참조 이분 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 그래프가 이분 그래프인지 여부를 판별하는 문제 2. 풀이 이분 그래프는 아래와 같이 2 그룹으로 나누었을 때, 같은 그룹은 서로 인접하지 않아야 한다. 위의 그림과 같이 빨간 그룹과 파란 그룹이 있는데 같은 그룹은 인접하여 연결되지 않았다. 이런 경우 이분 그래프라고 할 수 있다. 이를 구하는 방법은 그래프를 탐색하며 인접한 정점들이 같은 속성(보통 색깔로 표현)을 가지지 않는지를 검사하면 된다. 기본적으로 탐색을 수행하면서 현재 탐색 중인 정점의 색상을 지정하고, 그것..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 2. 27. 11:40

알고리즘 풀이 - 백준 11724(연결 요소의 개수, 그래프(DFS, BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 그래프 구조에서 연결 요소의 개수를 구하는 문제 2. 풀이 연결 요소란 그래프 상에서 이어져 있는 모든 정점들이 있을 때, 그것을 하나의 연결 요소라고 한다. 예를 들어 아래의 그림을 보자. 위 그래프에서 1, 2, 4는 하나의 연결된 그래프이므로 1개의 연결 요소 이고 3, 5도 하나의 연결된 그래프라서 1개의 연결 요소 이다. 즉, 위 그림에서 연결 요소의 개수는 2개가 되는 것이다. 따라서, DFS, BFS로 2가지 중 1가지의 방법을 사용하여 그래프 탐색을 시도한 뒤 연결 요소의 개수를 구하는 코드를 ..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 2. 27. 11:39