[알고리즘 연습]-DFS와 BFS(python)

1. 문제링크

[DFS와 BFS] : https://www.acmicpc.net/problem/1260

2. 풀이 전 생각

문제가 짧아서 배운 내용을 잘 써먹으면 풀 수 있을거라 생각했지만, 생각보다 어려웠다. 일단 수업때는 완전 이진트리를 갖춘 dfs와 bfs를 배웠지만 문제에서는 그저 정점끼리 연결되어있는 형태여서 1차 멘붕이 왔다..

3. 풀이

import sys

n, m, v = map(int, sys.stdin.readline().split())

graph = {i : list() for i in range(1,n+1)}
dfs_visited = []
bfs_visited = []

for j in range(m):
    x, y = map(int, sys.stdin.readline().split())
    graph[x].append(y)
    graph[y].append(x)

for h in range(1,n+1):
    graph[h].sort()

def dfs(graph, v):
    dfs_visited.append(v)
    for gra_node in graph[v]:
        if gra_node not in dfs_visited:
            dfs(graph, gra_node)
    return dfs_visited


def bfs(graph, v):
    queue = [v]
    while queue:
        cur_node = queue.pop(0)
        bfs_visited.append(cur_node)
        for gra_node in graph[cur_node]:
            if gra_node not in bfs_visited and gra_node not in queue:
                queue.append(gra_node)
    return bfs_visited

dfs(graph,v)
bfs(graph,v)

for z in dfs_visited:
    print(z,end=' ')

print(sep='\n')

for t in bfs_visited:
    print(t,end=' ')

먼저 그래프를 딕셔너리 안에 키와 리스트를 묶어서 저장하고 싶었다.(값이 저장되어 있으면 구현하기에 수월할것 같아서) 정점의 개수만큼 리스트를 만들고 키값과 함께 저장해준다. 그리고 간선이 연결되어 있는 수를 따라 각 키값에 맞는 리스트에 넣어준다. 그리고 각 리스트를 오름차순으로 정렬한 다음 함수를 구현하였다. dfs는 스택으로 구현하려고 했으나 결과값이 다르게 나오기 때문에 못했고 재귀함수를 이용해 구현하였다. bfs는 큐를 이용해 구현하였다. 출력을 하는데 좀 애먹었는데 깔끔하게 출력할수 있는 방법을 알고싶다... 이렇게 코드가 길고 지저분한데도 제출할때 시간초과가 안뜨고 맞아서 다행이다.

4. 풀이하면서 고민했던 점

클린코드를 구사하기까지 갈길이 멀고도 험하다는 생각을 했다.. 문제를 풀면서도 이 방법이 맞나? 최선인가? 라는 물음을 던지면서 고민이 길어지는것 같다.

5. 문제를 풀고 난 소감

시간 단축이 목표이다.