알고리즘 - Python / 백준 - 14217번 : 그래프 탐색

14217번: 그래프 탐색 (acmicpc.net)

14217번: 그래프 탐색

 

---

풀이

• 간선을 제거하고 추가하면서 그 상황에서 root 로부터 다른 노드까지의 최단 거리를 구하는 문제다.
• 그래프 탐색 문제이면서 최단 거리 문제 이므로 단순하게 bfs로 구현하기로 하였다.
• 평소 스타일 대로 bfs를 사용해 풀었더니 , 시간 초과가 나왔다. ( 해당 코드 첨부 )
• 예제는 문제가 없었기에 방문할 노드를 체크할 때 시간이 오래 걸렸나 생각했다.

 

첫 번째 코드

• 첫 번째 코드에서는 2차원 배열을 통해 C[출발 노드][도착 노드] 가 1이면 간선 존재 , 0 이면 간선 없음으로 두었다.
• 이후 for 문으로 해당 출발 노드의 행 혹은 열을 모두 훑으면서 찾았다.
• 이 경우 방문하지 않는 노드도 검사해 비 효율 적이라 생각해 다른 방식으로 해당 부분을 바꾸었다.

 

두 번째 코드

• 첫 번째 코드의 간선 기록 방식을 C[출발노드].append(방문할 노드) 로 바꾸었다.
• 이 경우 최악의 경우 ( 모든 노드들과 연결된 경우 ) 첫번째 코드와 같을 것이고 , 최소 손해는 보지 않는다 생각했다.
• 이러한 방식으로도 시간 초과가 발생하였고 다른 부분에서 문제를 찾아야 했다.

 

정답 코드

• 천천히 코드에서 시간을 잡아먹을 만한 메소드나 함수들을 살펴보았다.
• 보이는 함수들은 append() , pop() , remove() 정도였다.
• 이를 보고 pop()에서 시간 초과가 일어났다는 것을 눈치챘다.
• pop()의 일반적인 경우 맨 끝만 빼면 O(1)로 가능하지만 , pop(0)의 경우 맨 앞을 빼주고 앞의 것들을 한 칸씩 당겨주어야 하기 때문에 O(N)의 시간 복잡도가 걸린다.
• remove()의 경우도 O(N)이지만 , 이 문제에서는 그렇게 많은 remove() 연산을 수행하지는 않는다.
• 따라서 리스트의 pop(0)을 collections의 deque의 popleft를 사용하여 시간 초과를 해결하였다.
• deque는 Double ended Queue로 더블 링크드 자료구조이므로 좌 우 삽입 , 제거에서 O(1)의 시간으로 해당 연산이 가능하다.
• 이런 기초적인 부분에서 실수가 나는 걸 보면 아직 갈길이 먼 듯하다...

 

 

#첫번째 코드 - 시간초과

import sys
n,m = map(int , sys.stdin.readline().split(" "))
c = [[0 for i in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int , sys.stdin.readline().split(" "))
    c[a][b] = 1; c[b][a] = 1

def bfs():
    global n; global c
    visited = [-1 for i in range(n+1)]
    root = [[1,0]]
    while root:
        pops = root.pop(0)
        if visited[pops[0]] == -1:
            visited[pops[0]] = pops[1]
            for i in range(1,n+1):
                if c[i][pops[0]] == 1 and visited[i] == -1:
                    root.append([i,pops[1]+1])
    return visited

k = int(sys.stdin.readline())
for _ in range(k):
    a, ct1 , ct2 = map(int, sys.stdin.readline().split(" "))
    if a == 1:
        c[ct1][ct2] = 1; c[ct2][ct1] = 1
    else:
        c[ct1][ct2] = 0; c[ct2][ct1] = 0
    ans = bfs()
    print(0, end=" ")
    for i in range(2,n):
        print(ans[i] ,end=" ")
    print(ans[n])

 

 

 

#두번쨰 코드 - 시간초과

import sys
n,m = map(int , sys.stdin.readline().split(" "))
c = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int , sys.stdin.readline().split(" "))
    c[a].append(b); c[b].append(a)

def bfs():
    global n; global c
    visited = [-1 for _ in range(n+1)]
    root = [[1,0]]
    while root:
        pops = root.pop(0)
        if visited[pops[0]] == -1:
            visited[pops[0]] = pops[1]
            for i in c[pops[0]]:
                if visited[i] == -1:
                    root.append([i,pops[1]+1])
    return visited

k = int(sys.stdin.readline())
for _ in range(k):
    a, ct1 , ct2 = map(int, sys.stdin.readline().split(" "))
    if a == 1:
        c[ct1].append(ct2); c[ct2].append(ct1)
    else:
        c[ct1].remove(ct2); c[ct2].remove(ct1)
    ans = bfs()
    print(0, end=" ")
    for i in range(2,n):
        print(ans[i] ,end=" ")
    print(ans[n])

 

 

 

#세번째 코드 - 정답

import sys
from collections import deque
n,m = map(int , sys.stdin.readline().split(" "))
c = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int , sys.stdin.readline().split(" "))
    c[a].append(b); c[b].append(a)

def bfs():
    global n; global c
    visited = [-1 for _ in range(n+1)]
    root = deque([[1,0]])
    while root:
        pops = root.popleft()
        if visited[pops[0]] == -1:
            visited[pops[0]] = pops[1]
            for i in c[pops[0]]:
                if visited[i] == -1:
                    root.append([i,pops[1]+1])
    return visited

k = int(sys.stdin.readline())
for _ in range(k):
    a, ct1 , ct2 = map(int, sys.stdin.readline().split(" "))
    if a == 1:
        c[ct1].append(ct2); c[ct2].append(ct1)
    else:
        c[ct1].remove(ct2); c[ct2].remove(ct1)
    ans = bfs()
    print(0, end=" ")
    for i in range(2,n):
        print(ans[i] ,end=" ")
    print(ans[n])

 

 

---