DFS BFS 알아둘 것
- DFS 문제든 BFS 문제든 방문 기록을 활용하는 방식으로,
- "방문 기록"을 남기는 방향으로 문제를 푸는 유형이다 라고 생각하면 될거같다.
Python - Stack & Queue
- Stack 사용 시 그냥 list를 활용
- stack = []
- stack.append(4)
- stack.pop() # 최상단 원소 제거
- Queue 사용 시 라이브러리 활용 <중요>
- from collections import deque
- queue = deque() # 큐 생성
- queue.append(5)
- queue.popleft() # 가장 먼저 들어온 데이터 삭제
- queue.reverse() # 큐 내용물을 역순으로 바꾸기
""" Python """
def dfs(graph, v, visited):
# 3. 방문한 노드 체크
visited[v] = True
print(v, end=' ')
# 4. 현재 노드와 연결된 다른 노드를 재귀적으로 방문
# 재귀호출!! (<-> BFS)
for i in graph[v]:
if not visited[i]: # not 연산자<중요>
dfs(graph, i, visited)
# 1. Input graph : 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
[], # 보통 1번부터 있기 때문에 인덱스 0번은 비워둠
[2,3,8], # 2번 노드(에 연결된 노드들)
[1,7], # 3번 노드
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# 2. 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9 # 리스트 인덱스 0부터 시작이기 때문에 9개
dfs(graph, 1, visited)
''' 내가 짠 코드 '''
def dfs(graph, v, visited):
if visited[v] == False:
visited[v] = True
print(v, end=' ')
for i in graph[v]:
dfs(graph, i, visited)
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False]*9
dfs(graph, 1, visited)
다 필요없고 BFS 핵심
0. BFS는 재귀 X이다.
1. 따라서 BFS 안에 큐 생성한다
2. 시작 포인트 일단 넣는다
3. while queue
4. 현위치 = popleft()
5. for 다음위치(또는 다음 노드) 가져와
6. 다음 위치가 조건에 맞으면(또는 방문 안했으면) 이동시켜
7. queue.append(다음위치) <--- 개중요 (for안에 넣어서 다음위치/이웃노드 전부 넣어주는)- 그리고 DFS 문제든 BFS 문제든 방문 기록을 활용하는 방식으로,
- "방문 기록"을 남기는 방향으로 문제를 푸는 유형이다 라고 생각하면 될거같다.
''' Python '''
from collections import deque
def bfs(graph, start, visited):
# 3. BFS를 위해 큐(Queue) 생성
queue = deque([start]) # parameter node 하나를 큐에 넣음
# 해당 방문한 노드 체크
visited[start] = True
# 4. 큐가 빌 때까지 반복!!
while queue:
# 5. 큐에서 하나의 원소를 뽑아 출력
v = queue.popleft()
print(v, end=' ')
# 6. 아직 방문하지 않은 인접 원소를 "전부" 큐에 삽입
# 큐에 삽입한건 모두 방문처리함!!! (너비우선<->깊이우선_하나씩)
# 그래서 재귀호출 X !!! (<-> DFS)
for i in graph[v]:
if not visited[i]:
queue.append(i) # 방문 안한 노드 넣어주고
visited[i] = True # 넣은건 바로 체크(=방문)
# 1. Input graph : 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
[], # 보통 1번부터 있기 때문에 인덱스 0번은 비워둠
[2,3,8], # 2번 노드(에 연결된 노드들)
[1,7], # 3번 노드
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# 2. 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9 # 리스트 인덱스 0부터 시작이기 때문에 9개
bfs(graph, 1, visited)
''' 내가 짠 코드 '''
from collections import deque
queue = deque()
def bfs(graph, v, visited):
if visited[v] == False:
visited[v] = True
print(v, end=' ')
for i in graph[v]: # 이웃 노드를 다 넣어주는게 핵심이다
if visited[i] == False: # 불필요한 탐색 횟수 제거
queue.append(i)
if len(queue) > 0:
bfs(graph, queue.popleft(), visited)
graph = [
[],
[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)
- 그래프 만들기 (중요)
- 입력은 그래프 형태로 줄 수도 있지만, edge형태로 준다면 graph로 변환해야 함
- 입력은 그래프 형태로 줄 수도 있지만, edge형태로 준다면 graph로 변환해야 함
''' 내가 만든 - 밑에거가 더 편하다 '''
# n : 노드 수, m : 엣지 수, v : 시작 노드 번호
n, m, v = map(int, input().split())
# 밑에 코드 보면 알겠지만 필요 없는 배열이었다...
arr = [list(map(int, input().split())) for _ in range(m)]
check = [False] * (n+1) # (중요) False로 만들 것
# Create Graph (내가 만듦) - edge는 양방향이므로 둘 다 넣어준다
graph = [[] for _ in range(n+1)]
for i in range(len(arr)):
graph[arr[i][0]].append(arr[i][1])
graph[arr[i][1]].append(arr[i][0])
print(graph)
''' 다른 사람 코드 (블로그) '''
import sys
input=sys.stdin.readline
n,m,start=map(int,input().split())
visited=[False]*(n+1)
graph=[[] for _ in range(n+1)] # 빈 2차원 배열 생성! (n+1)개
for _ in range(m):
a,b=map(int,input().split()) # 내 코드와 달리 edge배열을 만들지 않음!
graph[a].append(b)
graph[b].append(a)
Do My Best