빈코의 개발일지

오늘은 BFS를 활용하여 토마토 문제를 풀어보려 합니다. 토마토 문제는 근방에 익은 토마토가 있다면 하루가 지나 같이 익게 되고, 모든 토마토가 다 익을 때까지의 날짜 수를 구하는 문제입니다😄 개요 이 문제의 핵심은 BFS 알고리즘을 활용과 Queue의 원리, 여러 시작점에서 동시다발적으로 여러개의 토마토가 익는 부분, 상자의 상하좌우 확인 방법, 익은 토마토를 체크 총 5가지가 되겠네요😀 TomatoPoint📙 class TomatoPoint { public int x,y; TomatoPoint(int x, int y) { this.x = x; this.y = y; } } TomatoPoint 클래스는 상자판에서 행,열을 입력할 때 사용합니다. 근방에 익은 토마토에 의해 해당 토마토가 익을 때 큐에 쌓..

오늘은 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 & BFS 기초에 이어서 알고리즘을 활용하여 Tree 말단 노드까지의 가장 짧은 경로를 구하는 간단한 문제를 풀어 볼 예정입니다😄 개요 사실 최단 경로를 구하는 문제는 대게 BFS(넓이 우선 탐색)를 이용하여 문제를 풀지만, DFS로도 풀 수 있는 문제가 왕왕 있기 때문에 2가지 문제 풀이법 모두 진행해보려 합니다. 문제는 위 그림처럼 1번 노드에서 시작해 가장 말단 노드까지 가는 최단 경로를 구하는 문제입니다. 여기서 말단 노드는 하위 노드가 없는 노드를 뜻하며 그림에서는 4, 5, 3에 해당하겠네요! 가장 짧은 간선을 구하기 때문에 한 개의 간선만 필요한 3번 노드가 말단 노드로 지정되고, 정답은 간선의 개수이기 때문에 1이 되겠습니다😊 이전 포스팅과 마찬가지로 Node ..

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