Algorithm/Graph188 [파이썬] 백준 10282 : 해킹 (골드4) [파이썬] 백준 10282 : 해킹 (골드4)) https://www.acmicpc.net/problem/10282 풀이 방향성 생각 방향 그래프 시작점이 주어지면 탐색을 통해서 각 노드에 도달하는 시간을 기록해야한다. 간선의 가중치가 다르니 다익스트라로 진행 전체코드 import sys import heapq as hq input = lambda : sys.stdin.readline().rstrip() INF = 1e9 def dijkstra(N,x): # 각 노드에 최대값 할당 visit = [1e9]*(N+1) visit[x] = 0 # 시작점 힙에 넣고 시작 heap = [] hq.heappush(heap,(0,x)) while heap: t,x = hq.heappop(heap) for nx,nt.. 2024. 2. 28. [파이썬] 백준 2610 : 회의준비 (골드2) [파이썬] 백준 2610 : 회의준비 (골드2) https://www.acmicpc.net/problem/2610 풀이 방향성 생각 크게 두 가지 파트로 구성 유니온 파인드를 통해서 연결 요소 만들어주기 플로이드 와샬을 통해서 각 연결 요소에서 최대 거리가 가장 작은 노드 구하기 유니온 파인드, 플로이드 와샬이 아니더라도 기본적인 탐색만 쓰고도 풀 수 있다. 하지만 $N = 100$이므로 플로이드 와샬을 통해서 푸는 것이 정해라고 생각한다. 전체코드 from collections import defaultdict as dd import sys input = lambda : sys.stdin.readline().rstrip() def find(a): if parent[a] != a: parent[a] = .. 2024. 2. 28. [파이썬] 프로그래머스 : 수레 움직이기 (레벨3) [파이썬] 프로그래머스 : 수레 움직이기 (레벨3) 코딩테스트 연습 - [PCCP 기출문제] 4번 / 수레 움직이기 | 프로그래머스 스쿨 (programmers.co.kr) 풀이 방향성 생각 맵 크기가 굉장히 작다. 완탐? 효율적으로 탐색하기 위해서 bitmask? 벽, 빈칸, 수레 3가지 종류가 존재해서 힘들어보임 최대 4x4 size에서 이전에 왔던 위치는 지나갈 수 없고, 벽이라는 제약 조건이 있어서 가지치기를 해주면 전체 케이스가 많지 않을 것이라고 판단. DFS로 수레를 이동시키며 경로를 저장한다. 목적지에 도달했을 경우 이동거리와 이동 경로를 저장한다. 빨간 수레의 경로와 파란 수레의 경로를 비교한다. 중간에 같은 좌표를 가지거나, 서로 부딪히며 이동하는 경우를 제외한 가장 짧은 탈출시간 리턴.. 2024. 2. 28. [파이썬] 프로그래머스 : 표 병합 (레벨3) [파이썬] 프로그래머스 : 표 병합 (레벨3) https://school.programmers.co.kr/learn/courses/30/lessons/150366 풀이 방향성 생각 입력이 (50*50) * 1000 = 25만 각 command마다 루프를 전부 돌아도 시간이 부족하지 않은 문제. 각 노드들을 연결했다, 끊었다 -> 유니온 파인드? 그냥 구현으로도 풀 수 있겠지만, 유니온 파인드로 진행. 2차원 리스트에서 반복적으로 다른 리스트로 이동하게 되면 시간적으로 부담돼서 1차원으로 변경. MERGE, UNMERGE 이후 2500개의 셀을 훑고 업데이트 해야 하므로 1차원으로 바꿈. 전체코드 def solution(commands): parent = [i for i in range(51*51)] ce.. 2024. 2. 25. 이전 1 ··· 23 24 25 26 27 28 29 ··· 47 다음