Union-Find

Algorithm/Baekjoon Online Judge
[Java] 백준 16957 (체스판 위의 공) Gold 4
Problem : https://www.acmicpc.net/problem/16957 16957번: 체스판 위의 공 크기가 R×C인 체스판이 있고, 체스판의 각 칸에는 정수가 하나씩 적혀있다. 체스판에 적혀있는 정수는 모두 서로 다르다. 체스판의 각 칸 위에 공을 하나씩 놓는다. 이제 공은 다음과 같은 규칙 www.acmicpc.net Approach Union-Find 성격의 개념과 DFS를 혼용하여 풀이한 문제이다. 처음엔 모든 위치를 기준으로 DFS를 수행하여 정답을 구하였다. 이 방법은 TLE(Time Limit Error)가 발생한다. 그러므로 다른 방법을 사용해야 한다. 시간초과를 받은 코드와 정답처리를 받은 코드를 함께 게시하겠다. DFS는 불가피하다. 그러므로 DFS의 횟수를 줄이면서 알고..
→2021.06.20
Algorithm/Baekjoon Online Judge
[Java] 백준 1967 (여행 가자) Gold 4
Problem : https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net Approach 유니온 파인드(Union-Find) 를 활용한 문제였다. 플로이드 와샬 알고리즘으로도 풀이가 가능하다고 한다. (여기서는 다루지 않는다.) 주어진 여행 경로가 어떤 형식으로든 서로 연결되어 길이 존재한다면 가능한 여행경로라고 볼 수 있다. 따라서 입력데이터를 받아 도시 사이에 길이 있다면 같은 집합으로 묶는 작업을 진행한다. 그런 뒤에 여행경로에 있는 모든 도시들..
→2021.04.19
Algorithm/Baekjoon Online Judge
[Java] 백준 1043 (거짓말) Gold 4
Problem : https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net Approach union-find라는 알고리즘을 사용하는 문제였다. 같은 집합으로 묶는 개념이며 알고리즘에서 자주 사용하는 방법이므로 숙지해두면 좋다. 다른 union-find에서와 마찬가지로 parent[] 배열을 사용한다. 로직은 다음과 같다. 진실을 아는 사람들은 parent[x] = x로 초기화를 하고, 진실을 모르는 사람들은 parent[x] = -1로 초기화를 한다. 각 파티마..
→2021.03.29

• 이전
• 1
• 다음