BFS4 [알고리즘] [15] 그래프 순회 1. 그래프 순회 비선형 구조인 그래프의 모든 정점을 빠짐없이 탐색하는 것 너비 우선 탐색과 깊이 우선 탐색으로 순회할 수 있다. 2. BFS (Breadth First Search) 탐색 시작점의 인접 정점을 모두 방문한 이후, 방문한 정점을 시작점으로 하여 차례로 방문한다. 그래프는 계층형 구조가 아니기 때문에 루트의 개념이 없어 임의의 정점에서 시작 가능하다. 선입선출 형태의 큐를 활용한다. 2024. 2. 16. [BOJ] [JAVA] 14442번 벽 부수고 이동하기 2 BFS를 공부하고 관련 문제를 풀었다. 그 중 하나를 적어보기로 했다. 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net import java.io.*; import java.util.*; // Hammer 클래스는 (x, y) 좌표에 위치한 사람이다. // 사람은 h 개의 해머를 가지고 있고 // 현재 좌표에 distance 만큼의 거리를 이동하여 도달해있다. class Hammer { int x; int y; int h; int di; public Hammer(int x, .. 2024. 1. 27. [BOJ] [JAVA] 1012번 유기농 배추 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net BFS를 이용해서 해결했다. BFS의 개념 자체는 어렵지 않은데, 코드를 깔끔히 구현하는 방법을 모르겠다. 내가 생각한대로 코드를 작성해봤다. 좌표값을 Queue에 집어넣어야하는데, 방법을 모르고 qX, qY로 x, y 좌표를 각각 받았다. Point라는 걸로 받으면 된다더라,, 그리고 나는 현재 depth에서 확인해야 할 노드의 개수를 그 전 depth에서 계산하고, 다음 depth에게 알려주는 방식으로 했는데 정석이 어떤지는 확인해봐야겠다! package BOJ; imp.. 2024. 1. 20. [알고리즘] [3] BFS 1. 그래프 탐색 그래프는 노드 (Node)와 간선 (Edge)으로 이루어진 자료구조이다. 그래프 탐색은 그래프에서 특정 조건을 만족하는 노드를 찾거나, 모든 노드를 방문하는 데 사용한다. BFS와 DFS는 가장 일반적인 그래프 탐색 알고리즘이다. 2. BFS (Breadth First Search) 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 특정 노드에서 인접한 노드를 모두 방문한 다음, 다음 레벨의 인접 노드로 이동하는 방법 자료구조 큐(Queue)를 사용하여 구현한다. BFS는 재귀적으로 작동하지 않는다. BFS는 어떤 노드의 방문 여부를 반드시 검사해야 한다. DFS는 무한한 길이를 가지는 경로에 도달했을 시 탐색 목표가 현재 경로에 있지 않다면 무한 루프에 빠질 수 있.. 2024. 1. 18. 이전 1 다음
