Algorithm475 [파이썬] 백준 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. [파이썬] 백준 1473 : 미로 탈출 (플레5) [파이썬] 백준 1473 : 미로 탈출 (플레5)https://www.acmicpc.net/problem/1473 풀이방향성 생각작은 맵 + state가 변하는 2 요소 = 비트필드를 이용한 BFS카카오 기출에서 비슷한 문제가 있었다.현재 맵 상태를 bit로 나타내고 큐에 같이 넣어주기.가로로 이동하는 경우현재 칸이 가로로 이동가능 (A or 회전안된D or 회전된 C)다음 칸이 가로로 이동가능 (A or 회전안된D or 회전된 C)다음 칸이 가로로 이동 불가능 (회전된D or 회전안된C)세로로 이동하는 경우도 마찬가지이다.현재에서 원하는 방향으로 나갈 수 있는지 체크다음 칸이 회전 안하고 갈 수 있는지 체크 (상태 s 그대로)다음 칸을 회전하고 가야 하는지 체크 (상태 ns로 변경 후 제자리에 큐 추가.. 2024. 11. 26. 이전 1 ··· 34 35 36 37 38 39 40 ··· 119 다음
