40_숨바꼭질

다익스트라 알고리즘을 이용해 1번 노드 ~ 다른 모든 노드까지의 최단 거리를 구하면 나오는 distance 리스트를 통해 풀 수 있는 문제.

여기서는 각 노드 사이의 거리가 1이기 때문에 BFS를 이용해서도 풀 수 있지만, 다익스트라 알고리즘을 사용하면서 각 노드 사이의 거리를 1로 넣어주면 다익스트라 알고리즘으로도 풀 수 있다.

 

---

내 풀이 코드

 

# 숨바꼭질
import heapq, sys
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)] # (도착노드, 거리)를 저장하기 위한 리스트
distance = [INF] * (n+1) # 최단거리를 저장하기 위한 리스트

# 노드 연결
for _ in range(m):
    a, b = map(int, input().split())
    # 양방향 연결 및 거리는 1
    graph[a].append((b, 1))
    graph[b].append((a, 1))


def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        # 이미 처리된 적 있는 노드면 무시
        if distance[now] < dist:
            continue

        # 현재 노드와 연결된 다른 인접한 노드 확인
        for i in graph[now]:
            cost = dist + i[1]
            # 현재 노드를 거쳐서 다른 인접한 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))


# 다익스트라 알고리즘 실행
dijkstra(1)

# (번호, 거리)로 저장된 distance 리스트
new_distance = list(zip(range(1, n+1), distance[1:]))

new_distance.sort(key = lambda x: (-x[1],x[0])) # 거리 내림차순 배열, 번호 오름차순 배열

max_node = new_distance[0][0] # 숨어야 하는 헛간 번호
max_distance = new_distance[0][1] # 그 헛간까지의 거리
max_count = len(list(filter(lambda x: x[1] == max_distance, new_distance))) # 그 헛간과 같은 거리를 갖는 헛간의 개수

print(max_node, max_distance, max_count)

 

---

 

나는 다익스트라 알고리즘을 수행한 후, 주어진 값들을 구할 때, 파이썬 내장 zip, filter함수를 사용해서 풀었지만, 사용하지 않고, 더 쉽게 풀 수 있는 방법도 있다.

 

.....


# (번호, 거리)로 저장된 distance 리스트
new_distance = list(zip(range(1, n+1), distance[1:]))

new_distance.sort(key = lambda x: (-x[1],x[0])) # 거리 내림차순 배열, 번호 오름차순 배열

max_node = new_distance[0][0] # 숨어야 하는 헛간 번호
max_distance = new_distance[0][1] # 그 헛간까지의 거리
max_count = len(list(filter(lambda x: x[1] == max_distance, new_distance))) # 그 헛간과 같은 거리를 갖는 헛간의 개수

print(max_node, max_distance, max_count)

이 부분의 코드를

 

max_node = 0
max_distance = 0
result = []

for i in range(1, n+1):
    if max_distance < distance[i]:
        max_distance = distance[i]
        max_node = i
        result = [max_node]
    elif max_distance == distance[i]:
        result.append(i)

print(max_node, max_distance, len(result))

이렇게 바꿀 수 있다.

 

이렇게 구현하면 보는 사람이 이해하기 더 쉽다!