이모저모

문제: https://www.acmicpc.net/problem/1956 이 문제에서 찾아야 하는 최단경로는, 출발지로 돌아와야 하는 순환경로라는 점이 다른 최단거리 구하는 점과 다르다. 처음에는 뭔가 복잡하게 접근할 뻔했는데, 생각해보니 자기 자신으로 오는 거리를 처음에 0으로 초기화하지만 않으면 되는 것이었다. 보통 다른 최단경로문제를 풀 때는 자신에게로 오는 거리를 처음부터 0으로 초기화해서 애초에 다른 아이를 경유하는 경우는 고려도 하지 않았다. 하지만 다른 노드에 대해서와 마찬가지로 INF(매우 큰 수)로 초기화해두면, 다른 노드로 갈 때 경유지를 고려하는 것과 마찬가지의 작업이 자기 자신에 대해서도 일어날 수 있다. + 지금 플로이드 워셜을 공부하던 터라 이 문제를 플로이드 워셜로 풀었지만, ..

이코테 38번 문제 학생 N명에 대한 성적을 분실했는데, 다만 두 명씩 성적을 비교한 결과 M 개가 있다. 예를 들어 1~6번 학생이 있는데, 1 < 5, 3 < 4, ... 이런 식으로 정보가 주어진다. 이 정보들만으로 확실히 성적 순위를 알 수 있는 학생은 몇 명일까? 느낀 점 플로이드 워셜을 최단거리 구하는 데만 사용하다가, 이렇게 살짝 다른 방식(순위 결정)에 적용하려니까 나는 어려웠다.ㅎㅎ 그런데 이 문제를 공부하고 나니까, 플로이드 워셜의 조금 더 본질적인 부분을 살짝 느낄 수 있었던 것 같아서, 개인적으로는 마음에 드는(?) 고마운 문제다!🤓 이 문제에서 필요한 작업은 각 노드가 다른 노드들과 대소비교가 가능한가가를 알아내야 하는 문제였는데, 이때 다른 노드를 매개물로 삼아보는 과정이 필요하..

문제: https://www.acmicpc.net/problem/1753 다익스트라의 전형같은 문제! 코드 import heapq import sys n, m = map(int, sys.stdin.readline().split()) s = int(sys.stdin.readline().rstrip()) # 연결 정보 받아오는 중첩리스트 conn_info = [[] for _ in range(n+1)] for _ in range(m): u, v, w = map(int, sys.stdin.readline().split()) conn_info[u].append((v, w)) # 초기화에 사용/도달불가한 노드 알아볼 큰 수 INF = int(1e12) # 최단거리 테이블 min_dis = [INF] * (n+1)..

- 문제: https://leetcode.com/problems/network-delay-time/ - 코드 class Solution(object): def networkDelayTime(self, times, n, k): # 초기화에 사용할 큰 수 INF = int(1e8) # 각 노드 간 간선과 간선에 해당하는 시간(가중치)에 대한 정보를 2차원 배열에 반영 graph = [[] for _ in range(n+1)] for time in times: graph[time[0]].append((time[1], time[2])) # 각 노드에 이르는 최소시간을 적어놓을 1차원 배열 mins = [INF] * (n+1) def dijkstra(start): # 최소 시간인 경로부터 뽑기 위해 heapq 준..

import heapq import sys n, m = map(int, sys.stdin.readline().split()) con_info = [[] for _ in range(n+1)] for _ in range(m): s, e = map(int, sys.stdin.readline().split()) con_info[s].append(e) con_info[e].append(s) # 출발점에서 각 노드(헛간)에 이르는 최단거리 테이블 준비 (INF 로 초기화) INF = int(1e9) min_dis = [INF] * (n+1) min_dis[1] = 0 # 해당 시점마다 출발지로부터 가장 가까운 노드들을 가져와서, 그 노드를 경유하는 루트를 고려할 것 # 가까운 것부터 가져오기 위해 최소힙 사용 qu..

1. 문제 2. 코드 import heapq import sys # n X n 의 탐사 지형(?) 정보 받아와서 2차원 배열로 그리기 n = int(sys.stdin.readline().rstrip()) graph = [[] for _ in range(n)] for i in range(n): row = list(map(int, sys.stdin.readline().split())) graph[i] = row # 초기화에 사용할 큰 수 INF = int(1e9) # 아직 접근 가능한 좌표와 경로 전혀 취하지 않았으니까 모든 좌표는 큰 수로 초기화, 시작점은 자신의 칸에서의 소모량으로 초기화 consumption = [[INF] * n for _ in range(n)] consumption[0][0] = g..