백준 1260 : DFS와 BFS

필수로 익혀야 할 알고리즘 DFS와 BFS를 사용해보자.

 

문제

1260번: DFS와 BFS

우선 입력을 받을 코드를 먼저 작성해준다.

우선 노드의 수, 간선의 수, 시작 노드를 입력을 받는다.

그 후 간선의 수 만큼 입력을 받아 인접 리스트 방식으로 그래프를 만들어 줄 것이다. 방문 확인을 위한 리스트도 만들어 줘야함.

Node,edge,start = map(int,input().split())

graph = [[]for _ in range(Node+1)]
visited = [False]*(Node+1)

for _ in range(edge):
    n, m = map(int,input().split())
    graph[n].append(m)
    graph[m].append(n)

이 때 노드와 노드의 연결을 입력 받을 때 각 노드에 저장해주어야 한다. 예를 들어 5 2 라는 입력을 받았으면

5와 2는 연결되었다는 의미이므로 graph[5].append(2), graph[2].append(5)로 저장해주어야 함.

그 다음 노드에 접근해서 다른 노드에 방문할 때 작은 수 부터 방문을 해야하니 정렬을 해준다.

그 후에 DFS와 BFS 함수를 구현하도록 하겠다.

for i in graph:
    i.sort()

DFS(graph,visited,start)
visited = [False]*(Node+1)
print()
BFS(graph,visited,start)

DFS는 시작노드를 방문했을 때 방문 표시를 해준 뒤에 시작 노드를 출력한다. 그 후에 시작노드에 연결된 노드에 방문한뒤,  방문하지 않은 노드라면  출력, 또 다시 연결된 노드의 연결된 노드를 방문한다. (반복) 본래 스택으로 구현하나 재귀로 쉽게 구현할 수 있다. 

def DFS(g,v,s):
    v[s] = True
    print(s, end=' ')
    for i in g[s]:
        if not v[i]:
            DFS(g,v,i)

BFS는 시작 노드를 방문하고 시작 노드와 연결된 노드를 모두 큐에 넣는다. 

연결된 노드를 방문하고 연결된 노드의 연결된 노드를 큐에 추가한다. 다시 큐에서 노드를 꺼낸 방문하고 연결된 모든 노드를 큐에 넣는다. 큐에 넣었기 때문에 넣은 순서대로 방문한다. 즉 시작노드, 시작노드와 연결된 노드들, 시작노드와 연결된 노드들과 연결된 노드들 순으로 방문한다.

def BFS(g,v,s):
    queue = deque([s])
    v[s] = True

    while queue:
        n = queue.popleft()
        print(n, end=' ')
        for i in g[n]:
            if not v[i]:
                queue.append(i)
                v[i] = True

 

전체 코드

from collections import deque

def DFS(g,v,s):
    v[s] = True
    print(s, end=' ')
    for i in g[s]:
        if not v[i]:
            DFS(g,v,i)

def BFS(g,v,s):
    queue = deque([s])
    v[s] = True

    while queue:
        n = queue.popleft()
        print(n, end=' ')
        for i in g[n]:
            if not v[i]:
                queue.append(i)
                v[i] = True
        
    


Node,edge,start = map(int,input().split())

graph = [[]for _ in range(Node+1)]
visited = [False]*(Node+1)

for _ in range(edge):
    n, m = map(int,input().split())
    graph[n].append(m)
    graph[m].append(n)

for i in graph:
    i.sort()

DFS(graph,visited,start)
visited = [False]*(Node+1)
print()
BFS(graph,visited,start)