[CodingTest] 백준 1260번 DFS와 BFS

문제

내 풀이

init_ls = input().split()
vertex_num = int(init_ls[0])
edge_num = int(init_ls[1])
start_vertex = int(init_ls[2])

adjacency_ls_dfs = [[] for _ in range(vertex_num+1)]
adjacency_ls_bfs = [[] for _ in range(vertex_num+1)]

for _ in range(edge_num):
    edge = input().split()
    edge[0] = int(edge[0])
    edge[1] = int(edge[1])
    
    adjacency_ls_dfs[edge[0]].append(edge[1])
    adjacency_ls_dfs[edge[1]].append(edge[0])
    
    adjacency_ls_bfs[edge[0]].append(edge[1])
    adjacency_ls_bfs[edge[1]].append(edge[0])


for i in range(len(adjacency_ls_bfs)):
    adjacency_ls_dfs[i] = sorted(adjacency_ls_dfs[i], reverse=True)
    adjacency_ls_bfs[i] = sorted(adjacency_ls_bfs[i])

stack = [start_vertex]
visited_vertex_dfs = []

while stack:
    current = stack.pop()
    
    for neighbor in adjacency_ls_dfs[current]:
        if (not neighbor in visited_vertex_dfs) :
            stack.append(neighbor)
    if current not in visited_vertex_dfs:
        visited_vertex_dfs.append(current)
    

visited_vertex_bfs = []    
    
from collections import deque

queue = deque([start_vertex])
visited_vertex_bfs.append(start_vertex)

while queue:
    current = queue.popleft()
    for neighbor in adjacency_ls_bfs[current]:
        if (not neighbor in visited_vertex_bfs) :
            queue.append(neighbor)
            if neighbor not in visited_vertex_bfs:
                visited_vertex_bfs.append(neighbor)


for i in visited_vertex_dfs:
    if i == visited_vertex_dfs[-1]:
      print(i)
      break
    print(i, end = " ")
    
for i in visited_vertex_bfs:
    print(i, end = " ")

bfs와 dfs를 이용해 풀어본 두번째 문제이다. graph에 cycle이 있는 경우 어떻게 해결해야하는지 점차 알아가게 되는 것 같다. 지금 사용하고 있는 dfs코드에서는 adjacency_ls가 vertex별로 성분이 내림차순으로 정렬되어 있어야 하고 bfs코드는 오름차순으로 정렬되어 있어야 하는데, 하나의 adjacency_ls를 이용하도록 개선이 필요하다.