그래프와 탐색

BFS, DFS, 최단 경로, 트리 문제입니다.

전체 결과문제 3710개

		유형				채점
끝나지 않는 BFS의 역습방문 처리를 빠뜨린 잘못된 BFS가 주어진 방향 그래프에서 유한 번에 멈추는지 판정하고, 멈춘다면 반복 횟수를 1e9+7로 나눈 값을 구한다.	어려움9	그래프BFS+2	아직 제출이 없습니다	2초	512 MB	채점 가능
배관공과 사나운 개홀수 행과 열에만 집이 있는 격자에서 각 집을 한 번씩 지나는 하강 경로들로 덮되, 개가 있는 칸을 지나는 파이프 비용을 최소화하고 경로 수를 K 이하로 제한하는 문제.	어려움9	동적 계획법그리디+2	아직 제출이 없습니다	2초	512 MB	채점 가능
가로수두 가지 색으로 각 건물 앞에 나무를 심는 최소 비용 배정을 유지하면서, 같음/다름 제약과 비용 갱신이 추가될 때마다 최적 비용을 출력한다.	어려움9	유니온 파인드그래프+2	아직 제출이 없습니다	2초	256 MB	채점 가능
일반 그래프 매칭정점 N개와 간선 M개를 가진 무방향 그래프가 주어질 때 최대 매칭의 크기를 출력한다.	어려움9	그래프그리디+2	아직 제출이 없습니다	1초	128 MB	채점 가능
일반 그래프 최대 가중치 매칭가중 무방향 그래프가 주어졌을 때, 간선 가중치 합이 최대인 매칭을 찾는다.	어려움9	그래프그리디+1	아직 제출이 없습니다	2초	512 MB	채점 가능
Voronoi Diagram연결된 가중 그래프와 시작 정점 집합이 주어질 때, 각 간선 위의 모든 점을 가장 가까운 시작 정점에 배정하고 각 정점이 차지하는 길이의 합을 구한다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	2초	1024 MB	채점 가능
Xtreme NP-hard Problem?!정점 1에서 n까지 정확히 k개의 간선을 쓰는 단순 경로 중 가중치 합이 최소인 것을 찾고, 없으면 -1을 출력한다. n, m, k가 10^6까지 커서 문제 자체가 NP-난해임을 명시한다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	5초	1024 MB	채점 가능
떠돌이 상인가중치가 있는 방향 그래프와 각 시장의 K개 품목 매매 가격이 주어질 때, 한 번에 한 품목만 거래하며 닫힌 보행을 돌 때 이익을 시간으로 나눈 값의 최댓값을 구해 내림한 정수를 출력한다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	2초	512 MB	채점 가능
나무 탈출루트가 있는 트리에서 각 리프에 말이 하나씩 놓인 상태로 시작해, 두 사람이 번갈아 말을 부모로 옮기고 루트에 닿으면 제거하는 게임에서 선수가 이길 수 있는지 판정한다.	어려움9	게임 이론트리+2	아직 제출이 없습니다	2초	512 MB	채점 가능
트리와 쿼리 20동적으로 변하는 가중치 트리에서 정점 값을 토글하고, 각 트리에서 가중 거리 합이 최소인 정점의 값을 구하는 link-cut 자료구조 문제입니다.	어려움10	트리세그먼트 트리+1	아직 제출이 없습니다	5초	512 MB	채점 가능