https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 1, 양방향이고 최대치를 sys.maxsize로 잡아서 문제의 제한사항으로부터 자유로워 졌다. 2, 똑같은 다익스트라문제이지만 무조건 마지막에 주어진 두 정점을 지나야하기때문에 시작값이 매개변수로 주어진 다익스트라 함수를 만들어서 경로 1 - num1 - num2 - n 이랑 1 - num2 - num1 - n을 비교해준다. # 1504번 특정한 ..

https://www.acmicpc.net/problem/14284 14284번: 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. www.acmicpc.net 풀이 1, 양방향이며 최대치는 5억이기에 INF는 10억으로 잡아주었다. 2, 다익스트라 적용 # 14284번 간선 이어가기 2 import heapq import sys input = sys.stdin.readline INF = int(1e9) def dijkstra(start, target): q = [] # heapq.heappush(dist, node) heapq.heappush(q,..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 풀이 1, 양방향 문제이다. INF는 10억이기에 int(1e9)로 해주었다. 2, 다익스트라 적용 # 1916번 최소비용 구하기 import heapq import sys input = sys.stdin.readline INF = int(1e9) def dijkstra(start, target): q = [] # heapq.heappush(dist, node) ..

https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 풀이 1, 단방향인것을 주의해서 문제를 풀어주길 바란다. 최대치 또한 고려해서 INF를 sys.maxsize로 고쳐주었다. 2, 다익스트라 적용 # 5972번 택배 배송 import sys import heapq input = sys.stdin.readline INF = sys.maxsize def dijkstra(target): q = [] heapq.heappush(q, (0, 1)) distance[..

https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 풀이 다익스트라 알고리즘 사용해서 풀 수 있는 문제이다. 1 , 이 문제에서 최대는 300억이 나오기에 INF 설정에 주의를 해야한다. 아래 코드에서는 INF를 1000억으로 구성했다. 코드가 더럽지 않게 리스트로 간단히 만들어서 인덱스 비교로 간선 처리를 하려했으나 집합으로 처리해보고 싶어서 처리했다. INF가 무엇인지 모르겠다면 본 블로그 알고리즘을 참고해주세요. 2..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 최단경로를 찾기 위해서는 2*X의 위치로 이동하는 경우는 우선 순위로 처리해줄 수 있게해야한다. appendleft( ) 메서드로 덱의 앞쪽으로 둬서 우선처리해준다. 그 이후는 목표값을 구할 때 까지 구해준다. # 13549번 숨바꼭질 3 # 이동방향 [x+1, x-1, 2*x] 대신 시간소모는 [+1, +1, 0]이다. # 가장 빠른시간. from coll..

https://www.acmicpc.net/problem/2506 2506번: 점수계산 OX 문제는 맞거나 틀린 두 경우의 답을 가지는 문제를 말한다. 여러 개의 OX 문제로 만들어진 시험에서 연속적으로 답을 맞히는 경우에는 가산점을 주기 위해서 다음과 같이 점수 계산을 하기로 www.acmicpc.net 풀이 단순한 그리디 문제이기에 풀어주면 됩니다. # 2506번 점수계산 T = int(input()) score = list(map(int, input().split())) cnt = 0 # 연속된 점수일 경우 더해준다. answer = [] for i in score: if i == 1: answer.append(1 + cnt) cnt += 1 elif i == 0: answer.append(0) c..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 # 7562번 나이트의 이동 # 배열의 크기는 가로, 세로가 I. 시작점, 목표점이 주어짐, 이동방향은 나이트의 이동 8개 # bfs는 최적의 수를 주기에 visited 안에서 이동할때마다 1씩 추가해준다. import sys from collections import deque input = sys.stdin.readline dx = [2, 2, -2, -2, -1, 1, -1, 1] dy ..