Algorithm/Graph188 [파이썬] 백준 1938 : 통나무 옮기기 (골드2) [파이썬] 백준 1938 : 통나무 옮기기 (골드2)https://www.acmicpc.net/problem/1938풀이방향성 생각다차원 그래프 문제통나무의 상태에 따라서 위치 이외에 state를 추가해서 V[state][y][x]로 배열 생성하기.범위 조건 체크하기 -> 통나무 회전 시 주변 모든 좌표 탐색해야함 파이썬from collections import dequeinside = lambda x,y : 0코멘트하드코딩은 원트했는데....x y 인덱스 바꿔쓰는거 잘 찾기 2025. 4. 5. [파이썬] 백준 17940 : 지하철 (골드2) [파이썬] 백준 17940 : 지하철 (골드2)https://www.acmicpc.net/problem/17940풀이방향성 생각조건을 2개 쓰는 다익스트라인접 행렬 -> 인접리스트로 변환 해주기환승 횟수는 최대 N-1이므로 내부 탐색 루프에 조건 걸어주기.힙에 우선순위를 정해놨으면 ex에 도달했을 때 바로 탈출 전체코드import heapq as hqimport sysinput = sys.stdin.readlineINF = float('inf')N,ex = map(int,input().split())company = [int(input()) for _ in range(N)]G = [[] for _ in range(N)]for x in range(N): for nx,cost in enumerate(m.. 2025. 3. 26. [파이썬] 백준 16402 : 제국 (골드2) [파이썬] 백준 16402 : 제국 (골드2)https://www.acmicpc.net/problem/16402풀이방향성 생각유니온 파인드서로 다른 군집끼리 진행했을 때는, 이긴 쪽 루트를 루트로 설정해주면 된다.서로 같은 군집끼리 진행했을 때는, 부모가 해당 루트인 모든 노드들을 이긴 노드로 변경한다.N이 매우 작게 나왔는데, 문제 의도는 매 쿼리마다 경로압축으로 루트를 업데이트하는 문제인듯? 전체코드import sysinput = lambda : sys.stdin.readline().strip()def get_name(string): return string.split()[-1]def find(x): if P[x] != x: P[x] = find(P[x]) return P.. 2025. 3. 25. [파이썬] 백준 5214 : 환승 (골드2) [파이썬] 백준 5214 : 환승 (골드2)https://www.acmicpc.net/problem/5214풀이방향성 생각node가 10만개.각 하이퍼튜브에 1000개씩 1000개의 node가 들어올 수 있다.각 하이퍼튜브들은 완전 그래프를 띄므로, 인접 리스트로 구현해도 10^9까지 올라가서 불가능하다.하이퍼튜브를 하나의 정점으로 보면, 하이퍼튜브 탑승/하차의 cost가 0/1임을 알 수 있다.0-1 너비우선 탐색으로 탑승에는 appendleft, 하차에는 append를 사용해서 구현. 파이썬from collections import dequeimport sysinput = lambda : sys.stdin.readline().strip()N,K,M = map(int,input().split())G =.. 2025. 3. 24. 이전 1 2 3 4 5 6 7 ··· 47 다음
