21606번 - 아침 산책
문제 풀이 시간 : 1시간
문제 요약 :
- •
서현이는 아침 산책을 한다.
- •
N개의 장소를 N-1 개의 길의 트리로 나타낸다.
- •
각 장소는 실내와 실외로 나눠진다.
- •
시작점과 도착점은 실내로 해야한다.
- •
경로의 중간에 실내가 있으면 안된다.
- •
서로 다른 산책 경로가 몇 가지가 있을까?
문제 풀이
처음엔 그냥 dfs로 전부 다 탐색해보면 되는거 아닌가?
라는 생각이었는데 조건을 보니 장소의 개수가 최대 200,000개라서 모든 장소에 대해 탐색하면 시간복잡도가 어마어마해지는 것을 알 수 있다.
근데 딱히 다른 방법이 떠오르지 않아서 그냥 일단 코드를 짜보았다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;
public class Main {
public static int N, result = 0;
public static int[] arr;
public static ArrayList<Integer>[] road;
public static HashSet<Integer> inside;
public static boolean[] visited;
public static int find(int start, int next) {
if(visited[next])
return 0;
if (start!=next && inside.contains(next)) {
return 1;
}
visited[next] = true;
int temp = 0;
for (int i = 0; i < road[next].size(); i++) {
temp += find(start ,road[next].get(i));
}
return temp;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new int[N];
road = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
road[i] = new ArrayList<>();
}
inside = new HashSet<>();
String input = br.readLine();
for (int i = 0; i < N; i++) {
if (input.charAt(i) == '1') {
inside.add(i + 1);
arr[i] = 0;
} else {
arr[i] = 1;
}
}
for (int i = 0; i < N - 1; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
road[a].add(b);
road[b].add(a);
}
for (int a : inside) {
visited = new boolean[N + 1];
result += find(a,a);
}
System.out.println(result);
}
}
이 문제는 서브태스크 문제라서 60%까지는 맞았지만 그 이후는 틀렸다.
따라서 총 200점 중 108점을 받았다.
dp인가 싶기도 하고 여러 방법을 생각해보았지만
아무리 생각해도 다른 방법이 떠오르지 않아서 결국 SOS를 쳤다.
내 풀이의 문제점은 실내를 기준으로 탐색을 한 것이다.
접근을 다르게 해서 실외를 기준으로 가능한 경로를 찾는 것이 더 쉽다고 한다.
아래와 같은 경우를 보자.
실내에서 출발했을 때 다른 실내로 도착할 수 있는 경우의 수는 6이다.
N개의 실내 중 하나를 고르고, 나머지 N-1개 중에 하나를 더 고르는 것이므로
총 경우의 수는 N(N-1)이 된다.
그럼 만약 실외가 더 많은 경우는 어떻게 될까?
이런 경우에도 똑같이 적용이 가능하다고 한다.
전체 실내의 개수는 14개이므로 총 경우의 수는 14*13 = 182개이다.
그럼 실내 개수 다 주어지는데 그대로 계산하면 개빠르게 풀 수 있는거 아니냐?
라는 생각을 할 수 있다.
이런 경우를 보자.
실외의 중간에 실내가 끼여있다.
우리는 가운데 실내를 기준으로 오른쪽 한세트, 왼쪽 한세트로 나눠서 계산해야한다.
따라서 우리는 dfs로 모든 실외를 탐색하며 해당 실외와 연결된 실내의 개수들을 모두 파악해주면된다.
이렇게 하면 완벽할까??
한가지 경우가 더 있다.
우리는 이런 경우도 파악해줘야 한다.
이것도 2가지의 경우가 있는 것이므로 추가해주어야한다.
이제 진짜 완벽하다고 생각하나???????????????????
그렇다.
최종 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;
public class Main {
public static int N, result = 0;
public static ArrayList<Integer>[] road;
// public static HashSet<Integer> outside;
public static int[] arr;
public static boolean[] visited;
public static int find(int node) {
int temp = 0;
for (int a : road[node]) {
if (arr[a] == 0) {
if (!visited[a]) {
visited[a] = true;
temp += find(a);
}
}
else {
temp++;
}
}
return temp;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
road = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
road[i] = new ArrayList<>();
}
arr = new int[N + 1];
String input = br.readLine();
for (int i = 1; i <= N; i++) {
if (input.charAt(i-1) == '1') {
arr[i] = 1;
} else {
arr[i] = 0;
}
}
for (int i = 0; i < N - 1; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
if (arr[a] == 1 && arr[b] == 1) {
result += 2;
}
road[a].add(b);
road[b].add(a);
}
visited = new boolean[N + 1];
for (int i = 1; i <= N; i++) {
int temp = 0;
if (arr[i] == 0) {
if (!visited[i]) {
visited[i] = true;
temp += find(i);
}
}
result += temp * (temp - 1);
}
System.out.println(result);
}
}