1260 DFS & BFS

아.. 내꺼 너무 시간이 오래걸린다.

내 코드는 아래와 같다.

from collections import deque

def dfs(graph, v, visited):
    # 현재 vertex를 방문 처리함.
    visited[v] = True
    print(v,end=' ')

    # 이제 탐색 시작
    for i in graph[v] :

        # 만약 방문하지 않은게 참(not)이라면
        if not visited[i] :

            # 그곳을 방문 처리하자.
            dfs(graph,i,visited)


def bfs(graph,start,visited):

    # 현재 위치를 queue에 쌓기
    queue = deque()
    queue.append(start)

    # 방문했다고 기록하기
    visited[start] = True

    # queue 가 더이상 쌓이지 않을때까지 반복
    while queue :
        # queue에서 하나 뽑아.
        v= queue.popleft()
        print(v,end=' ')

        # 주변을 하나씩 탐색하기 시작
        for i in graph[v]:
            # 탐색하려는 곳이 방문하지 않은게 참이면,
            if not visited[i]:
                # 여기는 이제 탐색하러 도착했음. 이제 이녀석의 주변을 방문하기 위해서 queue에 쌓자
                queue.append(i)
                # 도착했으니 True로 .
                visited[i]=True


n,m,v = map(int,input().split())
node_list = [[] for _ in range(n+1)]

for i in range(m):
    # 연결관계 입력 받기
    now_inputs = list(map(int,input().split()))

    # 각 정점마다 연결 관계 나타내기
    extract_first = node_list[now_inputs[0]]
    extract_first.append(now_inputs[1])
    extract_first.sort()
    node_list[now_inputs[0]] = extract_first

    extract_second = node_list[now_inputs[1]]
    extract_second.append(now_inputs[0])
    extract_second.sort()
    node_list[now_inputs[1]] = extract_second

dfs_visited = [False for _ in range(n+1)]
bfs_visited = [False for _ in range(n+1)]
dfs_visited[0] = True

dfs_results = []
bfs_results = []

dfs(node_list,v,dfs_visited)
print()
bfs(node_list,v,bfs_visited)

위 코드는 512ms가 걸렸다.

여기서 다른 사람들의 코드랑 비교했을 때 알게된 점은 다음과 같다.

• list의 요소를 뽑아와서 바로 append() 해서 값을 추가할 수 있다.
• DFS와 BFS는 되게 정형화 되어있는 상태인 듯 하다.

그래서 조금 수정하게 된 코드는 아래와 같고, 총 504ms가 걸렸다.

from collections import deque

def dfs(graph, v, visited):
    # 현재 vertex를 방문 처리함.
    visited[v] = True
    print(v,end=' ')

    # 이제 탐색 시작
    for i in graph[v] :

        # 만약 방문하지 않은게 참(not)이라면
        if not visited[i] :

            # 그곳을 방문 처리하자.
            dfs(graph,i,visited)


def bfs(graph,start,visited):

    # 현재 위치를 queue에 쌓기
    queue = deque()
    queue.append(start)

    # 방문했다고 기록하기
    visited[start] = True

    # queue 가 더이상 쌓이지 않을때까지 반복
    while queue :
        # queue에서 하나 뽑아.
        v= queue.popleft()
        print(v,end=' ')

        # 주변을 하나씩 탐색하기 시작
        for i in graph[v]:
            # 탐색하려는 곳이 방문하지 않은게 참이면,
            if not visited[i]:
                # 여기는 이제 탐색하러 도착했음. 이제 이녀석의 주변을 방문하기 위해서 queue에 쌓자
                queue.append(i)
                # 도착했으니 True로 .
                visited[i]=True


n,m,v = map(int,input().split())
node_list = [[] for _ in range(n+1)]


for i in range(m):
    # 연결관계 만들어주기
    now_inputs = list(map(int,input().split()))
    node_list[now_inputs[0]].append(now_inputs[1])
    node_list[now_inputs[1]].append(now_inputs[0])

for i in range(n+1):
    # 노드를 작은 것부터 방문해주기 위해
    node_list[i].sort()

dfs_visited = [False for _ in range(n+1)]
bfs_visited = [False for _ in range(n+1)]
dfs_visited[0] = True

dfs_results = []
bfs_results = []

dfs(node_list,v,dfs_visited)
print()
bfs(node_list,v,bfs_visited)