https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 단순하게 벽을 부수는 횟수를 카운트 하다가 오답이 계속 나왔는데 이를 해결하기 위해서 새로 탐색하는 칸이 벽인 경우와 통로인 경우의 가중치를 다르게 주어야 한다. 1) 통로 : 벽을 부수지 않아도 통과하여 이동할 수 있으므로 가중치가 높다. 덱 (deque) 의 앞쪽으로 밀어넣는다 2) 벽 : 벽을 부수어야 하므로 가중치가 낮다. 덱 (deque) 의 뒤쪽으로 밀어넣는다 # ..
다익스트라
https://www.acmicpc.net/problem/22865 22865번: 가장 먼 곳 $N$개의 땅 중에서 한 곳에 자취를 하려고 집을 알아보고 있다. 세 명의 친구 $A$, $B$, $C$가 있는데 이 친구들의 살고 있는 집으로부터 가장 먼 곳에 집을 구하려고 한다. 이때, 가장 먼 곳은 선택할 www.acmicpc.net 다익스트라 알고리즘을 이용해서 a, b, c로부터 모든 지점까지의 거리를 구한다. 그 거리들을 담아 놓은 리스트가 dist_a, dist_b, dist_c이다. for i in range(1, n+1): if max_dist < min(dist_a[i], dist_b[i], dist_c[i]): max_dist = min(dist_a[i], dist_b[i], dist_c[..
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 트리도 결국 그래프에 속한다! 라고 생각하면 조금 더 쉽다 모양은 나무처럼 생겨서 이상하지만,, 결국 우리는 1번 노드에서 가장 멀리 떨어진 정점을 찾고, 그 정점에서 가장 멀리 떨어진 정점을 찾아서 두 가중치를 더해주면 최대값이 된다 이 예시에서도 1번에서 가장 떨어진 노드는 9번이다. 이말은 노드 1에서 출발 했을 때 가중치 값이 가장 큰 노드가 9라는 것이다 그후 9번을 ..
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 각 노드들에서 x로 갈때 다익스트라 최단경로 알고리즘을 이용해 최단거리를 구하면 노드 i에서 모든 노드까지의 최단 거리 결과를 알 수 있다. 이 결과값을 나는 최단 거리를 저장하는 리스트 dist라고 두었다. dist[x]값이 바로 학생 i가 파티 주최지 x 노드까지 '가는' 데에 소요되는 최단경로 cost이다. 문제는 왕복을 해야 한다는 것인데, 원래는 구해놓은 최단거리에 2배 곱해주면 되지 않나라고..
import heapq INF = int(1e9) n, m = map(int, input().split()) graph = [[] for _ in range(n+1)] for i in range(m): a, b = map(int, input().split()) graph[a].append((b, 1)) graph[b].append((a, 1)) distance = [INF]*(n+1) start = 1 def dijkstra(start): # 다익스트라 q = [] heapq.heappush(q, (0, start)) distance[start] = 0 while q: dist, now = heapq.heappop(q) if dist > distance[now]: continue for i in grap..
