[BOJ] 백준 1260 파이썬 - DFS와 BFS

[BOJ] 백준 1260 파이썬 - DFS와 BFS

728x90

문제 출처 :

기본적인 DFS 와 BFS를 이용해 방문하는 노드를 순서대로 정렬하는 문제 입니다.

<그래프 구현 코드>

n, m, v = map(int, input().split()) dic = {} for i in range(n): dic[i+1] = set() # 각각의 간선에 연결된 노드 표시 for j in range(m): a, b = map(int, input().split()) dic[b].add(a) dic[a].add(b) # 서로가 서로의 하위 노드 이기 때문에 두개 모두에 추가 for i in range(1, n+1): dic[i] = sorted(dic[i]) # 방문할 노드가 여러개이면 작은 순서부터 방문한다 했으므로 sort 해줌

def dfs(start): if len(visitedDfs) == 0: # 첫번째 노드는 무조건 방문한 것 이므로 추가(for 문 안으로 들어가면 연결된게 없을때 오류남) visitedDfs.append(start) for i in dic[start]: if i not in visitedDfs: # 상위 노드와 연결된 하위 노드가 방문된적이 없으면 visitedDfs.append(i) dfs(i) # 재귀함수로 계속 돌려줌

from collections import deque queue = deque() # bfs 할때 dequeue를 수월하게 해주기 위해 deque 선언 def bfs(start): queue.append(start) # 연결된 하위노드의 너비에 해당하는 노드들을 추가 visitedBfs.append(start) # dfs와 마찬가지로 첫번째는 무조건 방문 while queue: a = queue.popleft() # 앞에서부터 순서대로 pop, 이미 sort됐기 때문에 크기 고려 안해줘도 됨 for x in dic[a]: # 상위노드와 연결된 하위노드 중에서 if x not in visitedBfs: # 방문 된적이 없다면 queue.append(x) # 작업열에 추가 visitedBfs.append(x) # 방문된 노드에 추가

<답 도출 코드>

dfs(v) bfs(v) print(*visitedDfs) print(*visitedBfs) # 리스트 형태가 아닌 노드의 번호만 출력해야 하므로 분해하여 출력

<전체 정답 코드>

from collections import deque n, m, v = map(int, input().split()) visitedDfs = [] visitedBfs = [] # visited 리스트 초기화 안하려고 두개 선언 dic = {} for i in range(n): dic[i+1] = set() # 각각의 간선에 연결된 노드 표시 for j in range(m): a, b = map(int, input().split()) dic[b].add(a) dic[a].add(b) # 서로가 서로의 하위 노드 이기 때문에 두개 모두에 추가 for i in range(1, n+1): dic[i] = sorted(dic[i]) # 방문할 노드가 여러개이면 작은 순서부터 방문한다 했으므로 sort 해줌 def dfs(start): if len(visitedDfs) == 0: # 첫번째 노드는 무조건 방문한 것 이므로 추가(for 문 안으로 들어가면 연결된게 없을때 오류남) visitedDfs.append(start) for i in dic[start]: if i not in visitedDfs: # 상위 노드와 연결된 하위 노드가 방문된적이 없으면 visitedDfs.append(i) dfs(i) # 재귀함수로 계속 돌려줌 queue = deque() # bfs 할때 dequeue를 수월하게 해주기 위해 deque 선언 def bfs(start): queue.append(start) # 연결된 하위노드의 너비에 해당하는 노드들을 추가 visitedBfs.append(start) # dfs와 마찬가지로 첫번째는 무조건 방문 while queue: a = queue.popleft() # 앞에서부터 순서대로 pop, 이미 sort됐기 때문에 크기 고려 안해줘도 됨 for x in dic[a]: # 상위노드와 연결된 하위노드 중에서 if x not in visitedBfs: # 방문 된적이 없다면 queue.append(x) # 작업열에 추가 visitedBfs.append(x) # 방문된 노드에 추가 dfs(v) bfs(v) print(*visitedDfs) print(*visitedBfs) # 리스트 형태가 아닌 노드의 번호만 출력해야 하므로 분해하여 출력

728x90

from http://j-34.tistory.com/38 by ccl(A) rewrite - 2021-11-16 01:27:03