https://www.acmicpc.net/problem/1238
1238번: 파티
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어
www.acmicpc.net
내 풀이
시도1
def solution():
INF = int(1e9)
n,m,x=map(int,input().split())
time_list=[]
result=[[]]
graph = [[] for _ in range(m+1)]
for _ in range(m):
a,b,c= map(int,input().split())
graph[a].append((b,c))
def get_smallest_node():
min_value = INF
index = 0
for i in range(1, n+1):
if distance[i] < min_value and not visited[i]:
min_value = distance[i]
index = i
return index
def ekdlrtmxmfk(start):
distance[start]=0
visited[start]=1
for j in graph[start]:
distance[j[0]]=j[1]
for _ in range(n-1):
now = get_smallest_node()
visited[now] = True
for j in graph[now]:
cost = distance[now] + j[1]
if cost<distance[j[0]]:
distance[j[0]] = cost
return distance
for i in range(1,n+1):
distance = [INF] * (n+1)
visited = [0] * (n+1)
result.append(ekdlrtmxmfk(i))
for i in range(1, n+1):
time_list.append(result[i][x] + result[x][i])
print(max(time_list))시간초과가 났다. 특정 한 점에서 다른 모든점까지의 거리를 구하는 부분에서 다익스트라는것을 알았지만 단 한번도 다익스트라 문제를 풀면서 heapq를 사용하지 않은적이 없어서 문득 그냥 구현하면 통과가 될까싶어 한번해보았다.
시도2
import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)
def solution():
n,m,x = map(int,input().split())
graph =[[] for _ in range(n+1)]
for _ in range(m):
a,b,c = map(int,input().split())
graph[a].append((b,c))
def ekdlrtmxmfk(start):
q = []
heapq.heappush(q,(0,start))
distance[start] = 0
while q:
dist,now = heapq.heappop(q)
for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]]=cost
heapq.heappush(q,(cost,i[0]))
return distance
result = [[]]
dis =[]
for i in range(1,n+1):
distance= [INF] * (n+1)
result.append(ekdlrtmxmfk(i))
for i in range(1,n+1):
dis.append(result[i][x]+result[x][i])
print(max(dis))
solution()원리는 같은데 heapq를 사용한 방법이다.
다른사람의 풀이
최근에 기사시험을 시작으로 본격적인 취준이 시작되었다. 아직 한학기가 남긴했지만 지원가능한 회사에 꽤나 많이 지원했는데(다행히도 서류는 꽤 많이 붙었다) 저번주부터 코딩테스트가 시작되었다. 18학점을 들어야하는 상황이라 학교 중간고사도 겹치다보니 쉽지않다..
하루에 하나정도는 문제를 꼭 풀어야겠다 + sql도
'취준 > 백준' 카테고리의 다른 글
| 10816(숫자카드 2) - 파이썬 (0) | 2022.10.27 |
|---|---|
| 1806(부분합) - 파이썬 (0) | 2022.10.24 |
| 25755 - 파이썬 (0) | 2022.10.21 |
| 1912(연속합) - 파이썬 (0) | 2022.10.18 |
| 2589(보물섬) - 파이썬 (0) | 2022.09.02 |