와 어제 만들어놓고 정리해놓은 벨로그가 삭제 된것같다. 큰일 큰일.. 이지만 굴하지 않고 새롭게 작성하자 오늘은 확실히 조금 차근 차근 정리해가며 해보자!
개념을 다시 정리하면서 해보도록하면!
- BFS: 너비 우선 탐색
- DFS: 깊이 우선 탐색
어제 확실히 조금이라도 영상을 본게 도움이 된 것 같다. 지수님 감사!
백준1260 BFS와 DFS
이제 혼자 가벼운 그래프 정도는 짤 수 있을 것 같다.
- graph를 리스트 2차원으로 정리한다. 리스트안에 리스트를 넣는데 첫번째는 아주 비워놓고 그 다음번부터 1번에 연결된 것, 그 다음 리스트에 2번에 연결 된것으로, 이어서 나가면 된다 예를 들어,
graph = [
[],
[2,3], #1번 노드?라고 해야되나?
[1], #2번 노드
[1] #3번 노드
]
visited = [False]* (node개수 +1)이렇게 방문 기록을 남겨 둔다
3-1. DFS 코드는 재귀를 써서 오히려 좀 간단한 느낌이 있는데 지금 복습겸 다시 한번 써보자!
def dfs(graph, start, visited):
# True 박아 놓기
visited[start] = True
print(start, end = ' ')
for item in graph[start]:
if not visited[item]:
# 이 바로 아래줄은 굳이 안써줘도 되는 것 같고 ... 써도 통과는 한다
visited[item] = True
dfs(graph, item, visited)오 시발 좀 잘 쓴 듯?!
3-2. BFS 코드는 que를 써서 뭔가 좀 더러운 느낌이 있지만 그래도 일단 혼자 한번 써보자!
from collections import deque
def bfs(graph, start, visited):
# 큐에 일단 시작 박기
go_que = deque([start])
# 방문 박아놓기
visited[start] = True
# 큐가 없어질때 까지
while go_que:
# 큐에서 가장 왼쪽 예전에~ 들어 온거 팝!
v = que.popleft()
print(v, end = ' ')
# 그 팝된 그래프에서 일단 다 방문!
for item in graph[v]:
if not visited[item]:
go_que.append(item)
visited[v] = True이건 왜 이렇게 손에 안 붙는 지 모르겠다. 문제를 풀어봐야 정신을 차릴련지 ㅎㅎ.
백준11724 연결요소의 개수
단계별로 적어보자 그냥 심플한 dfs응용.... 이라고 말할 수 있나? ㅋㅋ
1단계. input 받기!
n_point, n_line = map(int, input().split())
graph = [ [] for _ in range(n_point + 1)]
for _ in range(n_line):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
sorting을 항상 하는게 좋더라고~
for item in graph:
item.sort()2단계. dfs 정의 해놓기
visited = [False] * (n_point + 1)
def dfs(graph, start):
global visited
visited[start] = True
# print(start, ' visited!')
for item in graph[start]:
if not visited[item]:
dfs(graph, item)
일단 나는 확인할때 방문한 것은 print(start, ' visited!') 으로 처리해줘서 확인을 하려고 했다.
dfs는 연결 된 것 만 방문할 수 있으니까!
- 여러번 돌리는 것을 해서 다 visit으로 만들때까지 반복해주는 아이디어로 하고
- visited를 기준으로 만약에 방문하지 않은 것이면 dfs로 방문해주는 아이디어로!
dfs_count = 0
visited = [False] * (n_point + 1)
for index in range(1, len(visited)):
if visited[index] == False:
dfs(graph, index)
# print('linked over! ')
dfs_count += 1
# print(visited)
else:
pass
print(dfs_count)
dfs를 카운트 해주는 데~
dfs가 한번 끝나면 linked over! 라고 발표해주는 방식으로 했다!
만약에 이미 방문 한 것이면 count는 끝낫음을 보여주는 방식으로!
아 맞다! 이거는 꼭 기억하자
sys.setrecursionlimit(10**6)재귀로 풀 때 설정 해주는 것을!
백준2606 바이러스
이것도 심플한 recursion 응용한 문제
약간 이제 dfs 그래프 문제는 이제 알것 같은데 이게 과연 효율적일지는 모르겠다!
import sys
sys.setrecursionlimit(10**6)
n_computer = int(input())
n_link = int(input())
graph = [[] for i in range(n_computer+1)]
for _ in range(n_link):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
for item in graph:
item.sort()
visited = [False] * (n_computer + 1)
visit_computer = []
def dfs(graph, start, visited):
visited[start] = True
visit_computer.append(start)
for item in graph[start]:
if not visited[item]:
dfs(graph, item, visited)
dfs(graph,1,visited)
print(len(visit_computer)-1)백준11725 트리의 부모 찾기
이 문제가 좀 뭐라고 해야되지 recursion dfs를 이해하고 있는가를 물어보는 문제 같은데
뿌려준다라고 생각하면 좀 편할것 같다. 연결 되는 것이 어차피 트리 구조로 되어 있으니까, 찾아가면서 뿌려준다 이런 식으로 생각해보자. 이건 진짜 어쩔 수 없이 답지를 참고햇는데 좀 허탈하다. 사실 트리에서의 특이한 구조?이기 때문에 아주 전형적인 문제라고는 할 수 없겠다.
import sys
sys.setrecursionlimit(10**6)
n_nodes = int(input())
graph = [[] for i in range(n_nodes+1)]
mothers = [0 for i in range(n_nodes+1)]
while True:
try:
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
except:
break
# print(graph)
def dfs(graph, start):
for item_linked in graph[start]:
if mothers[item_linked] == 0:
mothers[item_linked] = start
dfs(graph, item_linked)
else:
pass
dfs(graph, 1)
for mother in range(2, len(mothers)):
print(mothers[mother])백준1707 이분 그래프
쉬어가기
일단 너무 심심해서 공부할겸 Python Django web framework 3/14 까지 봄 이번주는 그냥 이런거 하나 야무지게 보는 걸로 하자
생활코딩그: python django framework
좀 좋은 것을 알아낸것
사실 visited라는 리스트를 계속 쓸 수 있는 게 신기 해서 가지고 왔다.
알게 된 사실
- 그냥 변수는 사실 바뀌지도 않고 쓸 수도 없다. 대신 global 쓰면 가능
- 리스트는 바뀌기도 하고 그렇게 BFS, DFS그래서 쓰는 듯
- 또한 촌수 찾기 문제에서 알아낸건데 그게 생각보다 중요한게 변수를 저장하면서 쓸 수도 없고 그러니까 아예
dfs(input)으로 받아내면 변수 count를 제어할 수 있어서 좋은 것 같다.
재귀 리턴받을 때!!!!!
또 개꿀띠
- 변수에다가 저장을 그냥 아무거나 해놓은 다음에 딱 원하는 타이밍일때 딱 global 생성한거를 갖다가 집어 넣어준다 아니면 global에 받아 놓기아아아아아 알겠슴돠!!!!
이거는 촌수 계산 백준 문제에서 사용하면 좋을 것 같으다앙
