너비우선탐색
-
[백준]20005: 보스몬스터 전리품 - JAVA문제풀이/백준 2021. 7. 20. 15:59
[백준]20005: 보스몬스터 전리품 20005번: 보스몬스터 전리품 입력의 첫째 줄에는 멤멤월드의 지도의 크기를 나타내는 두 정수 M(6 ≤ M ≤ 1000), N(6 ≤ N ≤ 1000)과 플레이어의 수 P(1 ≤ P ≤ 26)가 주어진다. M은 지도의 세로 길이, N은 지도의 가로 길이이다. 입 www.acmicpc.net 풀이 🪑 입력받는 정보가 많아서 복잡해 보이지만 알고보면 구현 + BFS문제였다. 문제의 조건을 정리해 보자. 전리품은 한 번이라도 피해를 준 플레이어에게 지급된다. 최대 몇명의 플레이어가 전리품을 가져갈 수 있는지 알아낸다. 각각의 플레이어는 보스에게 최단거리로 이동하여 보스 칸에 도달하자마자 공격을 시작한다. 플레이어의 공격은 동시에 이뤄지며 같은 위치에 여러 플레이어가 위치..
-
[백준]14226: 이모티콘 - JAVA문제풀이/백준 2021. 5. 16. 14:58
[백준]14226: 이모티콘 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 풀이 걸리는 시간의 최소값을 구하는 문제 이므로 BFS 탐색을 사용하여 문제를 풀었다. BFS탐색을 하면서 조건에 맞게 1, 2, 3번을 진행하고 현재 개수가 S와 같아진다면 BFS탐색을 종료하고 현재 시간을 출력하도록 하였다. 탐색을 하면서 계속 같은 구간을 반복하지 않도록 visited 배열을 사용하였다. 각각의 인덱스가 의미하는 바는 [clipboard에 현재 복사..
-
[백준 ]5014: 스타트링크 - JAVA문제풀이/백준 2021. 3. 3. 15:08
문제 www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 S -> G로 가는 최단 경로를 찾는 문제이므로 BFS를 사용하여 풀었다. 이미 방문한 층을 다시 방문하면 최단 경로가 아니기 때문에 visited를 사용하여 다시 방문하는 일이 없도록 하였다. 또한 노드 class를 만들어 현재 층의 위치와 현재까지 몇번의 버튼을 눌렀는지 기억하도록 하였다. 이 문제에서 주의할 점이 있는데 예제 입력 1번을 잘 이해했다면 넘어가도 된다. 예를 들어, 예제 1번에서 1 -> 10..
-
알고리즘 - DFS, BFSCS/알고리즘 2021. 2. 12. 22:23
DFS, BFS DFS, BFS 그래프의 탐색 방법이다. 시간복잡도는 노드, 엣지의 개수에 영향을 받으며 DFS, BFS 동일하다. 인접 리스트로 구현시 -> O(|v|+|e|) 인접 노드로 구현시 -> O(v^2) DFS - 깊이 우선 탐색 재귀적으로 구현한다. 모든 노드를 다 탐색해야 최단 거리를 알 수 있으므로 최대 길이, 최대값 등을 찾을때 적합하다. 시작 노드로 부터 한 방향으로 계속 탐색을 진행하다가 더 이상 갈 곳이 없을때 되돌아와서 다른 방향으로 다시 탐색한다. 트리의 순회에서 중순위 탐색한 결과와 같다. 구현 with 자바 1 2 3 4 5 6 7 8 9 static void dfs(int[][] node, boolean[] memo, int num) { memo[num] = true; ..