** 알고리즘 오답노트 16 (백준 - 1260)

박경준·2021년 6월 19일
0

알고리즘 문제풀이

목록 보기
19/24

DFS와 BFS

DFS는 스택, BFS는 큐를 기반해서 작성한다.
DFS와 BFS는 모두 노드 간의 연결 상태를 파악할 수 있는 무언가가 필요한데, 나는 딕셔너리가 편하다.
출력 양식(작은 수부터 탐험하는 양식)을 맞추기 위해서는 DFS에서는 딕셔너리의 value를 reverse sort 해야했고, BFS에서는 sort해야 했다.

여기서 스택이나 큐는 가야할곳, visited는 갔던 곳으로 이해하면 쉽다.

  • 틀린 부분 : 시작 노드가 아무것도 연결이 안되어있을 수 있는 경우를 예외처리 해야한다.
    이 문제에서는 연결이 안돼있다면 print(시작노드) 로 처리했다.
import sys
node_count, line_count, start_node = map(int, sys.stdin.readline().split())
graph = {}
dfs_visited = []
bfs_visited = []
dfs_stack = [start_node]
bfs_queue = [start_node]
for _ in range(line_count):
  line = list(map(int, sys.stdin.readline().split()))
  
  if line[0] in graph:
    graph[line[0]].append(line[1])
  else:
    graph[line[0]] = [line[1]]
    
  if line[1] in graph:
    graph[line[1]].append(line[0])
  else:
    graph[line[1]] = [line[0]]

# dfs
if start_node not in graph:  # 시작 노드가 아무것도 연결이 안되어있을수 있는 경우를 예외처리 해야한다.
  print(start_node)
else:
  for x in graph:
    graph[x].sort(reverse=True)

  while len(dfs_stack): # 더 가야할 곳이 있는 한 반복
    cur = dfs_stack.pop() # 방문할 리스트중 마지막 노드를 현재 노드로 둔다.
    if cur not in dfs_visited: # 현재 노드에 방문한 적 없다면
      dfs_visited.append(cur) # 방문했다는 기록을 해두고
    for i in graph[cur]: # 현재 노드의 인접 노드들을 하나씩 돌면서
      if i not in dfs_visited: # 인접 노드에 방문한 적 없다면
        dfs_stack.append(i) # 해당 노드를 방문할 리스트에 추가한다.

  for x in dfs_visited:
    if x == dfs_visited[-1]:
      print(x)
    else:
      print(x, end=' ')

# bfs
if start_node not in graph: # 시작 노드가 아무것도 연결이 안되어있을수 있는 경우를 예외처리 해야한다.
  print(start_node)
else:
  for x in graph:
    graph[x].sort()
    
  while len(bfs_queue):
    cur = bfs_queue.pop(0)
    if cur not in bfs_visited:
      bfs_visited.append(cur)
    for i in graph[cur]:
      if i not in bfs_visited:
        bfs_queue.append(i)

  for x in bfs_visited:
    if x == bfs_visited[-1]:
      print(x, end='')
    else:
      print(x, end=' ')
profile
빠굥

0개의 댓글