백준) DFS와 BFS

문제: https://www.acmicpc.net/problem/1260

 

오늘 스쿼드 진행 중에 DFS와 BFS 관련 문제로 튜터님이 제시한 과제(?)이다.

오늘의 주 목적은 DFS와 BFS의 확실한 이해와 그것을 적용 할 수 있게 하는 거였는데 문제 자체가 사이클로 되어 있어서 지금 까지 배워왔던 내용이랑은 조금 다른 문제였다.

 

확실히 다른 점은 간선(!!)이라는 녀석으로 문제에서 서로간 이동이 가능하게 되어서 양쪽다 확인 해야 하는 부분이 였다.

 

즉 연결된 간선은 서로 부모, 자식이 되는 관계인 것이다.

 

그래서 그런지 처음 DFS를 만들때 예시 출력에는 나오는 숫자가 내가 만든 코드로 예시를 출력하면 그 숫자가 안나왔다.

그리고 왜 작은 숫자가 먼저 선택되어 출력되는지도 이해가 안되었는데 지금 와서 문제를 읽어보니 문제 설명란에 해당 부분이 나와 순간 당황하게 되었다.

 

역시 아직은 그냥 문제를 잘 않읽고 내식대로 하는 버릇이 고쳐지 않은 듯 하다....

 

어찌저찌 문제를 그래프를 그리고 중복을 제외하려는 최대한 노력을 한 뒤 대망의 제출!!!

 

그러나 아쉽게(><!!) 실패

 

뭐가 문제인지 알 고 싶은 마음에 질문하기 쪽 반례를 가져다가 적용해 보아도 잘 나오기만 했다...

 

아니 결과 값은 잘 나왔었다.

 

문제는 제출 형식이 달랐던 점...

 

그냥 배열로 출력을 해버려 문제에서 요구하는 문자열 형태가 아닌 것.. 이거 찾는다고 20분 이상 소요 된 듯 하다..

 

아래 정답 코드를 넣었으니 스포가 싫으시면 누르지 마시길...(이 기능이 있다는 걸 오늘 알게 되어 한 번 적용해 봄)

 

스포 주의!!!

# DFS와 BFS
# https://www.acmicpc.net/problem/1260
from collections import deque
def dfs(graph, start):
    visited = []
    stack = [start]
    while stack:
        node = stack.pop()

        if node not in visited:
            visited.append(node)
            if node in graph:
                changes = list(sorted(graph[node], reverse=True))
                stack.extend(changes)
    return visited


def bfs(graph, start):
    visited = []
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.append(node)
            if node in graph:
                changes = list(sorted(graph[node]))
                queue.extend(changes)

    return visited


N, M, V = map(int, input().split())
lst = {}
for _ in range(M):
    x, y = map(int, input().split())
    if x in lst:
        lst[x].add(y)
    else:
        lst[x] = set()
        lst[x].add(y)

    if y in lst:
        lst[y].add(x)
    else:
        lst[y] = set()
        lst[y].add(x)

print(' '.join(map(str, dfs(lst, V))))
print(' '.join(map(str, bfs(lst, V))))