문제 바로가기
문제:
컴공 출신은 치킨집을 하게 되어있다. 현실을 부정하지 말고 받아들이면 마음이 편하다. 결국 호석이도 2050년에는 치킨집을 하고 있다. 치킨집 이름은 "호석이 두마리 치킨"이다. 이번에 키친 도시로 분점을 확보하게 된 호석이 두마리 치킨은 도시 안에 2개의 매장을 지으려고 한다. 도시는 N 개의 건물과 M 개의 도로로 이루어져 있다. 건물은 1번부터 N번의 번호를 가지고 있다. i 번째 도로는 서로 다른 두 건물 Ai 번과 Bi 번 사이를 1 시간에 양방향으로 이동할 수 있는 도로이다. 키친 도시에서 2개의 건물을 골라서 치킨집을 열려고 한다. 이 때 아무 곳이나 열 순 없어서 모든 건물에서의 접근성의 합을 최소화하려고 한다. 건물 X 의 접근성은 X 에서 가장 가까운 호석이 두마리 치킨집까지 왕복하는 최단 시간이다. 즉, "모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합"을 최소화할 수 있는 건물 2개를 골라서 치킨집을 열려고 하는 것이다. 컴공을 졸업한 지 30년이 넘어가는 호석이는 이제 코딩으로 이 문제를 해결할 줄 모른다. 알고리즘 퇴물 호석이를 위해서 최적의 위치가 될 수 있는 건물 2개의 번호와 그 때의 "모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합"을 출력하자. 만약 이러한 건물 조합이 여러 개라면, 건물 번호 중 작은 게 더 작을수록, 작은 번호가 같다면 큰 번호가 더 작을수록 좋은 건물 조합이다.
입력:
첫 번째 줄에 건물의 개수 N과 도로의 개수 M 이 주어진다. 이어서 M 개의 줄에 걸쳐서 도로의 정보 Ai , Bi 가 공백으로 나뉘어서 주어진다. 같은 도로가 중복되어 주어지는 경우는 없다. 어떤 두 건물을 잡아도 도로를 따라서 오고 가는 방법이 존재함이 보장된다.
출력:
한 줄에 건물 2개가 지어질 건물 번호를 오름차순으로 출력하고, 그때 모든 도시에서의 왕복 시간의 합을 출력한다. 만약 건물 조합이 다양하게 가능하면, 작은 번호가 더 작은 것을, 작은 번호가 같다면 큰 번호가 더 작은 걸 출력한다.
풀이:
부분성공
import sys
from collections import deque
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n, m = map(int, sys.stdin.readline().split()) # 건물 n, 도로 m
graph = [[] * (n + 1) for _ in range(n + 1)]
for i in range(m):
x,y = map(int,sys.stdin.readline().rstrip().split())
graph[x].append(y)
graph[y].append(x)
def bfs(node1,node2):
Q = deque()
Q.append([node1,0])
Q.append([node2,0])
visited[node1] = True
visited[node2] = True
while Q:
node, depth= Q.popleft()
if scores[node] == 10000000:
scores[node] = min(scores[node],depth * 2)
for next_node in graph[node]:
if not visited[next_node]:
visited[next_node] = True
Q.append([next_node, depth+1])
# 모든 노드를 방문하면서 깊이 * 2를 기록한다.
cases_score.append([node1,node2,scores[1::]])
cases_score = []
scores = [10000000 for _ in range(n+1)]
chi = []
for i in range(1, n):
for j in range(i+1, n+1):
visited = [False for _ in range(n+1)]
bfs(i,j)
res = [[x,y,sum(z)] for x,y,z in cases_score]
res.sort(key = lambda x:-x[2])
print(res[0][0],res[0][1],res[0][2])
for 문으로 조합을 만들어주고 치킨집 2개 를 찾아준다.
노드를 방문해주면서 최솟값으로 바꿔준다.
근데 절반정도만 맞는다.
알고보니 무슨 플로이드 - 와샬 알고리즘을 사용한다고 한다.
import sys
n, m = map(int, sys.stdin.readline().split()) # 건물 n, 도로 m
INF = int(1e9)
graph = [[INF] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
a, b = map(int, sys.stdin.readline().split())
graph[a][b] = 1
graph[b][a] = 1
# 자기 자신은 초기화
for a in range(1, n + 1):
for b in range(1, n + 1):
if a == b:
graph[a][b] = 0
# 1. 모든 정점에서 모든 정점으로 가는 최소 거리 구하기
for k in range(1, n + 1):
for a in range(1, n + 1): # 출발 노드
for b in range(1, n + 1): # 도착 노드
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
min_sum = INF
result = list()
for i in range(1, n): # 건물 2개를 뽑는다.
for j in range(i+1, n + 1):
sum_ = 0
for k in range(1, n + 1): # 모든 집을 방문하면서 거리를 측정
sum_ += min(graph[k][i], graph[k][j]) * 2 # k -> i, k -> j 중에 짧은 거리 합치기
if sum_ < min_sum:
min_sum = sum_
result = [i, j, sum_]
print(*result)이 코드인, 플로이드 - 와샬 알고리즘에 대해 공부해야겠다.
댓글