🧚‍♂️알고리즘🧚‍♂️ - 완전탐색 - 너비 우선 탐색(BFS)

너비 우선 탐색(BFS)

탐색 시작 노드와 가까운 노드를 먼저 방문하여 완전 탐색하는 방법

최단 경로 찾기

 

- 큐 자료구조 이용 ->  선입선출 특성 필요

-노드 방문 여부를 체크할 리스트 필요

---

1260

실버 2

1260번: DFS와 BFS

- 노드 번호가 작은 것을 먼저 방문-> 오름차순 정렬하기

 

⭐️DFS BFS 기초 모양! ⭐️

import queue
from sys import stdin
N,M,V = map(int,stdin.readline().split()) #노드 / 간선 / 시작점
# 인접 노드 리스트 ( 노드 개수만큼 )+1(계산쉽)
Nlist = [[] for _ in range(N+1)]

#인접노드정보받기
for _ in range(M):
    A,B = map(int,stdin.readline().split())
    Nlist[A].append(B)
    Nlist[B].append(A)

# 번호가 같은 노드부터 방문하기 위해 정렬
for i in range(N+1):
    Nlist[i].sort()

#DFS
visited = [False for _ in range(N+1)] # 방문 체크 리스트!

def DFS(v):
    print(v, end=" ") #방문하는 노드 차례대로 출력
    visited[v] = True
    for i in Nlist[v]:
        if not visited[i]:
            DFS(i) #재귀이용
DFS(V)


print() # 줄바꿈

#BFS
from collections import deque #큐 필요
visited = [False for _ in range(N+1)] # 방문 체크 리스트!

def BFS(v):
    Myqueue = deque()
    Myqueue.append(v)
    visited[v] = True
    while(Myqueue): # 마이큐에 값이 있을 때까지
        NowNode = Myqueue.popleft() #선입선출
        print(NowNode, end = " ")#방문하는 노드 차례대로 출력
        for i in Nlist[NowNode]:
            if not visited[i]:
                visited[i] = True
                Myqueue.append(i)
BFS(V)

---

2178

실버1

2178번: 미로 탐색

최초로 목표 지점에 도달했을 때 깊이를 출력하면 됨

- DFS가 아닌 BFS인 이유: 해당 깊이를 전부 탐색한 후 다음 깊이로 넘어가므로 최솟값 얻기 가능

#BFS
from collections import deque #큐 필요
from sys import stdin
N,M = map(int,stdin.readline().split()) # 세로 가로
# 상하좌우 탐색을 쉽게 하기 위한 XY리스트
dx = [0,1,0,-1]
dy = [1,0,-1,0]
# 방문 체크 리스트!
visited = [[False]*M for _ in range(N)] 
# 미로&깊이갱신표
Nlist = [[0]*M for _ in range(N)]

for i in range(N):
    nlist = stdin.readline()
    for j in range(M):
        Nlist[i][j] = int(nlist[j])

def BFS(i,j):
    Myqueue = deque()
    Myqueue.append([i,j])
    visited[i][j] = True

    while(Myqueue): # 마이큐에 값이 있을 때까지
        NowNode = Myqueue.popleft() #선입선출

        for k in range(4): #사방면으로 탐색
            x = NowNode[0] + dx[k]
            y = NowNode[1] + dy[k]
            if x >= 0 and y >= 0 and x < N and y < M: # (dxdy에 -1이 있으므로 음수도) 범위 유의

                if Nlist[x][y] == 1 and not visited[x][y]: # 1로 된 길만 가야 함/간데또가면 ㄴ 
                    visited[x][y] = True
                    Nlist[x][y] = Nlist[NowNode[0]][NowNode[1]] + 1
                    Myqueue.append([x,y])
BFS(0,0) #Nlist 완성

print(Nlist[N-1][M-1])

이독자료

---

1167

골드 3

1167번: 트리의 지름

가장 긴 경로로 연결되어 있는 노드는 트리의 지름에 해당!

 

하나의 노드 선택 후 탐색 시작(BFS/DFS 무관) -> 거리 리스트에서 가장 큰 값을 가진 노드 찾기 -> 그 노드에서 한 번 더 탐색 -> 거리 리스트에서 가장 큰 값을 가진 노드 찾기  ==> 그 두 노드 사이가 트리의 지름

왜??

트리의 지름 구하기

와.. 이런 생각은 혼자 어떻게 해내야 하나요?

from sys import stdin

N = int(stdin.readline())
Nlist = [[i] for i in range(N+1)]

for _ in range(N):
    nlist = list(map(int, stdin.readline().split()))
    Nlist[nlist[0]] = nlist[1:-1]

distanceList = [0 for _ in range(N+1)] #거리
visited = [False for _ in range(N+1)] #방문여부

def DFS(v):
    stack = [v]
    while stack:
        node = stack.pop()
        visited[node] = True
        for i in range(len(Nlist[node])):
            if i % 2 == 0:
                if not visited[Nlist[node][i]]:
                    distanceList[Nlist[node][i]] += distanceList[node] + Nlist[node][i+1]
                    stack.append(Nlist[node][i])


DFS(2)
M = distanceList.index(max(distanceList[1:]))

distanceList = [0 for _ in range(N+1)] #거리
visited = [False for _ in range(N+1)] #방문여부
DFS(M)

print(max(distanceList[1:]))

---

스택/큐로 구현한 비슷한 형태의 DFS/BFS