DFS

python으로 알고리즘을 다시 공부하기 시작했다.

 

- 처음 만든 DFS 코드

# DFS - 깊이 우선 탐색
def make_dict(node):
    return {'node': node}


def make_graph(node, edge):
    graph = [[] for _ in range(node)]  # 연결 리스트 만들기
    for _ in range(edge):
        n, m = map(int, input().split())
        # 작은 순서대로 sorting 해야 되는데ㅠㅠ
        graph[n-1].append(make_dict(m))
        graph[m-1].append(make_dict(n))
    return graph


def DFS(graph, stack, flag):
    while len(stack) != 0:
        top = stack[-1]
        if len(graph[top - 1]) == 0:
            stack.pop()
        else:
            n = graph[top - 1][0]["node"]
            if flag[n-1] == 0:
                flag[n-1] = 1
                stack.append(n)
                print(n)
            else:
                graph[top - 1].pop(0)


N, E = map(int, input().split())
G = make_graph(N, E)
F = [0] * N
S = []

start_point = int(input())
F[start_point-1] = 1  # 방문 완료 처리
S.append(start_point)
print(start_point)

DFS(G, S, F)

 

- 2차로 다듬은 코드

괜히 메모리 한 줄 줄이겠다고 n - 1과 같이 알아보기 힘들고 계산도 어려운 코드는 지양하도록 하자.

8개가 필요하면 9개를 할당 받아서 1~9까지 사용하는 방식으로 바꿨다.

# DFS - 깊이 우선 탐색
# 스택을 이용한 DFS 구현

def make_dict(node):
    return {'node': node}


def make_graph(node, edge):
    graph = [[] for _ in range(node + 1)]  # 연결 리스트 만들기
    for _ in range(edge):
        n, m = map(int, input().split())
        # 작은 순서대로 sorting 해야 되는데ㅠㅠ
        graph[n].append(make_dict(m))
        graph[m].append(make_dict(n))
    return graph


def DFS(graph, stack, visited):
    while len(stack) != 0:
        top = stack[-1]
        if len(graph[top]) == 0:
            stack.pop()
        else:
            n = graph[top][0]["node"]
            if not visited[n]:
                visited[n] = True
                stack.append(n)
                print(n)
            else:
                # 효율을 따져서 다시 만들자..
                graph[top].pop(0)


N, E = map(int, input().split())  # N : 노드 개수, E : 간선 개수
G = make_graph(N, E)  # 그래프 만들기
V = [False] * (N + 1)  # 방문 처리
S = []

start_point = int(input())
V[start_point] = 1  # 방문 완료 처리
S.append(start_point)
print(start_point)

DFS(G, S, V)

 

아직 멀었다. 혼자 DFS를 생각하는 데에 1시간 반은 걸렸다.

다른 사람들 코드랑 비교해서 다듬어야지ㅠㅠ