[백준_1260] DFS와 BFS

풀이과정

1. 양방향 접근이 가능하다. 길에 해당하는 li리스트에 길을 추가할 때 양방향으로 추가한다.

li = [[] for _ in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    li[a].append(b)
    li[b].append(a)

2. 길을 정렬해준다. (오름차순)

for i in range(1,N+1):
    li[i].sort()

3. (DFS) check 리스트로 진입 여부를 표시하고, stack으로 이동 경로를 표시한다. (이동경로의 시작은 V)

check = [True] * (N+1)
stack = [V]

4. (DFS) DFS 함수를 만들고 실행한다.

def DFS(last):
    check[last] = False
    for to_go in li[last]:
        if check[to_go]:
            stack.append(to_go)
            DFS(to_go)

DFS(V)

5. (DFS) 출력한다. : print(' '.join(map(str,stack)))

6. (BFS) 이동경로를 표시하는 stack, 진입 여부를 표시하는 check 리스트를 초기화하고, queue를 만든다. queue에는 첫 이동지점인 V를 추가한다.

que = deque()
check = [True] * (N+1)
que.append(V)
stack = []

7. (BFS) while문으로 BFS를 구현한다.

while que:
    start = que.popleft()
    if check[start]:
        stack.append(start)
        check[start] = False
        for i in li[start]:
            if check[i]:
                que.append(i)

8. (BFS) 출력한다. print(' '.join(map(str,stack)))

코드전문

from collections import deque
N,M,V = map(int,input().split())
li = [[] for _ in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    li[a].append(b)
    li[b].append(a)

for i in range(1,N+1):
    li[i].sort()

check = [True] * (N+1)
stack = [V]
def DFS(last):
    check[last] = False
    for to_go in li[last]:
        if check[to_go]:
            stack.append(to_go)
            DFS(to_go)

DFS(V)
print(' '.join(map(str,stack)))

que = deque()
check = [True] * (N+1)
que.append(V)
stack = []
while que:
    start = que.popleft()
    if check[start]:
        stack.append(start)
        check[start] = False
        for i in li[start]:
            if check[i]:
                que.append(i)
print(' '.join(map(str,stack)))