Algorithm/Graph188 [파이썬] SWEA 1247 : 최적 경로 (D5) [파이썬] SWEA 1247 : 최적 경로 (D5)SWEA 1247 : 최적 경로풀이방향성 생각완탐 or 비트마스킹 다익맵 크기가 충분히 작아서 이 상태에서도 비트 다익을 돌려도 된다.하지만, 노드 수가 적고 간선 코스트를 구하는게 쉬워서 2차원에서 1차원으로 압축시켜주기.간선 코스트가 다르니까 다익스트라 사용.방문 유무를 비트마스킹으로 관리 전체코드import heapq as hqINF = float('inf')TC = int(input())for tc in range(1,TC+1): N = int(input()) infos = list(map(int,input().split())) done = (1j : cost) G = [[] for _ in range(N+2)] for .. 2025. 3. 9. [파이썬, 자바] 백준 1506 : 경찰서 (플레5) [파이썬, 자바] 백준 1506 : 경찰서 (플레5)https://www.acmicpc.net/problem/1506풀이방향성 생각간선 정보가 인접행렬로 나와있다.N이 작아서 인접 리스트를 구현하는 대신 그냥 인접행렬 사용하기문제를 해석하면 SCC가 몇 개나 있는지 확인하는 문제이다.각 SCC 내에서 가장 작은 건설 cost를 구해서 더해주면 되는 문제 파이썬from collections import dequeimport sysinput = lambda : sys.stdin.readline().strip()N = int(input())arr = list(map(int,input().split()))G = [list(map(int,input())) for _ in range(N)]# SCC 방문 / 카운팅.. 2025. 3. 9. [파이썬, 자바] 백준 4196 : 도미노 (플레4) [파이썬, 자바] 백준 4196 : 도미노 (플레4)https://www.acmicpc.net/problem/4196풀이방향성 생각타잔 알고리즘으로 얻은 SCC는 위상정렬의 역순으로 나온다.얻은 SCC에서 각 scc를 하나의 노드로 인식하게 만들어준다.새로운 노드간 그래프를 읽어서 진입차수를 계산해주기. 파이썬from collections import dequeimport syssys.setrecursionlimit(10**6)input = lambda : sys.stdin.readline().strip()TC = int(input())for tc in range(TC): # 타잔 N,M = map(int,input().split()) # 방문, 그룹관리, 카운팅, 스택 관리 V =.. 2025. 3. 8. [파이썬] 백준 2150 : Strongly Connected Component (플레5) [파이썬] 백준 2150 : Strongly Connected Component (플레5)https://www.acmicpc.net/problem/2150풀이방향성 생각타잔 알고리즘. 그래프의 사이클 탐색하기 전체코드import syssys.setrecursionlimit(10**6)input = lambda : sys.stdin.readline().rstrip()N,M = map(int,input().split())G = [[] for _ in range(N+1)]for _ in range(M): a,b = map(int,input().split()) G[a].append(b)cnt = 0V = [-1]*(N+1)P = [-1]*(N+1)on_stack = [False]*(N+1)stack .. 2025. 3. 7. 이전 1 ··· 5 6 7 8 9 10 11 ··· 47 다음
