파이썬(Python) 코테 대비 DFS/BFS : 백준 1260번 DFS와 BFS

[시작 체크 리스트]

1. 1시간 지났으나 발상 불가 또는 아예 다른 길
2. 코드 50% 정도 완성
3. 1시간 보다 더 걸려서 코드 완성
4. 코드는 다 돌아가는데 효율성에서 걸림
5. 코드 완성

[완료 후 체크 리스트]

1. 아예 모르겠음
2. 중간 정도 이해함
3. 완벽히 이해함

[스터디 시간]

1. 발상

DFS : 이어달리기, 바통터치 느낌 (한 정점에서 이어진 다른 정점 간 다음, 그 정점과 이어진 정점 순차적으로 이어주기)
BFS : 와이파이 느낌 (우선 한 정점과 이어진 모든 정점을 들른 후, 다음 정점도 마찬가지로 시작)

ex) 백준 문제 입력 예시 :
     1 2
     1 3
     1 4
     2 4
     3 4

dfs의 경우 : 1에서 시작해서 이어져있는 2로 간후, 2와 이어져있는 4로 가고, 4와 이어져있는 3으로 감 (바통터치)

bfs의 경우 : 1(공유기)에서 시작해서 이어져있는 2로 간후, 3도 가고난 후, 2(공유기)와 이어진 4로 간 후, 3(공유기)과 이어진 4로 감

2. 코드

N,M,V=map(int,input().split())
matrix=[[0]*(N+1) for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    matrix[a][b]=matrix[b][a]=1
visit_list=[0]*(N+1)

def dfs(V):
    visit_list[V]=1 #방문한 점 1로 표시
    print(V, end=' ')
    for i in range(1,N+1):
        if(visit_list[i]==0 and matrix[V][i]==1):
            dfs(i)

def bfs(V):
    queue=[V] #들려야 할 정점 저장
    visit_list[V]=0 #방문한 점 0으로 표시
    while queue:
        V=queue.pop(0)
        print(V, end=' ')
        for i in range(1, N+1):
            if(visit_list[i]==1 and matrix[V][i]==1):
                queue.append(i)
                visit_list[i]=0

dfs(V)
print()
bfs(V)

(출처 : https://www.acmicpc.net/problem/1260)