Algorithm475 [파이썬] 백준 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. [파이썬] 코드트리 나무박멸 (골드4) [파이썬] 코드트리 나무박멸 (골드4) https://www.codetree.ai/training-field/frequent-problems/problems/tree-kill-all/description?page=1&pageSize=20 풀이 방향성 생각 나무 주변으로 빈 칸, 벽, 나무가 있는지 체크해야함 -> search 주변에 있는 나무 개수에 따라 성장함(search 정보 바탕으로) -> grow 주변에 있는 빈 칸에 따라 확장함(search 정보 바탕으로) -> spread 제초제를 뿌릴 위치를 찾음(위치:개수) 이후 정렬 (기준 3개임)-> find_spot find_spot 리턴값을 바탕으로 나무 제거 제초제 유지시간을 기록해야하니 N*N size 리스트를 더 만든다. 나무가 없으면 확장, .. 2024. 3. 5. [파이썬] 백준 1301 : 비즈 공예 (골드3) [파이썬] 백준 1301 : 비즈 공예 (골드3) https://www.acmicpc.net/problem/1301 풀이 방향성 생각 다차원 DP / DFS + DP 다차원 DP로 접근할 경우 5개의 구슬 색 + 이전 2개의 상태 : 7개의 상태 구분조건이 주어져서 list로 구현할 경우 편해보이지 않음. DFS + DP로 가능한 노드에 접근했을 경우 메모제이션 해주고, 필요없는 부분은 가지치기. list 대신 hash 사용. 출근기록, ABC처럼 정답 하나를 찾는게 아니라 카운팅 해줘아하므로 set 대신 dict으로 개수까지 저장 전체코드 N = int(input()) remains = [int(input()) for _ in range(N)] dp = {} def dfs(remains: list, a.. 2024. 3. 3. 이전 1 ··· 52 53 54 55 56 57 58 ··· 119 다음
