vertex multiplexing을 이용한 가중치의 bitwise xor이 최소가 되는 경로

https://atcoder.jp/contests/abc410/tasks/abc410_d D - XOR Shortest WalkAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 방향 그래프가 주어지는데, A에서 B로 가는 간선의 가중치가 W이다. 이때, 1번부터 N번 정점까지 경로의 가중치들의 bitwise xor이 최소가 되는 경로에 대해 그 최솟값을 구하면? 여기서 1번부터 N번 정점까지 경로는, 동일한 간선이나 동일한 정점을 여러번 방문하더라도, 처음 시작점이 1번이고 마지막 종점이 N번인 경로이다. ----------..

• format_list_bulleted 알고리즘/그래프 이론 정복기
• · 2025. 6. 18.
• textsms

AtCoder Beginner Contest 405 대충 복기(BFS, 최단경로, 경우의수, 팩토리얼 모듈로 역원)

1. D번 D - Escape Route D - Escape RouteAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 2차원 배열이 주어질때, 각 위치에서 탈출구 E번까지 가는 최단 경로를 표시해야하는 문제 #은 이동불가능 지역이므로 표시하지 않는다. ..E...이라고 한다면? >>E>>^ 이런식으로 될 것이다. 혹은 정답이 여러개일 수 있는데 >>E^>^도 정답이 될듯? 각각의 지점에서 E까지 가는 최단 경로를 어떻게 찾는다고 하더라도 표시를 어떻게 해야하지? 각각의 지점이 1000*1000개인데 이걸 언제 다하냐? 그..

• format_list_bulleted 경쟁 프로그래밍/Atcoder
• · 2025. 5. 11.
• textsms

일직선 상에서 특정 위치에서 거리 합이 최소가 되도록 집을 짓는 문제

18513번: 샘터 N개의 샘터가 주어질때 K채의 집을 지을려고 한다 각 집에서 가장 가까운 샘터까지의 거리를 불행도라고 정의할때 K채의 집의 모든 불행도의 합이 최소가 되도록 집을 짓는다 그 불행도의 합의 최소를 구하는 문제 ------------------------------------------------------------------------------------------------------------------- BFS로 풀 수 있다는데 생각해봐도 감이 잘 안오더라고... 평소 BFS문제랑 조금 달라서 그런지 샘터 위치 x에서 왼쪽 오른쪽으로 -1,1만큼 봐서 비어있으면 x-1, x+1에 집을 짓고 다시 x-1에서 왼쪽 오른쪽으로 -1,1만큼 x-1,x에서 비어있으면 집을 짓고 x+1에..

• format_list_bulleted 알고리즘/DFS BFS 정복기
• · 2025. 4. 5.
• textsms

flood fill 핵심 트릭 - 사각형으로 둘러쌓인 연결요소의 둘레의 길이(연결요소 내부 영역을 찾는 방법)

5850번: Perimeter  100*100 들판에 1*1 건초를 n개 두는데 이 건초 n개는 연결되어있다. 즉 임의의 건초에서 상하좌우로 출발하면 다른 모든 건초로 도달할 수 있다 이 연결된 영역의 둘레를 구하고 싶다. 이때 건초 더미들이 감싸고 있는 내부 구멍이 있을 수 있는데 이 구멍들의 둘레는 계산하지 않는다 예를 들어 아래 그림은 둘레가 14이다. X부분의 둘레는 계산하지 않는다   --------------------------------------------------------------------------------------------------------------------------------- 건초더미 둘레를 구해야하는데 건초더미가 감싸는 내부 구멍을 어떻게 찾아야하느냐가 관..

• format_list_bulleted 알고리즘/DFS BFS 정복기
• · 2025. 2. 16.
• textsms

해밍거리 + BFS 경로 역추적하기

2479번: 경로 찾기 이진 코드들이 주어질때, A 이진코드에서 B 이진코드로 가는 경로를 찾을려고 한다 이때 경로를 구성한 노드간 서로 인접한 코드끼리의 해밍거리가 1이어야한다 해밍거리는 길이가 같은 두 이진코드들에서 왼쪽부터 오른쪽으로 차례로 비교할 때 서로 다른 값을 가진 비트의 수이다 예를 들어 010과 110은 서로 다른 비트가 0번째 비트로 1개이므로 해밍 거리가 1이다 코드 번호 A,B가 주어질때 가장 짧은 해밍 경로를 찾는다 -------------------------------------------------------------------------------------------------------------------------------------------------- 두 코..

• format_list_bulleted 알고리즘/DFS BFS 정복기
• · 2025. 2. 3.
• textsms

BFS로 어떤 정수의 0과 1로만 이루어진 배수 찾기

4994번: 배수 찾기 정수 N이 주어질때, N의 배수 중에 0과 1로만 이루어진 배수 M을 찾는다 1보다 큰 M의 길이는 100이 넘지 않아야하고 가능한 경우가 여러가지 있으면 아무거나 찾는다 ---------------------------------------------------------------------------------------------------------------------------------------- 100000000000000000000000000000000 해서 0인거 하나씩 1로 바꿔보고 11000000000000000000000, 101000000000000000000.... 근데 하나만 바꾸는게 아니라 문제는 2개 이상 바꿔야할수도 있잖아 11100000000..

• format_list_bulleted 알고리즘/DFS BFS 정복기
• · 2025. 1. 28.
• textsms