빈코의 개발일지

오늘은 BFS를 활용하여 미로의 최단 경로를 구해보는 문제를 풀어볼 예정입니다. 이전 포스팅에서 풀어 본 DFS를 활용한 미로 탐색과 풀이법이 유사하기 때문에 참고하면 좋을 듯하네요😊 개요 이 문제의 핵심은 BFS 알고리즘 활용과 Queue의 원리, 지나간 경로는 다시금 못 지나가게 막는 방법, 격자의 상하좌우 확인 총 4가지가 될 것 같아요. 한번 코드로 풀어볼까요? Point📙 class Point { public int x,y; Point(int x, int y) { this.x = x; this.y = y; } } Point 클래스는 격자판에서 x축, y축을 입력할 때 사용합니다. Queue에 지나간 격자를 넣거나 빼서 사용할 때 Point 클래스를 사용하여 현재 위치를 파악할 때 사용합니다. 자..

오늘은 DFS를 활용한 미로 탐색 문제를 풀어보려고 합니다😄 개요 이 문제의 핵심은 DFS 알고리즘 활용과 상하좌우 4방향으로 이동하는 방법이 주가 될 것 같아요. 한번 코드로 풀어볼까요? 📌 사전 지식으로 DFS의 원리와 Stack이 쌓이고 pop 되는 과정을 알아야 합니다. 모르시는 분은 해당 링크를 클릭해서 확인해주세요😀 Setting📙 public class MazeSearch { static int[] dx = {-1, 0, 1, 0}; static int[] dy = {0 ,1, 0, -1}; static int[][] board; static int result = 0; public static void main(String[] args) { MazeSearch T = new MazeSear..

오늘은 DFS 탐색 알고리즘을 사용한 동전 교환 문제를 풀어보려 합니다😊 개요 이 문제의 포인트는 DFS 탐색 알고리즘을 활용, 배열을 내림차순으로 하여 시간을 단축하였는가, 탐색하지 않아도 될 상황을 제한하였는가 총 3가지 인 것 같아요. 바로 코드를 보면서 확인해 볼게요😀 Main📙 public class ExchangeCoins { static int n, m, result = Integer.MAX_VALUE; public static void main(String[] args) { ExchangeCoins T = new ExchangeCoins(); Scanner sc = new Scanner(System.in); n = sc.nextInt(); Integer[] arr = new Integer[..

오늘은 Java 알고리즘에서 빼먹을 수 없는 DFS와 BFS에 대해 알아보려고 합니다. DFS는 Depth First Search의 약자로 깊이 우선 탐색을 말하고, BFS는 Breadth First Search의 약자로 너비 우선 탐색을 말합니다. 이 둘은 그래프 자료구조에서 완전 탐색을 수행하는 탐색 기법입니다😊 개요 앞서 말씀드린 그래프를 탐색하기 위한 대표적인 알고리즘 DFS, BFS를 이해하기 위해서는 스택(Stack), 큐(Queue), 재귀(Recursive)를 먼저 알아야 합니다. 스택과 재귀를 모르신다면 링크를 클릭해서 선수 학습을 해주세요😅 재귀 함수와 스택 프레임 코딩 테스트를 준비하면서 완전탐색, DFS, Back tracking 등의 알고리즘 개념을 접하게 되고, 자연스레 스택 프..