- 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 순회함
- A-B-C-D-G-H-I-E-F-J
그래프 표현 방법
- HashMap 과 ArrayList로 표현 가능
BFS
-
Queue를 이용 함
-
visited / needVisit 두개의 Queue 를 만듬
-
연결된 노드를 한 Hash Key 값에 ArrayList로 두고
-
탐색이란 ? 시작점에서 갈 수 있는 정점은?
-
BFS 에서는 다른 정점까지 최소 이동 횟수도 계산 가능하다.
dist[i] 라는 변수를 만들어서 S에서 i 까지 갈 때 필요한 최소 간선 개수
불가하면 - 1
visitcheck를 하는 순간에 dist를 하나 더 추가하면 됨
간선을 몇개 이동했냐 정도만 !
간선마다 가중치가 있으면 안됨
최소 , 가장 빠른 이라는 키워드
단지 번호 붙이기 문제
- 정답의 최대치는 모든 곳이 아파트인 경우 - 600개
- 단지가 다 떨어져 있는 경우 - 300개
- 격자형 그래프를 컴퓨터가 이해할 수 있도록 하는 경우
- (i,j) 격자가 중간이라면 위 (i-1,j) 왼쪽 ( i,j-1) 오른쪽 (i,j+1) 아래 (i+1,j)
- 간선을 만드는 조건 = 상하좌우가 인접해 있느냐
- 규칙이 있음 ((-1,0),(0,-1),(0,+1),(+1,0))
- 새로운 단지를 찾을 때마다 해당단지에 속해있는 집들은 처리되었다는 표시를 해주자!
- <격자형 그래프 > 정정 : O(N2) 간선 O(N2 * 4) BFS 든 DFS든 O(N**2)
