백준
백준 1043번 자바 ☆
1. 문제 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 2. 접근 방식 유니온 파인드 방식으로 접근하면 된다. 다만 문제를 풀면서 많이 헤맸던 부분의 반례 테케 하나를 아래에 첨부한다. 10 10 1 1 2 10 1 2 9 2 2 8 3 2 7 4 2 6 5 2 5 7 2 4 8 2 3 9 2 2 10 1 1 1번째 파티부터 N번째 파티까지 순차적으로 union연산을 하며 partyPeople의 요소들을 합집화한다. 그렇기 때문에 같은 집합이지만 fi..
백준 1976번 자바
1. 문제 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 2. 접근 방식 지난번에 풀었던 유니온 파인드 방식과 같으므로 자세한 설명은 패스..유니온 파인드 개념만 알고 있다면 전혀 어렵지 않은 문제다. 3. 구현 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; pub..
백준 1717번 자바
1. 문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 2. 접근방식 유니온 파인드를 활용해 해결하면 된다. 유니온 파인드란? 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union연산과 두 노드가 같은 집합에 속해 있는지 확인하는 find 연산으로 구성되어 있는 알고리즘 왜 쓰는지? 유니온 파인드 알고리즘에서 find 연산은 시간 복잡도를 줄이는 역할을 한다. fin..
백준 1707번 자바
1. 문제 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 2. 접근방식 트리 형태의 그래프인 경우 항상 이분 그래프가 된다. -> 이게 핵심이다. 즉 트리 형태가 아닌 그래프, 다시 말해서 순환형태의 그래프인 경우 이분그래프가 아니게 된다. 예를 들어 1 -> 2-> 3-> 1 형태의 그래프인 경우 1이 속한 집합이 A라고 가정할 때 2는 B -> 3은 A -> 1은 A가 되고 1과 3의 집합이 같기 때문에 이분그래프가 될 수 없다. 3. 구..
백준 18352번 자바
1. 문제 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 2. 접근 방식 처음 접근을 dfs로 했으나 문제에서 주어진 최단거리 K보다 짦은 거리의 노드 관계를 해결하지 못해 포기했다. 사실 '틀렸습니다'가 종종 시간초과를 포함하는 경우가 있어서 정확히 잘못된 부분은 모르겠다. 아마 시간 초과일 확률이 클듯하다.. public static void dfs(int node,..