본문 바로가기

Algorithm/Graph188

[파이썬] 백준 2307: 도로검문 (골드1) [파이썬] 백준 2307: 도로검문 (골드1) 2307번: 도로검문 그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸리 www.acmicpc.net 문제 풀이 방향성 생각 도둑은 항상 최단경로로만 간다. 최단경로가 여러 개일 수 있다. 어떤 경로를 거쳐 지나왔는지는 DFS를 통해 역추적. 여러 최단 경로의 합집합을 하나 구한다. 합집합에서 다리를 하나씩 끊으면서 탐색하기. 전체코드 import heapq as hq import sys input = lambda : sys.stdin.readline().rstrip() inf = 1e9 N,M = map(int,inpu.. 2024. 3. 16.
[파이썬] 백준 2406 : 안정적인 네트워크 (골드3) [파이썬] 백준 2406 : 안정적인 네트워크 (골드3) https://www.acmicpc.net/problem/2406 풀이 방향성 생각 네트워크가 고장나는 경우는 컴퓨터 간 연결이 끊어지는 경우나, 컴퓨터가 고장나는 것. 이 문제에서는 전자의 경우만 살펴본다. 1번 컴퓨터는 모든 노드와 연결돼있다. 2~N번 노드 간 MST로 연결이 돼있으면 중간에 네트워크가 끊기더라도 1번 컴퓨터를 통해서 갈 수 있다. 1번 컴퓨터와 연결된 간선과 미리 주어진 간선 정보를 제외하고, 남은 간선들을 이용해 2~N번 노드를 잇는 MST를 만드는 문제 전체코드 import sys input = lambda : sys.stdin.readline().rstrip() # 재귀로 부모 호출 def find(a): if pare.. 2024. 3. 5.
[파이썬] 프로그래머스 : 석유 시추 (레벨2) [파이썬] 프로그래머스 : 석유 시추 (레벨2) https://school.programmers.co.kr/learn/courses/30/lessons/250136 풀이 방향성 생각 기본 BFS문제 각 덩어리 별로 BFS를 돌리고 덩어리에 포함된 x좌표에 그 덩어리 크기를 대응시킨다. oils[x] = [덩어리크기1, 덩어리크기2, ...] x에서 시추를 했을 때 덩어리들의 합이 가장 큰 것을 출력한다. 전체코드 from collections import deque, defaultdict as dd def solution(land): h,w = len(land),len(land[0]) dire = [(1,0),(0,1),(-1,0),(0,-1)] V = [[False]*w for _ in range(h).. 2024. 3. 2.
[파이썬] 백준 2056 : 작업 (골드4) [파이썬] 백준 2056 : 작업 (골드4) https://www.acmicpc.net/problem/2056 풀이 방향성 생각 위상정렬 + DP. DP라고 하기엔 메모제이션이 크게 중요하지 않아서 위상정렬 위주 BFS를 사용해서 선행 작업들이 없는 노드에서 시작한다. 특정 노드에 필요한 선행 작업들이 모두 충족되면 해당 노드를 큐에 넣는다. 큐에 넣을 때는 최대값을 갱신해서 넣어준다. 해당 경로를 지나는 값 중 최대값을 넣어야한다. 전체코드 from collections import deque import sys input = lambda : sys.stdin.readline().rstrip() N = int(input()) T = [0]*(N+1) G = [[] for _ in range(N+1)] .. 2024. 2. 29.

티스토리툴바