[백준][python]호석이 두 마리 치킨

문제

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

소스코드 : BFS

import sys
from itertools import combinations
from collections import deque
input = sys.stdin.readline
if __name__ == "__main__":
	# 치킨집부터 각 노드까지 거리를 BFS를 이용해서 탐색하기
    n,m = map(int,input().split())
    tree = [[] for _ in range(n+1)] # 트리 만들기
    for _ in range(m):
        a,b = map(int,input().split())
        tree[a].append(b) #양방향 트리
        tree[b].append(a)

    cases = list(combinations([i for i in range(1,n+1)],2)) #조합으로 치킨집을 만들 수 있는 노드 체크

    res = [10**6,0,0] #결과, node1, node2

    for case in cases: # 치킨집을 세운 경우의 수를 모두 돌면서 정답을 찾는다.
        node1,node2 = case
        visited = [False for _ in range(n+1)]
        visited[node1] = True #초기 치킨집은 방문하지 않음
        visited[node2] = True #초기 치킨집은 방문하지 않음
        
        q = deque()
        q.append([node1,0]) #치킨집의 위치 , 치킨집까지의 거리
        q.append([node2,0])
        
        tmp_res = 0 #치킨집에서 각 집까지 걸린 이동 거리 누적
        
        while q: #탐색 시작
            cur_node, cnt = q.popleft()
            for next_node in tree[cur_node]: 
                if not visited[next_node]:
                    visited[next_node] = True
                    tmp_res += cnt + 1
                    q.append([next_node,cnt+1])

        if tmp_res * 2 < res[0]: #왕복 거리가 이전에 계산해놨던 최소값보다 작으면 정답 변경
            res[0] = tmp_res * 2
            res[1] = node1
            res[2] = node2
    print(f"{res[1]} {res[2]} {res[0]}")

 

소스코드2 : 플로이드와샬

import sys
from itertools import combinations
input = sys.stdin.readline

if __name__ == "__main__":
    n,m = map(int,input().split())
    INF = int(1e9)
    # 정점에서 정점으로 가는 거리 무한으로 초기화
    res = [[INF] * (n + 1) for _ in range(n + 1)]
    # 입력받은 값은 1로 초기화
    for _ in range(m):
        a,b = map(int,input().split())
        res[a][b] = 1
        res[b][a] = 1

    # 자기 자신은 0으로 초기화
    for i in range(1,n+1):
        for j in range(1,n+1):
            if i == j:
                res[i][j] = 0

    #1. 모든 정점에서 모든 정점으로 가는 최소값 구하기 (플로이드 와샬)
    for k in range(1,n+1): # 경유 노드
        for i in range(1,n+1): # 출발 노드
            for j in range(1,n+1): # 도착 노드
                res[i][j] = min(res[i][j], res[i][k] + res[k][j]) #곧장 가는 값과 경유해서 가는 값 중 최소값으로 초기화

    #2. 노드 2개 정해서 가장 최소값을 찾기
    cases = list(combinations([i for i in range(1,n+1)],2)) #치킨집 경우의 수
    ans_sum = INF
    ans_node = [0,0]
    for case in cases:
        node1,node2 = case
        tmp_sum = 0
        for i in range(1,n+1): #도착 노드 체크
            if i == node1 or i == node2: #치킨집은 탐색 안함
                continue
            tmp_sum += min(res[node1][i], res[node2][i]) #거리 누적

        if ans_sum > tmp_sum * 2:
            ans_sum = tmp_sum * 2
            ans_node[0] = node1
            ans_node[1] = node2

    print(ans_node[0],ans_node[1],ans_sum)

설명

문제에서 "모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합" 을 구하라고 되어있다. 이 말 자체가 플로이드 와샬의 정의이다.

N이 100이하 이기 때문에 플로이드 와샬을 사용하면 시간 복잡도가 O(N^3)이지만 충분하다고 판단해서 풀어보았다.

 

1. 플로이드 와샬로 모든 노드에서 모든 노드로 가는 최단 거리를 구해준다.

2. 행을 치킨집이라고 생각하고 열을 도착 아파트라고 생각해서 for문을 한번만 돌려서 거리를 계산해준다.

 

BFS로 탐색하는 것 보다 시간이 5배 절약된다.