Queue, BFS 보충

Queue:

자료구조(Data structure)중 하나

데이터를 활용함에 있어서 좀 더 유용하게 활용하기 위해서 저장하거나 사용하는 방법을 말한다.

1. 선형 자료구조 :
   1. 요소간 1대1 구조를 가지는 자료 구조
   2. 1대1이란?
   3. 요소 하나가 있으면 이것도 대응되는것이 하나
   4. 또 하나가 있어도 대응되는것은 하나
   5. ⇒ 선후 관계가 성립한다. = 앞 뒤 관계를 알 수 있다.
2. 요소는 선입선출되는 구조다.

착각 하기 쉬운것?

queue는 그냥 이름일 뿐, 함수나 메소드 같은것이 아니다

큐를 구현하는것은 어려우니까

파이썬에서 리스트를 이용해서 append, pop 쓰는 것

BFS 란?

너비우선탐색은 줄임말일뿐 그래프의 완전 탐색 중에 하나다

배열

1차원 : 그냥 앞에서 부터 검사하거나 뒤에서 부터 전부 탐색하자

2차원 배열 : 한 행식 전부 검사하거나, 한 열식 전부 검사하거나 등 완전 탐색

근데 ???

만약 그래프를 완전 탐색 하기 위해서는 어떻게 해야될까?

⇒ DFS 또는 BFS

시작점과 거리가 1인 애들 전부 돌고, 2인 애들 전부 돌고 ⇒ BFS

하나의 루트로 쭉가다가 길이 없으면 돌아오겠다 ⇒ DFS

⇒ BFS란? 그래프를 완전탐색하는데 시작점에서 가까운 노드 순서대로 탐색하는 것

BFS 에서 가장 먼저 해야 하는 일 : 그래프 저장하기

그래프

1. 비 선형 자료구조
2. 노드와 노드간에 1: N, M:N의 연결구조를 가진다.
3. 노드와 간선으로 이루어짐

⇒ 그래프는 어떻게 저장하지? 노드의 이름과 인덱스를 연결

일단 노드간의 연결 정보를 저장

배열을 이용해서 그래프를 저장 ⇒ 연결정보를 저장

0-[]

1: [2,3,4]

2- [1,6,5]

3-[1,5,7]

4-[1]

5-[2,3]

6-[2]

7-[3]
adj[3] = 1,5,7 을 불러온다.

adj = 인접 리스트

• 인접리스트 = 1차원 배열 형태
• 인접행렬 = 2차원 배열 형태

이러한 리스트와 행렬을 가지고 탐색을 하겠다.

'''
7 8
1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7
 인접 행렬로 저장하기 : 노드 번호를 인덱스로 활용
'''
V, E = map(int,input().split())
adj = [[0] * (V+1) for _ in range(V+1)]
data = list(map(int,input().split()))
for i in range(0,E * 2, 2):   # 1번 노드와 2번 노드가 연결되어있으면   # adj[1][2] = 1   # adj[2][1] = 1   adj[data[i]][data[i+1]] = 1   adj[data[i+1]][data[i]] = 1
for row in adj:print(row)

# 이제 그래프 제대로 입력 받았으니 ... BFS 탐색 수행
# 현재 위치에서 갈 수 있는 경로를 모조리 저장해뒀다가
# 발견 순서대로 방문 : BFS
# 순서대로? Queu를 활용하면 되겠다!!
# queue를 위한 방법입니다 라고 한다면 목적과 수단이 바뀐것
def bfs(start):   queue = [start]  # 리스트지만 큐처럼 활용   # 0 : 미방문, 1: 방문한 노드   visited = [0] * (V + 1)  # 재 방문을 막기 위해 방문 여부 표시   visited[start] = 1   while queue: # 발견한 경로를 순서대로 방문     current = queue.pop(0)     # 현재 노드에서 방문할 수 있는 노드 탐색     # 방문할 수 있는 노드? : 인접하면서, 방문하지 않은 노드     # adj[current]  #  current와 연결되어 있는 노드 정보     print(current, end=' ')     # 히ㅕㄴ재 노드와 연결되어 있는지 확인!     for i in range(V+1):       # adj[current][i] == 1 이면 나랑 연결됨       # visited[i] == 0 이면 미방문       if adj[current][i] and not visited[i]:         queue.append(i) # i 번 노드에 갈 수 있다.         visited[i] = 1 # 방문했다, 반복을 줄이기 위해 여기 넣었음     # 전부 방문 확인
bfs(1)

for row in adj:print(row)
행렬 보기 편하다.