Algorithm/DFS & BFS5 [Algorithm] BFS-2 import java.awt.Point; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class BfsIceCream { // 결과적으로 이 코드는 아이스크림 재료를 부을 수 있는 칸 0이 나오면 카운트를 증가하고, // 그곳의 상하좌우, 그 상하좌우의 또 상하좌우들을 전부 1로 만들어줘서 0으로부터 아이스크림이 생성될 수 있는 모든 곳을 1로 바꿔주는 코드이다. // 즉 0이 있다면 1로 만들고 카운트 증가 & 거기서부터 아이스크림이 만들어질 수 있는 모든 공간 1로 변경 // 더이상 1로 바꿀 것이 없다면 다음 칸에서 다시 0인지 체크 static int n = 0; static int m =.. 2022. 11. 26. [Algorithm] DFS-2 import java.util.Scanner; public class DfsIceCream { // 결과적으로 이 코드는 아이스크림 재료를 부을 수 있는 칸 0이 나오면 카운트를 증가하고, // 그곳의 상하좌우, 그 상하좌우의 또 상하좌우들을 전부 1로 만들어줘서 0으로부터 아이스크림이 생성될 수 있는 모든 곳을 1로 바꿔주는 코드이다. // 즉 0이 있다면 1로 만들고 카운트 증가 & 거기서부터 아이스크림이 만들어질 수 있는 모든 공간 1로 변경 // 더이상 1로 바꿀 것이 없다면 다음 칸에서 다시 0인지 체크 static int n = 0; static int m = 0; static String str = ""; static int[][] arr = new int[1000][1000]; public.. 2022. 11. 26. [Algorithm] BFS-1 import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; public class BreadthFirstSearch { // BFS // [BFS 알고리즘] 큐 사용 // peek() : Queue에 맨 앞에 있는 데이터를 가져온다 (Queue에서 꺼내진 않음) // poll() : Queue에 맨 앞에 있는 데이터 꺼낸다 // offer() : Stack에 데이터를 삽입 // (6)--(2)--(1)--(3)--(5) // | / | \ // (8) (4)--(7) public static boolean[] visited = new boolean[9]; public static ArrayList graph = new .. 2022. 11. 26. [Algorithm] DFS-1 import java.util.ArrayList; public class DepthFirstSearch { // DFS // [DFS 알고리즘] 스택 사용 // peek() : Stack 최상단에 있는 top data 반환한다(Stack에서 꺼내진 않음) // pop() : Stack에 있는 데이터 꺼낸다 // push() : Stack에 데이터를 삽입한다 // isEmpty() : Stack 비어있는지 확인한다 // empty() : Stack을 초기화한다 // size() : Stack Size를 반환한다 // (6)--(2)--(1)--(3)--(5) // | / | \ // (8) (4)--(7) public static boolean[] visited = new boolean[9]; public.. 2022. 11. 26. [Algorithm] DFS & BFS 이해하기 DFS : 한 드라마를 몰아서 본다(Stack이나 재귀함수를 사용) BFS : 여러 드라마를 한 편씩 본다.(Queue나 LinkedList를 사용) DFS 또는 BFS로 풀어야 하는 대표적인 유형 1. 경로 탐색 유형(최단거리, 시간) 2. 네트워크 유형(연결) 3. 조합 유형(모든 조합 만들기) DFS가 동작 검증이 쉽다. 하나씩 조합을 만들어서 정답과 비교하기 때문에 조합이 잘 나왔는지 확인이 쉽다. 하지만 수행 시간 관점에서는 복불복 운이 좋으면 첫 번째 조합이 최적의 답, 최악의 경우에는 모든 조합을 다 만들어 보면서 시간을 낭비하게 된다. BFS는 한 번에 여러 조합들을 한 칸 한 칸씩 만들다 보니 조합이 완성되어 정답과 비교하는 시점에 언제 이렇게 만들어졌는지 또는 어디서부터 틀린 건지 분석.. 2022. 11. 26. 이전 1 다음