프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 전형적인 최단 거리 문제.다익스트라 알고리즘을 활용해서 풀었다. 풀이 코드import heapqINF = int(1e9)# 다익스트라(O(ElogV))def dijkstra(start, N, road): q = [] distance = [INF] * (N+1) graph = [[] for _ in range(N+1)] # 데이터 입력 for r in road: a, b, c = r[0], r[1], r[2] graph[a].append((b, c)) ..
최단거리
다익스트라 알고리즘을 이용해 1번 노드 ~ 다른 모든 노드까지의 최단 거리를 구하면 나오는 distance 리스트를 통해 풀 수 있는 문제. 여기서는 각 노드 사이의 거리가 1이기 때문에 BFS를 이용해서도 풀 수 있지만, 다익스트라 알고리즘을 사용하면서 각 노드 사이의 거리를 1로 넣어주면 다익스트라 알고리즘으로도 풀 수 있다. 내 풀이 코드 # 숨바꼭질 import heapq, sys input = sys.stdin.readline INF = int(1e9) n, m = map(int, input().split()) graph = [[] for _ in range(n+1)] # (도착노드, 거리)를 저장하기 위한 리스트 distance = [INF] * (n+1) # 최단거리를 저장하기 위한 리스트 ..
이 문제는 이차원 리스트가 주어졌을 때, (0,0) 위치에서 (N-1,N-1) 위치로 이동하는 최단 거리를 계산하는 문제다. N X N 크기의 맵이 주어졌을 때, 맵의 각 위치(칸)을 노드로 보고, 상하좌우로 모든 노드가 연결되어 있다고 생각하면 된다. dx, dy 리스트를 사용하는 방법 + 다익스트라 알고리즘 구현 방법을 알고 있다면 쉽게 풀 수 있는 문제. 내 풀이 코드 # 화성 탐사 import heapq, sys input = sys.stdin.readline INF = int(1e9) # 최단 거리 탐색 def dijkstra(): q = [] n = int(input()) # 맵 크기 graph = [list(map(int, input().split())) for _ in range(n)] #..
최단 거리 문제이다. 책 풀이는 플로이드-워셜 알고리즘을 활용해서 풀었으나, 나는 다익스트라 알고리즘 같은 느낌의 알고리즘을 사용해서 풀었다. 내 풀이 # 정확한 순위 import sys, heapq input = sys.stdin.readline INF = int(1e9) n, m = map(int, input().split()) # n은 학생 수, m은 두 학생의 성적을 비교한 횟수 graph = [[] for _ in range(n+1)] connected = [[False] * (n+1) for _ in range(n+1)] # connected[i][j] = i->j로 연결되어 있는지 여부를 저장 # 성적 비교 입력 for _ in range(m): a, b = map(int, input().s..
37_플로이드 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 happenundo.tistory.com
11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-워셜 알고리즘을 알고 있다면 쉽게 풀 수 있는 문제. 플로이드-워셜 알고리즘의 시간복잡도는 O(V^3)인데, 도시 개수가 최대 100개이므로 시간 복잡도도 만족한다. 단, 이 문제에서는 추가된 조건들이 있다. 1. 시작도시와 도착도시가 연결된 노선은 하나가 아닐 수 있다. 2. 마지막에 최단 거리를 출력할 때, 갈 수 없는 경우에는 0을 출력한다. 1번 조건을 만족하기 위해, 이차원 리스트에 거리를 입력할 때, 입력받은 거리가 원래 입력되어 있는 거리보다..
