Algorithm/Graph188 [파이썬] 백준 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. [파이썬] 백준 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. 이전 1 ··· 16 17 18 19 20 21 22 ··· 47 다음
