본문 바로가기
728x90

그래프64

[python] 백준 11060 점프 점프 https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 문제 해결 판에 써져 있는 수 이하만큼 이동을 해서 최소한의 이동으로 끝까지 가는 문제 사실 bfs를 쓰고 이동을 1~판에 써져 있는 수 로 해서 바로 끝냈지만 메모리가 초과 되었다.(아무래도 MAX 이동 가능 거리가 100이기 때문에 많은 경우의 수가 deque로 들어가는 경우가 있기 때문) 그래서 어떻게 조건을 주어서 que에 들어가는 양을 줄일까 생각을 했는데 DP였다. DP로 이.. 2023. 4. 13.
[python] 백준 16562 친구비 https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 문제 해결 결국 친구 사이클(network)를 만들어서 거기서 친구비 가장 작은 값을 더해주는 문제. 즉 사이클과 그 사이클 안의 가장 작은 친구비를 구하면 된다. CODE import sys input = sys.stdin.readline INF = sys.maxsize sys.setrecursionlimit(10**6) def.. 2023. 4. 13.
[python] 백준 17142 연구소 3 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 문제 해결 시물레이션 + BFS가 바로 생각나는 문제 바이러스가 전염이 되는 것과 안되는 것이 처음에 존재하므로 존재하는 것을 고르는 경우의 수 combination을 사용한다. 각각의 경우 BFS를 사용하여 벽인 부분을 빼고 계속 전염시킨다. 만약 비전염 바이러스를 만나면 비전염바이러스가 전염이 되는 것과 같다. 모두 전염이 될 때의 시간을 결과값으로 받아서 최소값을 구하면 된다. ※ ps) 전형적인 삼.. 2023. 4. 12.
[python] 백준 1238 파티 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 문제 해결 다익스트라 문제 for문을 통해 1~n까지 한 점 i에서 x까지 가는데 최소 시간를 구하고 x에서 i까지 가는데 최소 시간를 구해서 더하면 왕복 최소 시간이 나온다. 리스트를 통해 최댓값을 구하면 된다. CODE import sys input = sys.stdin.readline import heapq INF = sys.maxsize n, m, x = ma.. 2023. 4. 9.
728x90