[백준] 21278번 호석이 두 마리 치킨 Python (BFS풀이, 플로이드워셜)

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

21278번: 호석이 두 마리 치킨

 

<1_ BFS 풀이 >

1. 치킨집을 두개 지정해주어야 한다. 이를 combination을 이용하여 간단히 구현했다. 

2. 치킨집 2개를 뽑는 모든 조합을 brute force로 확인한다. 그리고 왕복거리가 최소가 되는 경우를 구한다. 

3. bfs는 치킨집 2개를 start node라고 가정하고, 치킨집에서 각각의 노드들을 방문하며 왕복거리를 계산했다. 

4. answer 를 sort해서 가장 노드 번호 조합이 작은것을 답으로 출력한다. 

난 당연히 bfs밖에 떠올리지 못했는데 플로이드-워셜로 정석적으로 푸는 것 같았다 

from itertools import combinations
from collections import deque

n, m = map(int, input().split())
graph = [[]*(n+1) for _ in range(n+1)]
node = [i for i in range(1, n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a) # 양방향 그래프


answer = []
total = int(1e9)
# 치킨집 2곳은 combination 으로 선정하기
def bfs(chicken):
    global total, answer
    visited = [False] * (n+1)
    queue = deque()
    start1, start2 = chicken
    queue.append([start1, 0])
    queue.append([start2, 0])
    visited[start1] = True
    visited[start2] = True
    distance = [0] * (n+1)
    while queue:
        now, cost = queue.popleft()
        # 왕복거리
        if distance[now] == 0:
            distance[now] = cost*2 # 왕복이므로 2배
        for i in graph[now]:
            if not visited[i]:
                visited[i] = True
                queue.append([i, cost+1])
    if sum(distance) < total:
        answer = []
        answer.append([start1, start2, sum(distance)])
        total = sum(distance)
    elif sum(distance) == total:
        answer.append([start1, start2, sum(distance)])

comb = list(combinations(node, 2))
for c in comb:
    bfs(c)
answer.sort()
print(*answer[0])

<2_ 플로이드 워셜>

1. 인접 그래프를 초기화한다. a <-> b 사이의 거리는 1이라고 설정한다. 

INF = int(1e9)
graph = [[INF]*(n+1) for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1 # a와 b사이의 거리
    graph[b][a] = 1

2. 플로이드 워셜로 각 node 들 사이의 최단거리를 모두 구해서 저장해둔다. 

for k in range(1, n+1):
    graph[k][k] = 0  # 자기자신 -> 자기자신 : 0
    for i in range(1, n+1):
        for j in range(1, n+1):
            graph[i][j] = min(graph[i][k] + graph[k][j], graph[i][j])

3. brute force 방법으로 치킨집을 2개 설정해준다 

# 치킨집 2개 골라서 브루트 포스로 확인하기
for i in range(1, n+1):
    for j in range(i, n+1):
        cost = 0
        for k in range(1, n+1): # k번쨰 정점에서 i or j 둘중 가까운 치킨집 방문
            cost += min(graph[k][i], graph[k][j])
        if total > cost*2:
            total = cost*2
            answer = [i, j, cost*2]

설정한 치킨집을 기준으로 k번쨰 정점에서 둘 중 가까운 치킨집을 방문했을 때의 거리를 계산한다. 

왕복거리가 total (현재 최소값) 보다 작은 경우 answer 와 total을 갱신한다. 

 

전체 코드 

# 호석이 두마리 치킨 ~~

n, m = map(int, input().split())
INF = int(1e9)
graph = [[INF]*(n+1) for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1 # a와 b사이의 거리
    graph[b][a] = 1

# 플로이드 워셜 : 각 건물사이의 최단 거리

for k in range(1, n+1):
    graph[k][k] = 0  # 자기자신 -> 자기자신 : 0
    for i in range(1, n+1):
        for j in range(1, n+1):
            graph[i][j] = min(graph[i][k] + graph[k][j], graph[i][j])

total = INF 
# 치킨집 2개 골라서 브루트 포스로 확인하기
for i in range(1, n+1):
    for j in range(i, n+1):
        cost = 0
        for k in range(1, n+1): # k번쨰 정점에서 i or j 둘중 가까운 치킨집 방문
            cost += min(graph[k][i], graph[k][j])
        if total > cost*2:
            total = cost*2
            answer = [i, j, cost*2]
print(*answer)

 

플로이드 워셜로 풀었을 때 BFS로 풀이했을 때보다 효율적이다