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

문제 이해N개의 정점, M개의 간선으로 구성된 무방향 그래프모든 간선의 가중치는 1이다.인접 정점은 오름차순으로 방문한다.한 줄마다 입력된 u v 정점은 양방향 간선을 가진다.첫 번째 u v 입력을 보면, 정점 1은 정점 4를 방문할 수 있고, 정점 4 또한 정점 1을 방문할 수 있다. 예제 입력을 그림과 표로 나타내보자.시작 정점방문할 수 있는 정점12, 421, 3, 432, 441, 2, 350시작 정점들에 대한 인접 리스트를 만들고, 각 정점이 방문할 수 있는 정점 번호들을 리스트에 넣는다.정점 번호가 작은 순서대로 탐색하기 위해 리스트 안의 정점들을 오름차순으로 정렬한다.그리고 시작 정점(r)에서부터 DFS를 수행하여 방문 순서를 기록한다.import java.io.IOException;impo..

문제 이해n명의 사람이 입국 심사를 위해 대기 중입국 심사대는 여러 개가 있고, 각 심사관마다 한 명을 처리하는 데 걸리는 시간이 다르다.모든 사람이 심사를 마치고 입국하는 데 걸리는 최소 시간을 구해야 한다.핵심은 특정 시간 동안 몇 명의 사람이 심사받을 수 있는지 계산하며 시간을 좁혀가야 한다. 그렇다면 특정 시간은 어떻게 지정해야 할까. 각 심사관이 한 명을 심사하는 데 걸리는시간은 1 가장 느림 심사관이 모든 인원을 처리하는 경우를 최대 시간으로 잡는다면 (1,000,000,000 * n명) 시간이 된다. 이분탐색을 활용하여 중간시간을 계산하고, 그 시간 동안 각 심사관이 몇 명을 처리할 수 있는지 계산해야 해 보자.처리 가능한 인원수(totalPeople)가 n명 이상이면 시간을 줄이고, n명 ..

문제의 핵심은 2가지로 생각했다.두 번째 점프부터는 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야만 한다.N번 징검 다리는 반드시 밟아야 한다.   생각만 했지 손도 못댔다.노트에 징검다리 그림까지 그려가며 풀어봤지만 코드 한 줄 적지 못했다.작은 수부터 그림을 그려가며 규칙성을 파악하고자 했다.Nresult1, 213, 4, 526, 7, 8, 9310, 11, 12, 13, 144뭐하는건가 싶었다. 결국 검색의 도움을 받았다.등차수열연속하는 두 항의 차이가 모두 일정한 수열을 뜻한다.이때 두 항의 차이는 이 수열의 모든 연속하는 두 항들에 대해서 공통으로 나타나는 차이므로, 공차라고 한다.- 위키백과 왜 등차수열이 나왔을까.문제 조건 중, 이전 점프한 거리보다 1 이상 더 긴 거리를 뛰어야 한..