https://www.acmicpc.net/problem/1260
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
내 코드
from collections import deque
def quick(array) :
if len(array) <= 1 :
return array
p = array[len(array) // 2]
less = [x for x in array if p > x]
mid = [x for x in array if p == x]
bigger = [x for x in array if p < x]
return quick(less) + mid + quick(bigger)
def main() :
n, m, v = list(map(int, input().split()))
graph = [[] for _ in range(n+1)]
for _ in range(m) : #그래프 입력받기
n1, n2 = list(map(int, input().split()))
graph[n1].append(n2)
graph[n2].append(n1)
for i in range(n+1) :
graph[i] = list(set(graph[i])) #모두 넣고 중복 제거
graph[i].sort()
visited = [False] * (n+1)
ans1 = dfs(graph, v, visited)
visited = [False] * (n+1)
ans2 = bfs(graph, v, visited)
print(*ans1)
print(*ans2)
def dfs(graph, start, visited) :
stack = []
stack.append(start)
ans = []
while stack :
node = stack.pop()
if not visited[node] :
visited[node] = True
ans.append(node)
stack.extend(reversed(graph[node]))
return ans
def bfs(graph, start, visited) :
queue = deque([start])
ans = []
while queue :
node = queue.popleft()
if not visited[node] :
visited[node] = True
ans.append(node)
queue.extend(graph[node])
return ans
if __name__ == "__main__" :
main()
느낀점
1. Index 범위 설정에 오류가 나지 않도록 잘하자
2. dfs, bfs에 더 익숙해지도록 하자
풀이 시간
