그래프와 탐색

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

전체 결과문제 12개

		유형				채점
거짓말파티 참석자들을 유니온파인드로 묶어, 진실을 알아야 하는 사람과 연결되지 않은 파티에서만 이야기를 부풀릴 수 있는 최대 횟수를 구합니다.	쉬움3	유니온 파인드그래프+1	아직 제출이 없습니다	2초	128 MB	채점 가능
친구N x N 친구 관계 행렬(N ≤ 50)이 주어질 때, 한 사람으로부터 두 단계 이내로 연결된 사람 수의 최댓값을 구합니다.	쉬움3	그래프행렬+1	아직 제출이 없습니다	2초	128 MB	채점 가능
트리의 리프 노드부모 배열로 주어진 트리에서 특정 노드와 그 자손을 모두 삭제한 뒤 남은 리프 노드의 개수를 구합니다.	쉬움3	트리DFS+1	아직 제출이 없습니다	2초	128 MB	채점 가능
칵테일N개의 재료가 트리 형태로 N-1개의 질량 비율로 연결되어 있을 때, 모든 비율을 만족하는 가장 작은 양의 정수 질량들을 구합니다.	보통5	트리DFS+2	아직 제출이 없습니다	2초	128 MB	채점 가능
숫자 교환정수 N의 자릿수를 정확히 K번 교환해 앞자리가 0이 되지 않게 만들 수 있는 가장 큰 수를 구하고, 불가능하면 -1을 출력합니다.	보통5	BFS완전 탐색+2	아직 제출이 없습니다	2초	128 MB	채점 가능
도로 그래프 연결하기인접 행렬이 주어질 때, 그래프를 완전히 연결시키는 데 필요한 최소 엣지 교환 횟수를 구하거나 불가능하면 -1을 출력합니다.	보통5	그래프유니온 파인드+1	아직 제출이 없습니다	2초	128 MB	채점 가능
검색 엔진웹사이트 간 링크 정보가 주어질 때, 순환이 생기지 않는 링크만 반영해서 특정 웹사이트의 신뢰도 점수를 계산합니다.	보통6	그래프DFS+2	아직 제출이 없습니다	2초	128 MB	채점 가능
완벽한 순열까지의 최소 차이주어진 순열을 하나의 N-사이클, 즉 완벽한 순열로 바꾸는 데 필요한 최소 변경 위치 수를 구하는 문제입니다.	보통6	수학그래프+2	아직 제출이 없습니다	2초	128 MB	채점 가능
도로N개 도시 사이 도로 중 정확히 M개를 선택해 모든 도시를 연결하면서 우선순위가 가장 높은(사전식으로 가장 작은) 도로 집합을 찾고, 불가능하면 -1을 출력합니다.	보통7	그리디유니온 파인드+2	아직 제출이 없습니다	2초	128 MB	채점 가능
섬8방향으로 연결된 섬과 4방향으로 연결된 바다가 있는 지도에서 섬이 다른 섬을 감싸는 포함 구조를 찾아 높이별 섬의 개수를 구하는 문제입니다.	어려움8	BFS그래프+2	아직 제출이 없습니다	2초	128 MB	채점 가능
뒤집기0이 A개, 1이 B개 있을 때 매 턴마다 정확히 K개를 골라 뒤집어서 전부 1로 만드는 최소 턴 수를 구하고, 불가능하면 -1을 출력합니다.	어려움8	BFS수학+2	아직 제출이 없습니다	2초	128 MB	채점 가능
도미노주어진 도미노 조각을 모두 사용해 서로 겹치지 않는 하나 이상의 순환으로 나누는 방법의 수를 구하는 문제입니다.	어려움9	그래프조합론+2	아직 제출이 없습니다	2초	128 MB	채점 가능