본문 바로가기

Algorithm/Graph188

[파이썬, 자바] 백준 14867 : 물통 (골드2) [파이썬, 자바] 백준 14867 : 물통 (골드2)https://www.acmicpc.net/problem/14867풀이방향성 생각입력이 조금 크고 물통 A,B의 순서가 중요해서 시간이 조금 빡빡하다.두 물통의 상태 변화를 파이썬에선 V에 tuple로 넣고, 파이썬from collections import dequedef bfs(X,Y,ex,ey): Q = deque([(0,0,0)]) V = set([(0,0)]) while Q: cx,cy,t = Q.popleft() if (cx,cy) == (ex,ey): return t for nx,ny in [(X,cy),(cx,Y),(0,cy),(cx,0), .. 2025. 2. 6.
[파이썬, 자바] 백준 24463 : 미로 (골드4) [파이썬, 자바] 백준 24463 : 미로 (골드4)https://www.acmicpc.net/problem/24464풀이방향성 생각BFS + 역추적 사용하기.DFS를 하기에는 너무 맵 사이즈가 커서 TLE 우려가 있어서 BFS 사용풀이테두리에서 start, end 탐색BFS + 역추적 기록역추적 복원 후 2D 배열 순회하면서 복원 set에 있는지 확인출력 파이썬from collections import dequeimport sysinput = lambda : sys.stdin.readline().rstrip()inside = lambda x,y : 0자바import java.io.*;import java.util.*;public class Main { public static int H; p.. 2025. 2. 4.
[파이썬, 자바] 백준 16681 : 등산 (골드2) [파이썬, 자바] 백준 16681 : 등산 (골드2)https://www.acmicpc.net/problem/16681풀이방향성 생각성취감은 높이로 이미 고정되어있다.등산의 가치를 최대로 하려면 소모한 체력을 최소로 해야한다.즉, 이동 거리가 최소여야하는 최단 거리 문제에 노드 간 이동 조건이 붙은 문제.1 -> N -> 1로 이동을 해야하므로 다익 2번 돌리기.1 -> N으로 이동이 가능하다는거 자체가 N -> 1도 가능하다는 소리.처음에는 다익 파라미터에 is_up같은거를 전달해서 조건문에서 다르게 구현하려고 했는데 그럴 필요가 없다. 파이썬import heapq as hqimport sysinput = lambda : sys.stdin.readline().rstrip()INF = float('inf.. 2025. 2. 3.
[파이썬, 자바] 백준 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.

티스토리툴바