본문 바로가기

유니온 파인드

[백준 1043] 거짓말 (JAVA)

CodingTEST 2023. 8. 27. [백준 1043] 거짓말 (JAVA) 백준 1043번 문제 - 거짓말 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 분석 N,M 입력 : 지민이는 N명의 친구가 있으며, M개의 파티에 참여해야한다. 수 K와 K명의 진실을 아는 사람 입력 M개의 파티를 입력 - 수 K와 K명의 파티에 참여하는 사람 입력 (M개의 파티에 순서는 없다) 진실을 아는 사람이 있을 때에는 과장해서 이야기 할 수 없을 때, M개의 파티에서 과장해서 이야기할 수 있는 파티의 개수를 출력해라. + 진실을 아는 사람과 함께 파티를 보낸 사람 또한 진실을 아는 사람이 된다. 해결 키..

[백준 1976] 여행 가자 (JAVA)

CodingTEST 2023. 8. 26. [백준 1976] 여행 가자 (JAVA) 백준 1976번 문제 - 여행 가자 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 문제 분석 N(전체 도시 개수)하고 M(가고 싶은 도시 개수)을 입력받고, N(1 ≤ i ≤ N)번 N(1 ≤ j ≤ N)개씩 수가 주어진다. 이 수는 i번 나라와 j번 나라의 연결 정보 입력 정보로 1이면 i와 j 나라가 연결되있음을 의미 가고 싶은 도시 M개를 입력 받는다. 가고 싶은 도시들이 다 연결되어 있어 모두 갈 수 있을 경우 YES, 아닐 경우 NO 출력 해결 키 포인트 유니온 파인드(union-find) 개념 사..

[백준 1717] 집합의 표현 (JAVA)

CodingTEST 2023. 8. 26. [백준 1717] 집합의 표현 (JAVA) 백준 1717번 문제 - 집합의 표현 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 문제 분석 N개의 수가 주어지면 N개는 각각 다른 집합으로 구성된다. M개의 수식이 주어지며, 수식은 다음 2가지 종류가 있다. 0 a b : b 집합을 a 집합에 포함 시킨다. 1 a b : a와 b가 동일한 집합이면 YES, 아니면 NO 출력 해결 키 포인트 유니온 파인드(union-find) 개념 사용 0도 포함되므로 배열 구현할 때, N개 배열 생성하고 a,b에서 -1을 하면 안된..

이전 1 다음

티스토리툴바