BFS2 [Algorithm] BFS/DFS 정리 너비 우선 탐색(BFS, Breadth-First Search) - BFS 루트 노드의 자식 노드들을 먼저 방문한 후, 방문했던 자식노드들을 기준으로 해당 노드의 자식노드들을 차례로 방문하는 방식 시작 정점으로부터 방문 가능한 가까운 정점들을 먼저 방문하는 것이다. 인전합 노드들을 탐색 후, 차례로 다시 너비우선탐색을 진행 => 선입선출 형태의 자료구조 큐이용 - 탐색 방법 1. 시작하는 칸을 큐에 넣고 방문표시 2. 큐가 빌때까지 아래의 과정을 반복 1) 원소를 꺼낸다. 2) 꺼낸 정점의 인접한 정점 탐색 3) 인접한 정점이 방문했던 적이 없다면, 방문 표시를 남긴 후 해당 칸을 큐에 넣는다. - 시간 복잡도 칸이 N개일 때: O(N) , 행이 R, 열이 C 인 경우: O(RC) 깊이 우선 탐색(DFS.. 2022. 4. 23. [백준] 1926번 그림 - 자바(Java) / bfs&dfs 📍 문제 링크 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 📍 문제 접근 그림은 1로 표시되어 있고, 가로나 세로로 연결된 경우 하나의 그림이다. 이차원 배열로 도화지를 선언하고, 인접한 위치 중에 1인 경우 탐색한다. => bfs, dfs 그림의 넓이 => 변수를 선언하여 탐색할 때마다 증가시키고, 탐색 종료 후 최대값을 갱신하자. 그림이 하나도 없는 경우 넓이를 0으로 출력해야 한다. 📍 코드 보기 public class BOJ_S1_1926.. 2022. 4. 22. 이전 1 다음