Algorithm475 [파이썬] 백준 20304 : 비밀번호 제작 (플레5) [파이썬] 백준 20304 : 비밀번호 제작 (플레5)https://www.acmicpc.net/problem/20304풀이방향성 생각사용한 비밀번호는 안전거리가 0이다.다익처럼 풀면 시간초과할듯?최대 10만개에서 힙에다가 계속 넣어버림.BFS는 어짜피 100만 2^10~2^11이라 각 자리수에서 최대 11?번이면 도달비트연산으로 해밍거리 1인거부터 차례로 이동하면 OK전체코드from collections import dequeN = int(input())M = int(input())arr = list(map(int,input().split()))V = [-1]*(N+1)for a in arr: V[a] = 0leng = len(bin(N))-2Q = deque(list(zip(arr,[0]*N)).. 2024. 11. 23. [파이썬] 백준 3197 : 백조의 호수 (플레5) [파이썬] 백준 3197 : 백조의 호수 (플레5)https://www.acmicpc.net/problem/3197풀이방향성 생각BFS + 유니온파인드.첫 BFS를 돌리고, 각 분리된 영역마다 번호를 매긴다. BFS를 돌리면서 X와 닿는 부분을 Q에 넣는다.백조가 있는 곳을 우선으로 1,2.그 이후부터는 3,4, ...로 매긴다.유니온 시, 루트 노드를 작은 쪽으로 해서 백조1과 백조2가 합쳐질 때 시그널을 받기 위함.Q넣은 좌표들을 주변으로 spread 시킨다.spread 시키며 다음 부분들은 next queue, nQ에 담는다.전체코드from collections import dequeimport sysinput = sys.stdin.readlineinside = lambda x,y: 0코멘트1년 전.. 2024. 11. 23. [파이썬] 백준 14868 : 문명 (플레4) [파이썬] 백준 14868 : 문명 (플레4)https://www.acmicpc.net/problem/14868풀이방향성 생각BFS + 유니온파인드백조의호수?랑 비슷해서 방향성은 바로 찾았다.중요한 점은, 각 노드마다 parent를 설정하면 map size가 굉장히 커서 시간 소모가 굉장히 크다는 점.각 문명마다 번호를 매긴다.시작점에서 붙어있는 경우를 생각하기 위해 BFS 사용하기.parent에서 K만큼 쌩으로 쓰는 것 보다 메모리를 꽤나 절약할 수 있다.visit 배열 첫 방문이면 그 문명으로 넘어가고, 두 번째 방문이면 union을 진행하면 된다.문명이 합쳐지는 경우는 두 가지axb -> aab로 합쳐지는 경우이 경우는 첫방문인 x->a에서 a로 합쳐지고 b에서 탐색 시 알아서 합쳐진다.axxb -.. 2024. 11. 22. [파이썬] 백준 11779 : 최소비용 구하기 2 (골드3) [파이썬] 백준 11779 : 최소비용 구하기 2 (골드3)https://www.acmicpc.net/problem/11779풀이방향성 생각최소비용 구하기 1916 이랑 같은 문제.다익스트라 + 역추적기존 다익스트라 배열에 previous node를 기록해주는 리스트를 추가한다.전체코드import heapq as hqimport sysinput = lambda : sys.stdin.readline().rstrip()N = int(input())M = int(input())G = [[] for _ in range(N+1)]for _ in range(M): a,b,cost = map(int,input().split()) G[a].append((b,cost))start,end = map(int,in.. 2024. 11. 21. 이전 1 ··· 35 36 37 38 39 40 41 ··· 119 다음