프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.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..
