본문 바로가기

Algorithm475

[파이썬, 자바] 백준 9370 : 미확인도착지 (골드2) [파이썬, 자바] 백준 9370 : 미확인도착지 (골드2)https://www.acmicpc.net/problem/9370풀이방향성 생각state 기반 / 다익스트라 여러 번 사용하기후자 풀이는 그냥 풀면 되니까...첫 풀이는 state 기반으로 접근힙에다가 (시간,노드,상태)를 넣고 지나야 하는 간선을 지난 경우에 상태값을 변화시켜서 풀이.방문 배열도 2차원으로 V[미방문 / g->h / h->g][노드 수] 이런식으로 방문했는데, 상태가 변하면서 최단거리로 이동하지 않는 문제가 발생.질문게시판에 간선 가중치를 2배로 바꿔주고 특정 간선에만 가중치를 -1로 빼서 다익스트라 사용 시, 후보 노드에 홀수 기록 시 해당 간선을 지났음을 확인하는 아이디어가 있어서 해당 풀이 사용 파이썬import heapq .. 2025. 2. 2.
[파이썬, 자바] 백준 5972 : 택배 배송 (골드5) [파이썬, 자바] 백준 5972 : 택배 배송 (골드5)https://www.acmicpc.net/problem/5972풀이방향성 생각그냥 기본 다익 파이썬import heapq as hqimport sysinput = lambda : sys.stdin.readline().rstrip()INF = sys.maxsizeN,M = map(int,input().split())G = [[] for _ in range(N+1)]for _ in range(M): a,b,cost = map(int,input().split()) G[a].append((b,cost)) G[b].append((a,cost))V = [INF]*(N+1)V[1] = 0heap = [(0,1)]while heap: t,x.. 2025. 2. 1.
[파이썬, 자바] 백준 1012 : 유기농 배추 (실버2) [파이썬, 자바] 백준 1012 : 유기농 배추 (실버2)https://www.acmicpc.net/problem/1012풀이방향성 생각배추 찾으면 BFS 돌리기BFS 돌린 횟수 카운팅해서 출력하기. 파이썬from collections import dequeimport sysinput = lambda : sys.stdin.readline().rstrip()inside = lambda x,y : 0테케 받아서 BFS 돌리기자바import java.io.*;import java.util.*;public class Main { public static int T, H, W, K; public static int[][] dire = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; .. 2025. 1. 31.
[파이썬] 백준 23286 : 허들 넘기 (골드3) [파이썬] 백준 23286 : 허들 넘기 (골드3)https://www.acmicpc.net/problem/23286풀이방향성 생각현재까지 통과한 간선 중 최대값을 힙에 담아서 다익스트라. 전체코드파이썬import heapq as hqimport sysinput = lambda : sys.stdin.readline().rstrip()INF = sys.maxsizeN,M,T = map(int,input().split())G = [[] for _ in range(M+1)]for _ in range(M): a,b,cost = map(int,input().split()) G[a].append((b,cost))def di(start): V = [INF]*(M+1) V[start] = 0 .. 2025. 1. 21.

티스토리툴바