BFS 너비 우선 탐색

BFS 1) BFS란?Breadth-First Search (너비 우선 탐색)의 약어로그래프 또는 트리 구조에서 루트(시작점)에서부터 가까운 노드부터 차례대로 탐색해 나가는 알고리즘입니다. 탐색 대상의 깊이보다는 너비(수평)를 먼저 탐색한다는 특징이 있습니다.즉, 시작 노드에 연결된 모든 이웃 노드를 먼저 방문하고, 그 다음에는 그 이웃들의 이웃 노드를 탐색하는 방식입니다.BFS는 보통 큐(Queue) 자료구조를 사용하여 구현됩니다. 2) BFS 시간복잡도요소 설명시간 복잡도O(V + E) → V: 정점 수, E: 간선 수공간 복잡도O(V) → 큐와 방문 리스트 저장 용도 BFS는 모든 정점을 한 번씩 방문하고, 각 간선도 한 번씩 확인하기 때문에, 총 연산량은 노드 수 + 간선 수에 비례합..

• format_list_bulleted Algorithm/이론
• · 2025. 4. 30.

[백준 1926] Java - 그림

그림 https://www.acmicpc.net/problem/1926 1) 문제어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와 가장 넓은 그림의 넓이를 출력하여라.그림은 1로 연결된 영역이고, 가로나 세로로만 연결된 것을 연결된 것이라 한다.그림의 넓이는 1의 개수이다.입력: 세로 크기 n (1 ≤ n ≤ 500), 가로 크기 m (1 ≤ m ≤ 500)이후 n줄에 걸쳐 0과 1로 이루어진 도화지 정보 제공출력: 그림의 개수와 가장 넓은 그림의 넓이 (없으면 0) 2) 예시입력출력6 5 1 1 0 1 10 1 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 1 1 1 0 0 1 1 149 3) 풀이 1. 아이디어2중 for문으로 모든 좌표 순회 → 값이 1이면서 방문..

• format_list_bulleted Baekjoon Coding Test/Java
• · 2025. 4. 3.