Algorithm/Graph188 [파이썬] 백준 1922 : 네트워크연결 (골드4) [파이썬] 백준 1922 : 네트워크연결 (골드4)https://www.acmicpc.net/problem/1922풀이방향성 생각모든 노드를 연결하는 최소 비용을 구하는 기본적인 MST 문제전체코드import sysinput = lambda : sys.stdin.readline().rstrip()N = int(input())M = int(input())# cost 내림차순 정렬G = [tuple(map(int,input().split())) for _ in range(M)]G.sort(key=lambda x:-x[2])P = [i for i in range(N+1)]def find(x): if P[x] != x: P[x] = find(P[x]) return P[x]answer = .. 2025. 1. 1. [파이썬] 백준 16952 : 체스판 여행 2 (플레4) [파이썬] 백준 16952 : 체스판 여행 2 (플레4)https://www.acmicpc.net/problem/16952 풀이방향성 생각BFS or 다익(조건 2개라서)배열을 하나 더 만들어서 $O(N^43400)$이라 다익으로 풀면 터질거같아서 BFS로 풀이다른 방법은 생각이 잘...숫자 a에서 b까지 이동하는데 룩,비숍으로 변경하면 최대 4번 걸린다 (현재 위치에서 변경 -> 이동 -> 이동위치에서 변경 -> 이동 : 총 4초)1부터 100까지 찾는거니까 최대 변경 횟수 400으로 생각더미큐를 제거하기 위해서 정답을 처음 찾은 시간 t를 찾으면 flag를 세우고, t+1 정보를 popleft 시키면 while문을 탈출한다. 전체코드from collections import dequeinside = .. 2024. 12. 7. [파이썬] 백준 16959 : 체스판 여행 1 (플레5) [파이썬] 백준 16959 : 체스판 여행 1 (플레5)https://www.acmicpc.net/problem/16959 풀이방향성 생각다차원 BFSN=10인데 위치만으로 visit 배열을 만들게 되면 방문 처리가 제대로 되지 않는다.위치 + 현재 사용하는 말 + 방문한 숫자(현재 위치가 아니라, 1~N^2까지 방문 중 몇번째인지)전체코드from collections import dequeinside = lambda x,y : 01): break # v까지 찾은 상태에서 다음 숫자 v+1을 방문 if V[c][v+1][ny][nx] == -1 and arr[ny][nx] == v+1: Q.append((nx,n.. 2024. 12. 6. [파이썬] 백준 16930 : 달리기 (플레3) [파이썬] 백준 16930 : 달리기 (플레3)https://www.acmicpc.net/problem/16930 풀이방향성 생각N,M,K로 visit 배열 만드는 하위 골드 문제의 경우 map size가 굉장히 작았다.V[K][N][M]으로 BFS를 진행하는 경우, K값이 커서 불가능V[N][M]으로 줄여서 최적화를 하는 테크닉 필요방문 유무와 방문 시간 정보를 통해서 K번 앞으로 달려나가는 것을 최적화 시킨다. 전체코드from collections import dequeimport sysinput = sys.stdin.readlineinside = lambda x,y: 0= V[ny][nx]: break # 현재 도착한 노드가.. 2024. 11. 29. 이전 1 ··· 14 15 16 17 18 19 20 ··· 47 다음
