알고리즘19 행성터널 (크루스칼) 행성들의 거리의 최소값을 통해 크루스칼도 스패닝트리를 만들면됩니다. 다만 여기서 각 최소값은 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. 괄호변환 (구현, 재귀) 상당히 쉬운 문제인데 처음에는 문제를 보고 지나치게 쫄기도 했고(?) 문제를 잘못 읽어서 어디가 틀린거지 하고 꽤 오래찾은 것 같습니다. 문제는 u 문자열을 뒤집는 부분에서 저는 reversed 인줄 잘못 알고 있었던 것이었습니다. 문제에서 말하는 대로 재귀형태를 만들어 구현하면 쉽게 풀 수 있습니다. from collections import deque def checkCorrect(s): count = 0 for i in s: if i == '(': count+=1 else: if count == 0: return False count-=1 return True # st = deque() # for i in range(len(s)): # if s[i] == '(': # st.append(i) # el.. 2021. 6. 17. 이전 1 2 3 4 5 다음