세그먼트 트리를 활용한 간선 생성 최적화 기법
문제 도입
그래프 이론 문제를 해결하다 보면, 특정 노드가 구간 내의 모든 노드와 간선을 연결해야 하는 상황이 종종 발생한다. 예를 들어, "노드 u에서 구간 [L, R]에 속하는 모든 노드로 이동 가능"과 같은 제약 조건이 대표적인 경우다. 이러한 경우 단순히 모든 노드를 순회하며 간선을 생성하면 O(n²)의 시간 복잡도가 발생하여 시간 초과가 발생할 수 있다.
이러한 ...
7월 13일 21:20에 게시됨
上海市计算机학회 경시대회 2023년 8월 월례丙조 T5 격자 경로
T5 격자 경로
메모리 제한: 256 Mb | 시간 제한: 1000 ms
문제 설명
n × m개의 격자로 이루어진 지도가 주어진다. 각 격자에는 지형 정보가 있다:
일부 격자는 벽(#)이며, 통과할 수 없다.
일부 격자는 길(.)이며, 통과할 수 있다.
좌상단 격자에서 시작하여 우하단 격자까지 최단 거리로 도착하는 경우의 수를 구해야 한다. 이동 중에는 벽 격자로 진입할 수 없으며, ...
5월 31일 13:16에 게시됨