전체 글625 [파이썬, 자바] 백준 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. [파이썬] 백준 2458 : 키 순서 (골드4) [파이썬] 백준 2458 : 키 순서 (골드4)https://www.acmicpc.net/problem/2458풀이방향성 생각node X에서 BFS를 진행하면 자기보다 확실히 키가 큰 사람이 몇 명 있는지 구할 수 있다.역방향 간선을 G_rev에 저장하고 BFS를 진행하면 확실히 키가 작은 사람이 몇 명 있는지 알 수 있다.BFS(node, graph) -> V로 T/F를 저장해서 리턴한다.sum(V)로 방문체크를 몇 개나 했는지 체크하면 된다.sum(V) + sum(rev_V)가 N-1이 되면 된다. (시작 node는 체크안해도 된다. 체크 할거면 중복때문에 N+1) 전체코드from collections import dequeimport sysinput = lambda : sys.stdin.readli.. 2025. 2. 18. 이전 1 ··· 5 6 7 8 9 10 11 ··· 157 다음
