[백준] Python 1260 DFS와 BFS

[백준] Python 1260 DFS와 BFS

삼성전자 코테를 위한 DFS,BFS 유형을 익혀야 한다.
위는 링크텍스트 에 나와있는 DFS+BFS 필수 문제 리스트이다.

단순 DFS와 BFS 함수를 구현해서 출력하는 문제다.
여기서 주의해야하는 점은, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 한다는 점이다. 이를 위해, 2차원 정렬이 필요한데, for 문을 돌아가며 각각의 리스트에서 정렬해주었다.

from collections import deque
import sys
sys.stdin=open("input.txt")

n,m,v=map(int,input().split())

graph=[[]for _ in range(n+1)] #1번 부터 시작
for _ in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in graph:
    i.sort() #2차원 리스트 안에서 각각 정렬을 진행하려면, for 문을 돌면서 정렬해야한다.


visited=[False for _ in range(n+1)]
def dfs(graph,visited,v):
    visited[v]=True
    print(v,end=' ')

    for i in graph[v]:
        if not visited[i]:
            dfs(graph,visited,i)

def bfs(graph,visited,v):
    q=deque()
    q.append(v)
    visited[v]=True

    while q:
        x=q.popleft()
        print(x, end=' ')

        for i in graph[x]:
            if not visited[i]:
                visited[i] = True
                q.append(i)

dfs(graph,visited,v)

visited=[False for _ in range(n+1)]
print()
bfs(graph,visited,v)