본문 바로가기

Algorithm475

[파이썬] 백준 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.
[파이썬] 백준 11976 : 불켜기 (골드2) [파이썬] 백준 11976 : 불켜기 (골드2)https://www.acmicpc.net/problem/11976풀이방향성 생각시작점에서 BFS 돌리기.불을 킬 수 있으면 해당 (x,y)와 연결된 노드 (xx,yy)로 불을 켜주기.(x,y)의 인접노드 (nx,ny)에서 첫방문 + 접근 가능한 경우 큐에 추가하기.불 켜진 노드 (xx,yy) 기준에서 인접노드를 탐색하고, 새로 불 켜진 노드 (xx,yy) 주변 노드가 하나라도 V가 true인 경우 (xx,yy)를 큐에 넣으면 된다.주의점은 table[(x,y)]에서 전부 훑지 말고, 업데이트 되는 노드만 방문하도록 수정하기.정답은 갈 수 있는 곳이 아니라, 불을 켤 수 있는 곳이다. V 배열의 element 합이 아니라, access 배열 element의 .. 2025. 3. 23.

티스토리툴바