Atcoder3 AGC 019 C 시작점에서 도착점까지 최단 경로를 구할 때 가로와 세로 중 한 방향을 먼저 끝까지 이동한 뒤 다른 방향으로 이동해도 거리는 손실되지 않는다. 도로 간격이 모두 동일하고 분수대가 교차점에만 존재하므로, 최단 경로는 결국 ‘ㄱ’자 형태로 압축될 수 있기 때문이다. 이렇게 한 방향을 먼저 확정한 뒤에는 시작점과 도착점이 만드는 직사각형 내부에 있는 분수대만 신경 쓰면 된다. 분수대는 같은 가로나 같은 세로에 두 개 이상 존재하지 않으므로, 직사각형 내부 분수대를 x 좌표 기준으로 정렬했을 때 y 좌표가 증가하는 부분수열, 즉 LIS를 구하면 우회 가능한 분수대의 최소 개수를 알 수 있다. 분수대 하나를 우회할 때 차량은 직선 20미터를 달릴 대신 반지름 10미터짜리 4분의 1원호를 따라 이동한다. 원호 길이가.. 2025. 2. 14. ABC 355 F 문제의 조건을 살펴보면 간선의 가중치가 10 이하로 매우 작다는 것을 알 수 있다. MST의 기본은 간선을 가중치 기준으로 정렬한 후, Union Find를 돌리는 것이다. 이때, 간선을 정렬할 필요 없이 가중치 별로 저장할 수 있다. Union Find를 10개 만들면 이를 쉽게 관리할 수 있을 것이라 생각했지만 단순히 Union Find를 10개 만드는 것으로는 해결되지 않았다. 여기서 필요했던 또 하나의 아이디어는 Union Find를 누적시키는 것이다. 추가된 간선이 더 낮은 간선들로 연결된 하나의 컴포넌트 내에 있다면, 이를 카운트할 필요가 없다. 따라서, 현재 가중치 이상인 Union Find에 모두 Union을 해주고 현재 가중치 - 1의 Union Find, 현재 가중치의 Union Fi.. 2025. 2. 5. ABC 357 E 모든 정점에서 출발해서 도달할 수 있는 정점들의 개수의 합을 구하는 문제이다. 반대로 생각해서 한 정점에 도달할 수 있는 정점들의 개수의 합을 구한다고 생각해 보자. out-degree가 모두 1이므로, 하나의 연결된 그래프에서 가능한 SCC의 개수는 최대 1개이다. SCC에 속하는 정점들의 경우 SCC의 크기의 제곱을 하면 한 번에 구할 수 있다. SCC에 연결된 가지들의 경우, 맨 끝에서 탐색하며 값을 더해 나가면 답을 구할 수 있다. 가지들이 합쳐지는 부분에서 주의해야 하는데, 여차하면 오답이나 시간초과가 발생할 수 있다. 나는 in-degree를 세는 방법으로 해결했다. in-degree가 1 초과이면 해당 정점에 현재까지의 가중치를 더해 놓고 in-degree를 1 감소시킨다. 이렇게 되면 .. 2025. 2. 5. 이전 1 다음