본문 바로가기

전체 글190

최종순위 (위상정렬) indegree[x] 가 0인 노드들을 순서대로 넣어주고 만약 큐가 비게된다면 cycle이 발생한 것, 큐의 사이즈가 2개이상이라면 경로가 2개이상인 개수가 발생한다는 것입니다. from collections import deque t = int(input()) while t: n = int(input()) indegree = [0]*(n+1) graph = [[False]*(n+1) for _ in range(n+1)] datas = list(map(int,input().split())) for i in range(n): for j in range(i+1,n): graph[datas[i]][datas[j]]=True indegree[datas[j]]+=1 m = int(input()) for i in .. 2021. 6. 17.
행성터널 (크루스칼) 행성들의 거리의 최소값을 통해 크루스칼도 스패닝트리를 만들면됩니다. 다만 여기서 각 최소값은 x기준 정렬, y기준 정렬, z기준 정렬을 통해 만들 수 있고 각 인덱스를 따로 저장해줘야합니다. import heapq def find_parent(parent,x): if parent[x]!=x: parent[x]=find_parent(parent,parent[x]) return parent[x] def union_parent(parent,a,b): a = find_parent(parent,a) b = find_parent(parent,b) if a>b: parent[a]=b else: parent[b]=a n = int(input()) parent = [0] *(n+1) edges = [] x_lst = [.. 2021. 6. 17.
연구소 (bfs/dfs) 파이썬은 combinations을 활용하면 쉽게 풀수 있습니다. 저는예전 c++로 n과 m시리즈를 풀었던 걸 기억하면서 dfs 함수로 짜보고 싶어서 해당 방식으로 풀어봤습니다. 복습을 하고 좋았습니다. dfs로 벽을, bfs로 벽이 3개가 되었을때 바이러스를 퍼지게 한후 안전영역을 확인하면 해결 가능합니다. from collections import deque n, m = map(int, input().split()) board = [[0]*m for _ in range(n)] mx = 0 dx = [1,-1,0,0] dy = [0,0,-1,1] visited= [[0]* m for _ in range(n)] for i in range(n): lines = list(map(int, input().spli.. 2021. 6. 17.
경쟁적 전염 (bfs , 우선순위큐) heapq를 통해 우선순위를 처리해주었고 s라는 시간을 처리하기 위해 큐 두개를 만들어 시간이 1초씩 지날때마다 한쪽을 비우고 다른 큐에 넣게를 반복해 s의 1초씩을 처리해주었습니다. from collections import deque import heapq n , k = map(int,input().split()) board = [[0]*n for _ in range(n)] dx = [1,-1,0,0] dy = [0,0,1,-1] for i in range(n): lines = list(map(int,input().split())) for j in range(n): board[i][j]= lines[j] s, x, y = map(int, input().split()) def bfs(s): global.. 2021. 6. 17.

티스토리툴바