[Python] 백준 #1260- DFS와 BFS

문제

---

 

1260번: DFS와 BFS

코드

---

My answer

import sys
from collections import deque
input= sys.stdin.readline

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

graph=[[] for _ in range(n+1)]
visited=[0 for i in range(n+1)]

answer1,answer2=[],[]

for i in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
for i in range(1,n+1):
    graph[i].sort()

def dfs(idx):
    visited[idx]=1
    answer1.append(idx)
    for i in graph[idx]:
        if(visited[i]==0):
            dfs(i)
    return 0

dfs(v)
print(*answer1)

visited=[0 for i in range(n+1)]

def bfs(idx):
    Q=deque()
    Q.append(idx)
    while Q:
        idx=Q.popleft()
        visited[idx]=1
        answer2.append(idx)
        for i in graph[idx]:
            if(visited[i]==0 and i not in Q):
                Q.append(i)
    return 0

bfs(v)
print(*answer2)

Another answer

from collections import deque


def dfs(start):
    visited[start] = True
    print(start, end=" ")
    for i in graph[start]:
        if not visited[i]:
            dfs(i)


def bfs(start):
    queue = deque([start])
    visited[start] = True
    while queue:
        v = queue.popleft()
        print(v, end=" ")
        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)

N, M, V = map(int, input().split())
graph = [[] for _ in range(N + 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()

# dfs
visited = [False] * (N + 1)
dfs(V)
print()

# bfs
visited = [False] * (N + 1)
bfs(V)

풀이

---

아직 DFS와 BFS가 잘 익숙하지 않지만, 전체적인 뼈대는 다 똑같은 것 같다. 

우선 두 방법 공통적으로 해야할 것이 있다.

1. 그래프 생성

각 노드에 연결된 노드를 담고있는 즉 그래프 전체를 나타내는 리스트를 생성하는 것이다. 

예를들어, 1번이랑 2,4번 / 2번이랑 1,3번 이런식으로 연결되어있다고 하면 빈 리스트에다가 해당 노드의 인덱스에 연결된 노드를 넣어주면 된다. 무슨 말이냐, 위에 예시에서 graph=[[],[2,4],[1,3]] 이렇게 넣어주면 graph[1] 즉 1번과 연결된 노드는 2,4번 (graph[2]=2번과연결된 노드= 1,3번)이 되는 것이다. 

2. 방문확인 리스트 생성

dfs 재귀 bfs 큐 등을 구성할 때 계속 반복하는 것을 막기위하여 이미 확인한 노드인지를 체크하는 visited 리스트를 관리하는 것이다. 처음에는 전체 노드 모두 0으로 초기화를 해놓고 dfs혹은 bfs를 순회하면서 체크하고 visited를 1로 바꿔주고 추후 visited 가 1인 것은 건너뛰는 것이다. 

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

1. DFS 

우선 DFS는 재귀를 이용하거나 스택을 이용하는 방법이 있는데 나는 재귀를 이용하였다. 

위의 방법을 따라서 graph라는 변수와 visited라는 리스트 2개를 생성해준다. 그리고 주의해야할 점이 위 문제 같은 경우나 대부분 첫 시작노드를 정해주고, 위 문제에서는 노드 번호가 작은 것부터 순회한다고 명시되어 있으니 반드시 graph를 입력받은 후에 sort 해줘야한다. 

다음으로 dfs 함수를 설명해보자. 우선 dfs가 실행되면 해당 노드는 방문한 것으로 간주하여 visited에 1을 올려준다. visited변수나 graph변수 모두 함수 밖에서 선언하였기 때문에 함수내에서 수정하여도 변경이 밖에도 적용된다. 아무튼   이후 문제의 answer 즉 방문 순서를 기록하기 위해서 answer에다가 현재 노드를 넣어주고, 해당 노드에 연결된 작은 순번부터 visited가 0이면 즉 방문하지 않았으면 dfs를 또 실행한다. 즉 [[],[2,3],[1,3,4] ..] 뭐 이런식이라하고 v=1이라서 1번 노드부터 순회할때 [2,3] 중 2번 노드가 아직 visit하지않았으므로 3을 넘어가기전 바로 노드 2번 노드 dfs를 또 실행시켜 [1,3,4]로 들어가게 된다. 이때 1번은 방문했으니 3번 노드로 넘어가고 또 3번 노드 dfs를 실행한다. 이렇게 제일 깊숙히 들어가는 방식이라 깊이 우선 탐색이다.

2. BFS

다음으로 우선 위에서 진행하면서 visited를 변경하였기 때문에 다시 전부 0으로 초기화해주고 진행한다.

BFS를 진행하기위해 우선 임의의 큐를 하나 생성하고, Q에다가 현재 노드번호를 집어넣는다. 이후 Q가 빌 때까지 반복하면서 Q에서 노드하나를 빼고 해당 노드에 연결된 노드들을 돌면서 아직 방문하지 않았거나 이미 큐에 들어가있지 않으면 

큐 대기열에 집어넣는다. 

예를 들어 설명하면 아까와 같은 예시로 해보겠다. [[],[2,3],[1,3,4] ..] 가 있을 때 v=1부터 시작한다고 할때 아까 dfs는 1번 노드와 연결된 2,3번에서 2번 노드와 연결된 걸로 넘어가고 이런식이었다면, 

bfs는 우선 1번을 큐에 넣고, 1번에 연결된 2,3번을 확인하면서 2번이 방문하지않고 큐 대기열에도 없으므로 2도 큐에 넣는다. 또 2번 노드와 연결된 것으로 넘어가는게 아니라 1번과 연결된 나머지 3번을 확인하면서 진행한다. 이후 큐에 2,3이 들어가있게 되고 이제 2번과 연결된 것들을 또 순회한다. 

 

( 제가 이해한 내용을 바탕으로 작성하여, 틀렸다면 지적해주세요 ㅠㅠ 나중에 보려고 좀 주저리 적었습니다.)