아이디어 itertools를 사용해 구역의 조합을 구한다. 두 구역이 연결되어 있는지 확인해야 한다. 풀이 및 해설 import sys from collections import deque, defaultdict from itertools import combinations # sys.stdin = open('게리멘더링.txt', 'r') # 연결이 되어있는지 확인하는 함수 def is_connected(group): Q = deque() Q.append(group[0]) visit = [0] * (N+1) visit[group[0]] = 1 while Q: u = Q.popleft() for v in graph[u]: if v in group and visit[v] == 0: Q.append(v) vi..

https://leetcode.com/problems/cheapest-flights-within-k-stops/ Cheapest Flights Within K Stops - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 및 해설(주석) import collections, heapq class Solution(object): def findCheapestPrice(self, n, flights, src, dst, K): # 정점: 인접정점, 가중치 딕셔너리 ..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 import math def find_set(x): while x != p[x]: x = p[x] return x for tc in range(int(input())): N = int(input()) info = [[0, 0] for _ in range(N+1)] r_info = list(map(int, input().split())) c_info = list(map(int, input().s..

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 및 해설(주석) def find_set(x): while x != p[x]: # 루트인지 아닌지 x = p[x] return x for tc in range(int(input())): N, E = map(int, input().split()) # 간선들의 리스트 저장 [[u, v, weight], ...] edges = [list(map(int, input().split())) for _ in range(E)] # kruskal 알고리..

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 def find_set(x): val = P[x] if x == val: return x else: return find_set(P[x]) def union(x, y): P[find_set(x)] = P[find_set(y)] for tc in range(int(input())): N, M = map(int, input().split()) info = list(map(int, input().split())) P = [i for i in..

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 및 해설(주석) from collections import deque # bfs탐색 def solve(num): global rst # print(nums) Q = deque() # Q에는 현재 숫자와 카운트 해줄 숫자를 튜플로 넣어줌 Q.append((num, 0)) # 현재 숫자 방문 체크 visit.add(num) while Q: now, cnt = Q.popleft() if now == M: rst = min(rst, cnt) ..

풀이 및 해설(주석) import collections; import sys sys.setrecursionlimit(10**6) for tc in range(int(input())): N = int(input()) nums = list(map(int, input().split())) graph = collections.defaultdict(list) # graph에 간선의 정보를 넣어줌 for i in range(1, N+1): graph[i].append(nums[i-1]) # traced 는 현재의 진행 상황, 간선을 타고 가다 traced안에 있으면 result를 1증가 traced = set() # visit은 중복처리 방지용, 후위 순회로 정점을 순회한 뒤 return할 때 증가 visited ..