[Python] 백준, 1260(트리)

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

1260번: DFS와 BFS

트리 알고리즘이라고 쓰기는 했지만, DFS, BFS 문항 중 가장 기본 문제인 것 같다. 실버2에 랭크되어 있는 것에 비해 아직 숙련도가 많이 부족해서 입력값 정리, 알고리즘 전개 방식 등 다방면에서 많이 헷갈리더라. 지난번에 포스팅했던 내용과 큰 차이는 없지만 이렇게까지 기억이 안나는 걸 보면 복습이 확실히 중요한 듯싶다. 

 

백준 티어 실버1으로 올랐다. 조금만 더 공부하면 드디어 골드다. 

 

# PYTHON CODE

from collections import deque
import sys

m, n , v = map(int, sys.stdin.readline().split())
tree = [[] for i in range(m + 1)]
visit = [False] * (m + 1)

for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    tree[a] += [b]
    tree[b] += [a]

for i in tree:
    i.sort()


def BFS(node):
    queue = deque([node])
    visit = [False] * (m + 1)
    visit[node] = True

    while queue:
        s = queue.popleft()
        print(s, end=' ')
        for i in tree[s]:
            if not visit[i]:
                queue.append(i)
                visit[i] = True

def DFS(node):
    visit[node] = True
    print(node, end=' ')
    for i in tree[node]:
        if not visit[i]:
            DFS(i)

def DFS2(node):
    stack = [node]
    list = []
    visit = [False] * (m + 1)
    while stack:
        s = stack.pop()
        if not visit[s]:
            visit[s] = True
            list.append(s)
            tree[s].sort(reverse=True)
            stack += tree[s]
    return list

BFS(v)
print()
print(' '.join(map(str, DFS2(v))))

BFS는 크게 문제가 없었는데, DFS가 잘 안 풀렸다.

 

재귀적인 방법은 약간의 구글링의 도움을 받아서 넘어갔지만, 스택을 이용한 비재귀적인 방법으로도 성공시키고 싶어서 DFS2라는 함수를 따로 정의했다. IDE 작업환경에서의 예제들은 모두 정답을 return했는데, 백준에서의 채점 결과는 오답이어서 질문 게시판에 올려놓은 상태인데 아직 어디가 잘못됐는지는 잘 모르겠다.