백준 1260번 바로가기

나의 풀이

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


def dfs(adjacencyList, root):
  stack = [root]
  visitedList = []

  while stack:
    current = stack.pop()
    if current not in visitedList:
      visitedList.append(current)
      temp = adjacencyList[current - 1]
      temp.sort(reverse=True)
      stack += temp
  return visitedList


def bfs(adjacencyList, root):
  from collections import deque
  queue = deque([root])
  visitedList = []

  while queue:
    current = queue.popleft()
    if current not in visitedList:
      visitedList.append(current)
      temp  = adjacencyList[current - 1]
      temp.reverse()
      queue += temp

  return visitedList


adjacencyList = [[] for _ in range(n)]

for edge in edgeList:
  adjacencyList[edge[0] - 1].append(edge[1])

print(*dfs(adjacencyList, v))
print(*bfs(adjacencyList, v))

CODE REVIEW

  1. DFS와 BFS를 구현하고 방문한 Node(Vertex)를 순서대로 출력하는 문제였다.
  2. 중간 순서가 자꾸 꼬여서 코드를 살펴봤는데, current에 연결된 vertex를 저장할 때에 stack/queue를 reverse 시켜줘야 했다.
  3. 그래프 이론의 기본 DFS & BFS에 대해서는 이제 어느정도 익숙해졌는데, 더 상위 문제를 풀어가며 그래프 이론을 더 알아가봐야겠다.