1260 - DFS와 BFS (silver 2)

"""
1260 - DFS와 BFS (silver 2)
"""
import sys
from collections import deque

input = sys.stdin.readline


def dfs(v):
    visited.append(v)
    for i in dic[v]:
        if i not in visited:
            dfs(i)


def bfs(v):
    visited.append(v)
    que = deque([v])
    while que:
        for i in dic[que.popleft()]:
            if i not in visited:
                visited.append(i)
                que.append(i)


# n: 정점개수 / m: 간선개수 / v:시작정점
n, m, v = map(int, input().split())

visited = []
dic = {}

for i in range(1, n + 1):
    dic[i] = set()
for _ in range(m):
    a, b = map(int, input().split())
    dic[a].add(b)
    dic[b].add(a)

dfs(v)
print(" ".join(str(i) for i in visited))
visited.clear()
bfs(v)
print(" ".join(str(i) for i in visited))

- 틀림!  

- 딕셔너리의 set 활용 때문이라고 생각 

dic = {1:{2,3,4}, 2:{3,4,5} .....}

set는 요소의 순서가 없기에 무작위로 선택 돼서 나온다.

(그런데, dic 출력이나 결과값들이 오름차순으로 잘 정렬 된 상태로 선택되어서 나와서 그냥 사용 함)

"""
1260 - DFS와 BFS (silver 2)
"""
import sys
from collections import deque

input = sys.stdin.readline


def dfs(v):
    visited.append(v)
    for i in lst[v]:
        if i not in visited:
            dfs(i)


def bfs(v):
    visited.append(v)
    que = deque([v])
    while que:
        for i in lst[que.popleft()]:
            if i not in visited:
                visited.append(i)
                que.append(i)


# n: 정점개수 / m: 간선개수 / v:시작정점
n, m, v = map(int, input().split())

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

for _ in range(m):
    a, b = map(int, input().split())
    lst[a].append(b)
    lst[b].append(a)

for i in range(len(lst)):
    lst[i].sort()

dfs(v)
print(" ".join(str(i) for i in visited))
visited.clear()
bfs(v)
print(" ".join(str(i) for i in visited))

- 간선 나타내기를 2차원 리스트로 변경

- 오름차순으로 값들을 확인해야 하므로 lst[i].sort()함수 사용

 

DFS / BFS 알고리즘