BFS

[알고리즘] BFS (너비우선탐색)

1. BFS (너비 우선 탐색)? BFS(Breadth-First-Search)는 너비 우선 탐색으로 큐(FIFO:선입선출)를 통해서 주로 구현이 됩니다. 출발 노드에서 가까운 것부터 접근하는 방식으로, 넓게, 층층히 탐색한다고 생각할 수 있습니다. 최단경로, 임의경로를 탐색해야하는 문제에서 주로 사용됩니다. DFS와 마찬가지로 방문체크를 해줄 필요가 있으며, 방문 체크를 하지 않을 경우 무한루프에 빠질 수 있습니다. 2. 기본적인 원리 기본적인 동작 원리는 다음과 같습니다. 현재 노드와 연결된 노드 중 방문되지 않은 모든 노드에 대해 방문체크 후 큐에 삽입 큐에서 가장 앞의 노드(가장 먼저 삽입된 노드) pop -> 새 노드 새 노드에 대해 1번 반복 큐에 원소가 없을 때까지 1~3 반복 처음에 시작노..

[백준7569] 토마토(3차원) / Java

문제주소 :www.acmicpc.net/problem/7569 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며..

[백준2178] 미로 탐색 / Java

문제주소 : www.acmicpc.net/problem/2178 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 입력 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는..

[백준1260] DFS와 BFS / Java

문제주소 :www.acmicpc.net/submit/1260 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결..