[실버 II] 2644번. 촌수계산

 문제 

https://www.acmicpc.net/problem/2644

2644번: 촌수계산

 사용 언어 

Python3

 풀이 과정 

부모 자식간의 관계 그래프를 가지고 촌수를 계산하는 문제였다.

 

나는 처음에 부모: [자식 리스트]와 같은 일방향 그래프를 만들어놓고 자식들 숫자 두 개만 주어지면 어떻게 찾아가지 하는 고민을 했는데, 따라서 자식: [부모 리스트] 그래프도 만들어 양방향 그래프를 만들어주어야 문제를 풀 수 있었다.

 

그래프를 만들 때 처음에는 이중 리스트를 사용했다가 나중에 저번 문제를 통해 공부한  defaultdict 를 적용해봤는데

아래와 같이 시간이 확연히 더 걸리는 것을 확인할 수 있었다.

from collections import defaultdict

...

if __name__ == "__main__":
    n = int(input())
    graph = [[] for _ in range(n+1)]
    graphDict = defaultdict(list)
    s, e = map(int, input().split())
    for _ in range(int(input())):
        u, v = map(int, input().split())
        graphDict[u].append(v)
        graphDict[v].append(u)
    check = [0] * (n+1)
    bfs(s)
    print(check[e] if check[e] > 0 else -1)

어쨌든 BFS를 사용해서 첫 번째 입력값과 모든 그래프 노드들의 촌수 관계 리스트를 만들어 두 번째 입력값 인덱스 값을 확인하는 방법으로 풀었고 맞았습니다!!

 제출 답안 

from sys import stdin
from collections import deque
input = stdin.readline

def bfs(node):
    queue = deque()
    queue.append(node)
    while queue:
        node = queue.popleft()
        for n in graph[node]:
            if check[n] == 0:
                check[n] = check[node] + 1
                queue.append(n)

if __name__ == "__main__":
    n = int(input())
    graph = [[] for _ in range(n+1)]
    s, e = map(int, input().split())
    for _ in range(int(input())):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)
    check = [0] * (n+1)
    bfs(s)
    print(check[e] if check[e] > 0 else -1)

 다른 사람 코드 

뭔가 굉장히 깔끔해보이는 코드를 들고 왔다.

import sys

input = sys.stdin.readline

# Get input.
n = int(input())
s, e = map(int, input().split())
m = int(input())

# Get edge.
edge = [[] for _ in range(n+1)]
for i in range(m):
	a, b = map(int, input().split())
	edge[a].append(b)
	edge[b].append(a)

# Make array for distance and visit.
visit = [0 for _ in range(n+1)]
dist = [-1 for _ in range(n+1)]

#BFS
q = [s]
visit[s] = 1
dist[s] = 0
for here in q:
	for there in edge[here]:
		if not visit[there]:
			visit[there] = 1
			q.append(there)
			dist[there] = dist[here] + 1

#print answer
print(dist[e])

➡ 같은 BFS 알고리즘을 사용했는데 내 코드와 비교했을 때 32ms나 차이난다. 차이점은 다음과 같았다.

1. while문 대신 for문을 사용
2. queue나 deque를 사용하지 않아 pop을 하는 과정이 불필요
3. visit과 dist라는 리스트를 분리하고 -1로 초기화 해서 마지막에 삼항연산자가 불필요

나는 check라는 리스트로 방문 처리까지 한 번에 한 점이 마음에 들었는데 오히려 분리하는게 시간적으로 더 효율적일 수 있다는 것을 깨달았고 while문 안에서 pop하는 방식이 아니라 for문으로 BFS 알고리즘을 구현할 수 있다는 게 놀라웠다...

 

이게 어떻게 가능한지 이해가 안돼서 print를 찍어가며 봤는데 for문 안에서 pop하는 것은 인덱스에 문제가 나지만 append를 하는 것은 그 다음 원소가 되기 때문에 문제가 없나보다. 따라서 for문을 시작할 땐 분명히 q에 2밖에 들어있지 않지만 there을 append 해줌으로써 다음 here이 생기게 되고 for문이 바로 끝나지 않는다.

 

이렇게 구현을 하다니 신기하군!😲