boj 1260 : DFS와 BFS

문제 주소: https://www.acmicpc.net/problem/1260

난이도: silver 3

1.문제설명

• 그래프의 정보가 주어질 때
• DFS, BFS로 탐색한 결과를 출력하라
• 단 특정노드에서 여러개 노드로 이동할 수 있을 때
• 번호가 작은 노드부터 먼저 방문한다.

2.문제해결 아이디어.

• 인접리스트로 그래프 정보를 저장하고
• 이를 DFS, BFS를 구현하여 해결한다

3.문제접근법

• 번호가 작은 노드부터 방문하기 위해
• 입력을 다 받고 정렬해줘야한다.

4.특별히 참고할 사항

• 출력할때 문제 형식에 맞춰 아래와 같이 출력할 수 있다.

print("내용", end = ' ')

• 인터넷에 보면 visited 를 list로 구현하는 경우가 있는데, set이나 dict로 구현하는게 더 빠르다.
• 딕셔너리가 가장 빠를 것 같다. 일반적으로 시간복잡도가 O(1)이기 때문에

5.코드구현

from collections import deque
V, E, start = map(int,input().split())
graph = [[] for i in range(V+1)]

for _ in range(E):
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)
    graph[n2].append(n1)
for item in graph:
    item.sort()


def BFS(graph, start):
    visited = set()
    visited.add(start)
    queue = deque([start])
    while queue:
        curnode = queue.popleft()
        print(curnode, end=' ')
        for nextnode in graph[curnode]:
            if nextnode not in visited:
                queue.append(nextnode)
                visited.add(nextnode)


visited = set()
def DFS(graph, start, visited):
    visited.add(start)
    print(start, end = ' ')
    for nextnode in graph[start]:
        if nextnode not in visited:
            DFS(graph, nextnode, visited)


DFS(graph, start, visited)
print()
BFS(graph, start)