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

해당 글 42건

알고리즘 풀이 - 프로그래머스(카카오프렌즈 컬러링북(Lv 2), BFS)

관련글 그래프 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 여러 장의 그림을 난이도 순으로 컬러링 북에 넣을 때, 난이도를 영역의 수로 정하였다면 그림의 영역의 수와 가장 큰 영역의 넓이가 얼마인지 계산하는 문제 2. 풀이 예시로 주어진 그림의 영역의 수 및 넓이를 알아보자. (영역은 숫자가 0이면 칠해지지 않은 것이며, 나머지는 그려진 것이다.) 위에서 색칠된 부분만 그림이므로, 영역은 총 4개이고 그 중 넓이가 가장 넓은 것은 5임을 알 수 있다. BFS를 통해 인접 같은 숫자 그림을 칠하고, 그 영역을 계산하는 방식으로 해결하는 간단한 문제이다. 3. 코드 아래의 코드를 통해 정답을 알아보자. ..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 7. 11. 14:07

알고리즘 풀이 - 프로그래머스(거리두기 확인하기(Lv 2), BFS)

관련글 그래프 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 코로나 바이러스 예방을 위해 면접 대기실에서는 거리두기를 지켜야 하는데, 이 때, 각 면접실의 대기실 지원자들이 거리두기를 유지하였는지를 판단하는 문제 (맨해튼 거리가 2이하인 거리에 붙어 앉으면 거리 두기 위반이지만, 그 사이에 파티션으로 구분되면 거리 두기를 지킨 것) 2. 풀이 거리두기를 지켰는지 주변 대기자들과의 거리를 재고 그 거리가 적절한지를 판단하는 문제이다. 즉, 그래프 자료구조를 통해서 각 대기실의 면접자를 정점으로 인식한다면 그 거리를 간선으로 이해하고 상호 간의 거리를 측정하여 계산하면 된다. 거리두기의 규칙은 다음과 같다..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 7. 11. 12:33

알고리즘 풀이 - 백준 14395(4연산, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 4개의 연산으로 A → B로 변환 가능한 최소의 연산의 경우를 사전 순으로 가장 앞서는 1개만 출력하는 문제 2. 풀이 각 연산은 다음과 같다. ① * 연산 : S = S*S ② + 연산 : S = S + S = 2xS ③ - 연산 : S = S - S = 0 ④ / 연산 : S = S / S = 1 여기서 처음에 단순 BFS로 모든 숫자를 탐색하여 가능한 연산 중 가장 적은 방식으로 연산하는 경우를 찾고자 할 수 있다. 그러나 다시 문제를 보면 최대 탐색 가능 숫자가 $10^9$이다. 즉, 10억이다.. 그..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 4. 6. 23:05

알고리즘 풀이 - 백준 10026(적록색약, 그래프(BFS, DFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 NxN크기의 그리드에 색상이 표시되어 있을 때, 적록색약의 경우와 일반인의 경우에 구분 가능한 색상 구역의 개수를 구하는 문제 2. 풀이 가장 기초적인 수준의 그래프 탐색 문제이다. 일반인의 경우와 적록색약인 경우에 그리드를 별도로 저장하여 각각 BFS를 수행한 뒤 구역의 개수를 구하는 방식으로 문제를 해결하였다. 3. 코드 아래의 코드를 통해 정답을 알아보자. ① BFS로 풀기 import java.io.*; import java.util.*; public class Main{ static int n; st..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 4. 6. 22:54

알고리즘 풀이 - 백준 1963(소수 경로, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 소수 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 4자리의 비밀번호를 A → B로 바꾸고 싶을 때, 4자리 중 1자리만 바꿀 수 있는 경우, 그 1자리를 바꿀 때도 전체 값이 소수가 되는 경우만 가능할 때, 몇 번의 변경으로 비밀번호를 바꿀 수 있는지 확인하는 문제 2. 풀이 소수를 구하는 문제 관련 포스팅은 이미 이전에 진행한 적 있다. 상단의 링크를 참조 여기서는 가장 빠른 에라토스테네스의 체를 이용하여 1000~9999까지 모든 소수를 미리 구하고 시작하였다. 그리고 1, 10, 100, 1000의 자리의 모든 숫자를 1..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 4. 6. 22:47

알고리즘 풀이 - 백준 6087(레이저 통신, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 레이저를 발사하여 두 위치를 연결 시키는 경우, 레이저가 거울을 만나면 90도 반사될 수 있을 때, 최소의 거울을 위치하여 연결하는 경우를 찾는 문제 2. 풀이 A → B 위치로 이동할 때, 꺾이는 부분이 최소가 되도록 연결하는 문제이다. BFS를 통해 현재 위치에서 목표 위치로 이동 가능한 모든 경우를 체크하여 각 위치에 거울을 놓을 필요가 있는지를 체크하면 된다. 거울을 놓을 필요가 있는 경우는 방향 전환이 발생하는 경우이다.(어떤 방향이든 이전 노드를 탐색 시에 이동한 방향과 다르다면 방향 전환이 있는 ..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 4. 6. 22:38

알고리즘 풀이 - 백준 16236(아기 상어, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 아기 상어가 자신보다 작은 물고기를 먹으며 커갈 수 있을 때, 엄마 상어의 도움이 없이 물고기를 찾아 먹으러 다닐 수 있는 최대의 시간을 구하는 문제 2. 풀이 이 문제는 여러번의 BFS를 통해 해결하는 문제이다. 해결 방법은 다음과 같다. ① 현재 남은 물고기의 위치 중 가장 가까운 위치의 물고기를 찾는다. → 해당 물고기들 중 가장 좌측 상단에 있는 물고기를 찾는다. ② 해당 물고기를 먹기 위해 위치로 이동한다. ③ 현재 까지 먹은 물고기의 수가 현재 상어의 크기와 같다면 상어의 크기를 +1 해준다. ④ ..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 4. 6. 22:27

알고리즘 풀이 - 백준 3055(탈출, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 고슴도치가 비버의 굴로 물 / 바위의 견제 없이 이동 가능한 경우 최소의 경우로 이동하는 횟수를 구하는 문제 2. 풀이 이 문제는 BFS를 통해 푸는 문제이다. 다만, 그동안에는 현재 위치에서 이동 가능한 구역을 찾아가며 알고리즘을 수행하였는데, 이 문제는 두더지가 이동 가능한 구역을 찾기 전에 물 또한 흐르므로 이동시켜야 한다. 즉, BFS 통해 먼저 물을 이동시켜 물이 차지할 위치를 찾은 뒤, 다음 BFS 로직을 이용하여 고슴도치를 이동시키는 것이다. 즉, 물의 현재 탐색 위치를 저장할 Queue와 고슴도..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 4. 6. 22:15