백준123 [백준] 20040번 : 사이클 게임 [파이썬] https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 조건 홀,짝 번갈아가며 사이클게임을 실시한다. 0 ~ n-1 의 점 n개가 주어진다.(이 중 어느 3점도 일직선에 있지않다.) 매 차례 마다 번갈아가며 점 사이에(중복X) 선분을 긋는다. (선분 간에 교차가 가능) 선분간에 사이클 C(한 점에서 출발하여 돌아올 수있음)가 생기면 게임이 종료된다. 몇 번째에서 사이클이 완성되는지 (완성될 수 없다면 0을) 출력 한다. 첫 줄 n, m은 점의 개.. 2021. 11. 18. [백준] 4195번 : 친구 네트워크 [파이썬] https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 조건 친구 관계가 순서대로 주어진다. 친구 네트워크란 친구 관계만이 이동할 수 있는 사이를 뜻한다. 두 사람의 친구 네트워크에 몇 명이 있는지 출력하라 첫 째줄에는 테스트케이스 T가 입력 각 테스트 케이스 첫째 줄에는친구 관계수 F( 2021. 11. 18. [백준] 1976번 : 여행 가자 [파이썬] https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 조건 첫째줄에 주어지는 노드의 개수는 N개이다. 둘째 줄에는 주어지는 숫자는 탐색해야하는 노드의 개수 M개이다. 간선의 정보는 i번째 줄의 j번째 숫자로 0, 1로 주어진다. 마지막 줄에는 노드의 탐색 순서가 주어지는데 가능하면 YES 아니면 NO를 출력해야한다. 풀이 아이디어 유니온-파인드 함수를 적절히 이용해보자. 풀이 부모노드 리스트를 선언해준뒤 union-find 함수를 각각 만들어준다. .. 2021. 11. 18. [백준] 1717번 : 집합의 표현 [파이썬] https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 문제를 풀기에 앞서 유니온-파인드의 개념을 알아야한다. 유니온 - 집합을 합치고 파인드 - 집합에서 원소를 찾는 것을 의미한다. https://20210916start.tistory.com/83?category=1009373 그래프 이론 서로소 집합 [union-find] 수학에서 서로소 집합(Disjoint Sets)란 공통 원소가 없는 두 집합을 의미한.. 2021. 11. 18. 이전 1 2 3 4 ··· 31 다음
