본문 바로가기

Algorithm/Graph188

[파이썬] 백준 14461 : 소가 길을 건너간 이유 7 (골드2) [파이썬] 백준 14461 : 소가 길을 건너간 이유 7 (골드2)백준 14461 : 소가 길을 건너간 이유 7풀이방향성 생각3차원 다익스트라같은 노드에 도착하더라도, 몇 번째 사이클에 도착했는지가 중요하다.사이클이 3이므로 $3NN$ 크기의 방문 배열을 만든다.코드import heapq as hqimport sysinput = lambda : sys.stdin.readline().rstrip()INF = float('inf')dires = [(1,0),(-1,0),(0,1),(0,-1)]inside = lambda x,y : 0 V[turn][y][x]: continue for dx,dy in dires: nx,ny = x+dx,y+dy if not insid.. 2025. 5. 15.
[파이썬] 백준 4386 : 별자리 만들기 (골드3) [파이썬] 백준 4386 : 별자리 만들기 (골드3)백준 4386 : 별자리 만들기 (골드3)풀이방향성 생각MST코드N = int(input())arr = [list(map(float,input().split())) for _ in range(N)]G = []for i in range(N-1): ax,ay = arr[i] for j in range(i+1,N): bx,by = arr[j] dist = ((ax-bx)**2+(ay-by)**2)**0.5 G.append((dist,i,j))G.sort()P = [i for i in range(N)]def find(x): if x != P[x]: P[x] = find(P[x]) retur.. 2025. 5. 14.
[파이썬] 백준 14923 : 미로 탈출 (골드3) [파이썬] 백준 14923 : 미로 탈출 (골드3)[https://www.acmicpc.net/problem/1012](백준 14923 : 미로 탈출)풀이방향성 생각벽부수고 이동하기랑 똑같은 문제.visit 배열에 부순 횟수를 추가해서 3차원으로 풀이한다.코드from collections import dequeimport sysinput = sys.stdin.readlineinside = lambda x,y: 0코멘트. 2025. 5. 13.
[파이썬] 백준 25195 : Yes or yes (골드4) [파이썬] 백준 25195 : Yes or yes (골드4)https://www.acmicpc.net/problem/25195풀이방향성 생각팬을 만나기 전 상태를 1, 만난 후 상태를 2라고 하면 1부터 전부 탐색했을 때 도착지점에 하나라도 도달할 수 있으면 성공이다.1만 먼저 탐색하기 위해서 다익스트라 사용.종료 조건 잘 생각하기.코드import heapq as hqimport sysinput = lambda : sys.stdin.readline().strip()INF = float('inf')N,M = map(int,input().split())G = [[] for _ in range(N+1)]for _ in range(M): a,b = map(int,input().split()) G[a].. 2025. 5. 12.

티스토리툴바