Algorithm/Graph188 [파이썬] 백준 16118 : 달빛 여우 (골드1) [파이썬] 백준 16118 : 달빛 여우 (골드1)https://www.acmicpc.net/problem/16118풀이방향성 생각늑대 / 여우 따로 Graph를 만들고 풀이 진행.간선은 기본 2배로 만들어주기 (늑대가 현재 빠르게 이동하는지, 느리게 이동하는지에 따라서 cost다익스트라를 따로 돌려주기.늑대의 경우엔 현재 빠르게 달릴 수 있는지, 없는지 fast라는 state를 힙에 같이 넣는다.fast이면 간선 비용이 절반인 cost를 가져오고, fast가 아니면 4배가 된 cost를 가져온다. 전체코드파이썬import sysimport heapq as hqinput = lambda : sys.stdin.readline().strip()INF = float('inf')# 간선 입력받기N,M = map.. 2025. 2. 24. [파이썬, 자바] 백준 1559 : 놀라운 미로 (플레5) [파이썬, 자바] 백준 1559 : 놀라운 미로 (플레5)https://www.acmicpc.net/problem/1559풀이방향성 생각비트 BFS먹은 보물은 bit filed를 이용해서 구현하기.핵심 로직은 열려 있는 문을 %를 이용해서 구현하기.또한, 제자리에 대기하는 로직을 구현하기.제자리에서 대하는 경우, 더미 데이터가 큐에 쌓이는 것을 방지하기 위해 해당 위치의 첫 방문 시점을 t라고 하면 t + 4 미만인 경우까지만 큐에 넣어준다.진행하려는 방향마다 데이터를 삽입하지 않게 하기 위해 stay라는 boolean 변수를 사용.다익스트라로도 구현이 가능하다.다익스트라로 구현하는 경우, 제자리에서 대기하는 로직 대신 각 방향마다 t + wait time을 구현해서 삽입해주면 더 쉽게 구현이 가능하다... 2025. 2. 23. [파이썬] 백준 11657 : 타임머신 (골드4) [파이썬] 백준 11657 : 타임머신 (골드4)https://www.acmicpc.net/problem/11657풀이방향성 생각음수간선이 포함된 벨만 포드문제V-1번의 안정화 과정, 1번의 음수 사이클 탐지를 확인한다. 파이썬import sysinput = lambda : sys.stdin.readline().strip()INF = float('inf')N,M = map(int,input().split())G = [tuple(map(int,input().split())) for _ in range(M)]def bf(sx): V = [INF]*(N+1) V[sx] = 0 for n in range(N): for a,b,cost in G: if V[a] + .. 2025. 2. 19. [파이썬] 백준 1865 : 웜홀 (골드3) [파이썬] 백준 1865 : 웜홀 (골드3)https://www.acmicpc.net/problem/웜홀풀이방향성 생각음수 간선이 포함된 벨만 포드 문제.그래프가 분리되어서 도달하지 못하는지, 아니면 현재 iteration에서 v가 짧아서 도달하지 못하는건지 확인을 해야한다.음수 간선이 아닌 간선은 양방향, 음수 간선은 단방향 간선이다.질문게시판에 에디토리얼(?)이 있으니 확인하면 좋은 문제.그래프가 분리되어서 도달하지 못하는 것을 확인하기 위해, 더미 노드에ㅐ서 모든 노드로 간선을 이어주어서 문제를 풀이한다.visit 배열 업데이트 시, 이 노드가 유효한 노드인지(현재 iteration에서 도달 가능한지) 확인하고 진행한다. 파이썬from collections import defaultdict as d.. 2025. 2. 19. 이전 1 ··· 8 9 10 11 12 13 14 ··· 47 다음
