[python] 이코테 - 숨바꼭질

출처 : 이것이 취업을 위한 코딩테스트다 with Python, 숨바꼭질

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

다익스트라 풀이 

 

import sys
from collections import Counter
from heapq import heappop, heappush

INF = float('inf')

def solution(n, pass_list):
    #1번으로부터 최단 거리가 가장 먼 노드를 찾음.

    ad_matrix = [[INF for _ in range(n)] for _ in range(n)]

    # 인접 행렬 초기화
    for h1, h2 in pass_list:
        ad_matrix[h1 - 1][h2 - 1] = 1
        ad_matrix[h2 - 1][h1 - 1] = 1

    min_dis = [INF for _ in range(n)]
    heap = []
    visited_set = set()

    heappush(heap, (0, 0))
    min_dis[0] = 0

    while len(heap) > 0:
        current_dis, node_idx = heappop(heap)

        if node_idx in visited_set:
            continue

        visited_set.add(node_idx)

        # 인접한 노드를 찾아 최소 거리 갱신
        for near_node_idx in range(n):
            near_node_dis = ad_matrix[node_idx][near_node_idx]

            if near_node_dis == INF:
                continue

            # 인접하다면, 최소 거리 갱신
            min_dis[near_node_idx] = min(min_dis[near_node_idx], current_dis + near_node_dis)

            # 우선순위 큐에 넣음
            heappush(heap, (min_dis[near_node_idx], near_node_idx))

    # 가장 거리가 먼 노드를 찾음.
    counting_dis = Counter(min_dis)
    max_dis, node_idx = sorted([(min_dis[i], i) for i in range(n)], key = lambda x: (-x[0], x[1]))[0]

    return (node_idx + 1, max_dis, counting_dis[max_dis])

n, m = map(int, input().split())
pass_list = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(m)]

print(solution(n, pass_list))

 

BFS 풀이

 

이 문제는 가중치가 없는 그래프에서 최단 거리를 찾는 문제이다.

따라서, BFS로도 풀 수 있다.

다익스트라와 다른 점은 다익스트라는 최소 거리가 바로 나오지만,

BFS는 최소 거리를 BFS의 층을 계산해 간접적으로 구해야한다.

 

import sys
from collections import defaultdict, deque, Counter
from heapq import heappop, heappush

INF = float('inf')

def solution(n, pass_list):
    # BFS
    ad_list = defaultdict(lambda : [])
    visited_set = set()
    dis_dict = defaultdict(int)

    for h1, h2 in pass_list:
        ad_list[h1].append(h2)
        ad_list[h2].append(h1)

    queue = deque([1])
    visited_set.add(1)

    floor = 0 # 거리
    floor_count = 1 # 거리 n에 해당하는 노드 개수

    while len(queue) > 0:
        current_node = queue.popleft()
        dis_dict[current_node] = floor
        floor_count -= 1

        for near_node in ad_list[current_node]:
            if near_node in visited_set:
                continue

            queue.append(near_node)
            visited_set.add(near_node)

        if floor_count == 0:
            floor += 1
            floor_count = len(queue)

    # 가장 거리가 먼 노드를 찾음.
    counting_dis = Counter(dis_dict.values())
    node_idx, max_dis = sorted(list(dis_dict.items()), key=lambda x: (-x[1], x[0]))[0]

    return (node_idx, max_dis, counting_dis[max_dis])

n, m = map(int, input().split())
pass_list = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(m)]

print(solution(n, pass_list))

---

 

Reference

이것이 취업을 위한 코딩테스트다 with Python

다익스트라