201224 개발일지(17일차) - 완전 탐색을 위한 알고리즘(2) : DFS(Depth-First Search)와 BFS(Breadth-First Search)

DFS와 BFS 모두 탐색했던 노드에 대해 방문 처리를 남겨줘야 한다!

visited 등의 리스트 자료형으로 표현하고, True 와 False를 활용해 방문 여부를 남겨주면 편하다.

BFS란?

Breadth-First Search의 약자로 너비-우선 탐색이라고도 불린다. 그래프에서 넓은 부분을 우선적으로 탐색하는 구조이다. 큐 구조를 활용한다.
(DFS는 스택 구조를 활용했다.)

그래프 표현 2가지는 DFS와 같은 내용!

앞의 포스팅을 확인하자.

BFS 구현하기

아래와 같은 그래프를 BFS로 구현해보자.

from collections import deque 		#큐(Queue) 구현을 위해 deque 라이브러리 사용

def bfs(graph, start, visited):
	queue=deque([start])
	visited[start] = True		#현재 노드를 방문 처리
    print(start, end=" ")		#현재 노드 출력
    
    while queue:			#큐가 빌 때까지 반복
        v = queue.popleft()		#큐에서 하나의 원소를 뽑아 출력
        print(v, end=' ')
        for i in graph[v]:		#해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
            if not visited[i]:
                queue.append(i)
                visited[i] = True
                            
                            
graph = [				#graph 만들기
    [],					#0번 노드는 보통 문제에서 없으므로, 헷갈리게 하지 않기 위해 빈 리스트로 생성만 해 둠
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visited = [False] * 9

bfs(graph,1,visited)

<출력값>
>>> 1 2 3 8 7 4 5 6

input값으로 graph 정보를 받아와 graph를 입력하는 방법

실제 문제에서는 위와 같이 graph에 직접 정보를 넣어줄 수 없다.
따라서 아래와 같은 아이디어가 필요하다.

#n이 노드의 수, m이 간선 정보의 수(노드 연결 정보)

matrix = [[] for _ in range(n+1)]
for i in range(m):
    p1, p2 = map(int, sys.stdin.readline().rstrip().split())	#p1, p2는 임시 노드 변수라고 생각하면 된다.
    matrix[p1].append(p2)
    matrix[p2].append(p1)
    
#위의 그림과 같은 그래프는 n=8일 것이며, m=9이다.