'앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.'이 부분을 보고 부모 번호에서부터 시작되는 단방향 그래프로 생각했다.그 생각에서 1시간을 넘게 벗어나지 못했다. 그리고 탐색은 무조건 1에서부터 시작해야한다는 고정관념이 있었다.실제 촌수 계산할 때, 자신(나)부터 거슬러올라가면서 계산한다.그래프 탐색 알고리즘 사용만을 생각하고, 문제와 상관없이 형식적으로 알고리즘을 사용했던 것 같다. DFS 풀이예제에서 촌수 계산을 해야하는 사람인 7번과 3번을 기준으로 계산해야 한다.단방향이 아닌 양방향 그래프를 그린다.7번부터 시작하여 3번까지 탐색한다. depth가 깊어질 때마다 count를 줘야 한다. import java.util.ArrayList;import java.util.Scanne..

단어가 만들어지는 규칙이 이해가 안됐지만 계속 보다보니 dfs 순서로 만들어지고 있다는 것을 알게 되었다.풀이주어진 A, E, I, O, U 사용하여 dfs 순서대로 단어를 생성한다. 생성된 단어들을 dictionary라는 리스트 자료구조에 저장한다.생성된 단어의 길이가 5를 넘는다면 상단에서 Early return으로 스택 프레임에 쌓인 함수를 종료시킨다.단어 생성 재귀 함수import java.util.ArrayList;import java.util.List;public class Solution { private static final String[] ALPHABETS = {"A", "E", "I", "O", "U"}; private static final List DICTIONARY =..

문제이해N개의 나무가 주어지며, 나무들의 높이는 0 최소 M미터의 나무를 가져가기 위해 설정할 수 있는 절단기의 최대 높이(H)를 구하라.최대값, 나무의 길이 제한, 나무의 높이 제한.3가지 키워드를 통해 이분탐색 문제인 것을 알 수 있다. 풀이이분탐색을 활용하여 특정 높이(H)를 구한다.주어진 나무들의 각 높이에서 특정 높이를 뺀 값을 모두 더한다(totalHeight).만약 특정 높이가 더 높다면 연산하지 않는다.계산된 값과 m을 비교하고 범위를 좁혀가며, 결과값을 찾는다.실패1public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextIn..

BFS루트 노드 또는 임의의 노드에서 시작하여 인접한노드를 먼저 탐색하는 방법.시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.깊게 탐색하기 전에 넓게 탐색하는 것.정점 A 에 인접한 정점 중 방문하지 않은 정점 B와 C가 있다면B,C 를 모두 방문하고 방문한 순서대로 큐에 저장한다.그리고 가장 먼저 저장된 정점 B를 가져와 B의 인접 정점을 탐색하여 방문한다.큐에 저장된 정점이 없을 때까지 위 과정을 반복한다. 스택 프레임을 쌓는 DFS와 달리, 큐를 사용해 메모리를 보다 효율적으로 사용한다.4일차의 DFS 문제에 이어 BFS 문제이다.그래프 초기화, 간선 입력 등의 코드는 모두 동일하고, dfs 메서드만 변경해주면 될 것 같다.실패static v..