[파이썬] 백준 1260 : DFS와 BFS (실버2)

[파이썬] 백준 1260 : DFS와 BFS (실버2)

 

1260번: DFS와 BFS

 

---

문제

---

풀이

0.방향성 생각

탐색 시 순번이 낮은 노드부터 탐색하므로 입력을 받은 후 정렬하는 과정이 필요함

 

1. 입력

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

node,line,start = map(int,input().split())
arr = [[] for i in range(node+1)]
for i in range(line):
    a,b = map(int,input().split())
    arr[a].append(b)
    arr[b].append(a)
    
for i in arr :
    i.sort()

 

2. DFS

# DFS
visit = [False]*(node+1)
stack = [start]
answer = []
while stack :
    x = stack.pop()
    if not visit[x]:
        visit[x] = True
        answer.append(x)
        for nx in reversed(arr[x]):
            if not visit[nx]:
                stack.append(nx)
print(*answer)

스택에 시작 노드를 넣는다.

방문처리 안돼있으면 True로 변경하고 answer에 넣는다.

다음 방문할 노드를 찾는다.

스택으로 구현했으므로 앞에서 정렬한 arr[x] 그대로 넣으면 2 3 4 순서로 탐색해야할게 4 3 2로 탐색된다.

다음 노드들에 대해서 방문이 안돼있으면 스택에 추가한다.

3. BFS

# BFS
visit = [False]*(node+1)
answer = []
q = deque()
q.append(start)

while q:
    x = q.popleft()
    if not visit[x] :
        visit[x] = True
        answer.append(x)
        for nx in arr[x]:
            if not visit[nx]:
                q.append(nx)
print(*answer)

큐에 시작 노드를 넣는다

방문처리 안돼있으면 True로 변경하고 answer에 넣는다

다음 방문할 노드를 찾는다.

순서대로 넣어주고 방문처리가 안돼있으면 큐에 추가한다.

---

전체코드

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

node,line,start = map(int,input().split())
arr = [[] for i in range(node+1)]
for i in range(line):
    a,b = map(int,input().split())
    arr[a].append(b)
    arr[b].append(a)
    
for i in arr :
    i.sort()

# DFS
visit = [False]*(node+1)
stack = [start]
answer = []
while stack :
    x = stack.pop()
    if not visit[x]:
        visit[x] = True
        answer.append(x)
        for nx in reversed(arr[x]):
            if not visit[nx]:
                stack.append(nx)
print(*answer)

# BFS
visit = [False]*(node+1)
answer = []
q = deque()
q.append(start)

while q:
    x = q.popleft()
    if not visit[x] :
        visit[x] = True
        answer.append(x)
        for nx in arr[x]:
            if not visit[nx]:
                q.append(nx)
print(*answer)

언패킹 안해서 틀림

보통 DFS같은 경우는 재귀로 구현하는데 기본적으로는 스택으로 구현