본문 바로가기

Algorithm475

[파이썬] 백준 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.
[파이썬, 자바] 백준 4485 : 녹색 옷 입은 애가 젤다지? (골드4) [파이썬, 자바] 백준 4485 : 녹색 옷 입은 애가 젤다지? (골드4)https://www.acmicpc.net/problem/4485풀이방향성 생각다익기본배열로 이동할 때, 간선 대신 배열에 저장된 값을 간선 가중치라고 생각해서 풀이한다. 파이썬import sysimport heapq as hqinput = lambda : sys.stdin.readline().strip()inside = lambda x,y: 0자바import java.io.*;import java.util.*;public class Main { static int N; static int[][] arr; static int[][] dires = {{1,0},{0,1},{-1,0},{0,-1}}; static .. 2025. 2. 17.

티스토리툴바