본문 바로가기

Algorithm/Graph188

[파이썬] 백준 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.
[파이썬, 자바] 백준 20158 : 사장님 달려가고 있습니다 (플레5) [파이썬, 자바] 백준 20158 : 사장님 달려가고 있습니다 (플레5)https://www.acmicpc.net/problem/20158풀이방향성 생각지문이 조금 애매하다. 테케 3번을 통해서 잘 이해해보자.현재 시간이 t이고 가속도가 a일 때, 가속도가 붙은 방향으로 a+1만큼 이동해야한다.도착 지점에서 진입이 막히는 경우는 nt부터이다.하지만, 도착지점까지 달려나갈 때 진입이 막히는 경우는 nt+1부터이다.state는 4가지로 구분한다. x,y,dire(방향),accel(가속도)같은 위치에 도착하더라도 어떤 방향이고, 어떤 가속도로 왔냐에 따라서 다음 노드로 가는데 영향을 준다.가속도는 최대 15까지 가능하다 (15 이상이면 한 방향으로 계속 달렸다는건데, 이 때 항상 맵 밖을 넘어가게 되어있다) .. 2025. 2. 13.
[파이썬, 자바] 백준 1800 : 인터넷 설치 (골드1) [파이썬, 자바] 백준 1800 : 인터넷 설치 (골드1)https://www.acmicpc.net/problem/1800풀이방향성 생각DFS로 node N까지 경로 메모리에 저장한다든가, 탐색을 여러 번 진행하면 TLE 발생.limit원까지 지불할 수 있을 때 node N까지 도달할 수 있냐 없냐를 확인한다.금액 크기가 $10^6$이므로 이분탐색 20번 정도면 풀이가 가능하다.$O(20*NlogN)$이고 N이 크지 않아서 시간은 널널하게 풀이가 가능이분탐색은 가장 비싼 간선 limit 제한이 걸렸을 때 node N까지 진행이 가능한가를 확인하고, 다익스트라는 N번 노드까지 사용한 전선의 개수를 기록한다. 파이썬import heapq as hqimport sysinput = lambda : sys.std.. 2025. 2. 10.

티스토리툴바