Algorithm/Graph188 [파이썬] 백준 17267: 상남자 (플레5) [파이썬] 백준 17267: 상남자 (플레5)https://www.acmicpc.net/problem/17267 풀이방향성 생각유니온 파인드로 세로단위 + 벽으로 나뉜 구분으로 나눠서 유니온 파인드로 풀려고 했다단위가 세로랑 벽으로 나뉘면 애초에 같은 노드라고 구분지을 수 있어서 0-1너비우선처럼 풀이세로로 이동하면 덱 맨 앞으로, 가로로 이동하면 덱 맨 뒤로 넣기.전체코드from collections import dequeimport sysinput = lambda : sys.stdin.readline().rstrip()inside = lambda x,y : 0코멘트. 2024. 11. 28. [파이썬] 백준 1981 : 배열에서 이동 (플레5) [파이썬] 백준 1981 : 배열에서 이동 (플레5)https://www.acmicpc.net/problem/1981 풀이방향성 생각첫 풀이는 다차원 BFS + 이분탐색으로 풀이했다.현재까지 범위 [a,b]를 사용해서 100100201 크기의 배열을 만들고 풀이최대 최소 범위를 제한시키고 풀이.하지만, 똑같이 범위차이가 10이어도 [5,15], [10,20]같이 state가 다른 배열(새로운 값 30을 만나는 경우 이전 범위차이가 같더라도 다른 상태에 방문해야한다)을 같은 V에 방문처리 하기때문에 오답두 번째 풀이는 BFS + 이분탐색 완탐처럼 풀이window를 [a,b]로 잡고, 도달할 수 있는지 없는지 풀이limit = b-a라고 했을 때 하나라도 성공하면 그 limit는 성공하고 다음 이분탐색 범위.. 2024. 11. 28. [파이썬] 백준 2325 : 개코전쟁 (플레5) [파이썬] 백준 2325 : 개코전쟁 (플레5)https://www.acmicpc.net/problem/2325 풀이방향성 생각N = 1000, M=50000간선이 최대 50000개 존재하기 때문에, $O((ElogV)^2)$로는 풀이가 불가능하다.다익스트라를 통해 최소 경로를 찾아주고, 그 경로를 무시했을 때 걸리는 시간을 기록한다.$O(V*ElogV)$ = $O(NMlogN)$이다.다른 플레 하위 그래프 문제에서도 비슷한 결의 문제가 많다. 전체코드import heapq as hqimport sysinput = lambda : sys.stdin.readline().rstrip()N,M = map(int,input().split())G = [[] for _ in range(N+1)]for _ in ra.. 2024. 11. 27. [파이썬] 백준 28032: Filed Day (플레2) [파이썬] 백준 28032 : Filed Day (플레2)https://www.acmicpc.net/problem/28032 풀이방향성 생각입력이 커서 $O(N^2)$로는 불가능.각 node bit로 표현하기.주어진 node 중, 해당 node의 hamming dist를 찾기.어떤 이진수 x가 있을 때, 각 자리를 모두 토글한 y는 x와 가장 해밍 거리를 가짐.x와 그 토글 y, 다른 node z가 있다고 가정하자.x -> z -> y 이동하는 경우 C만큼 걸림.각 Node마다 BFS를 돌리면 시간 초과지만, 각 node의 toggle값을 넣고 BFS를 돌리면 해당 노드에서 가장 가까운 거리를 찾고 C에서 빼면 정답을 구할 수 있다.전체코드from collections import dequeW,H = m.. 2024. 11. 26. 이전 1 ··· 15 16 17 18 19 20 21 ··· 47 다음
