본문 바로가기

그래프

 (4)
고득점kit) 그래프 #3. 방의 개수 (문제 설명) 원점(0,0)에서 시작해서 아래처럼 숫자가 적힌 방향으로 이동하며 선을 긋습니다. ex) 1일 때는오른쪽 위로 이동 그림을 그릴 때, 사방이 막히면 방 하나로 샙니다. 이동하는 방향이 담긴 배열 arrows가 매개변수로 주어질 때, 방의 개수를 return 하도록 solution 함수를 작성하세요. 제한사항 배열 arrows의 크기는 1 이상 100,000 이하 입니다. arrows의 원소는 0 이상 7 이하 입니다. 방은 다른 방으로 둘러 싸여질 수 있습니다. 입출력 예arrowsreturn [6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0] 3 입출력 예 설명 (0,0) 부터 시작해서 6(왼쪽) 으로 3번 이동합니다. 그 이후 주어진 ..
고득점kit) 그래프 #2. 순위 ( 문제 설명 ) n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대 1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다. 선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 선수의 수는 1명 이상 100명 이하입니다. 경기 결과는 1개 이상 4,500개 이하입니다. results 배열 각 행 [A, B]는 A 선수가 B 선수를 이..
고득점kit) 그래프 # 1. 가장 긴 노드 (문제 설명) n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다. 입출력 예nverte..
백준 1707번 이분그래프 출처 : 1707번: 이분 그래프 (acmicpc.net) 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 이분 그래프 성공 분류 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256 MB 39600 10147 5871 23.141% 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인..
728x90

티스토리툴바