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);
}
}함께 읽으면 좋은 글
5430번 - AC
함수 R은 배열을 뒤집는 연산 함수 D는 첫 번째 원소를 버리는 연산 단, 배열이 비어 있을 때 D를 수행하면 error 주어진 함수 문자열을 순서대로 수행한 뒤 최종 배열을 출력하는 문제 처음에는 문제 설명 그대로 R이 나올 때마다 배열을 실제로 뒤집고, D가 나오면 맨 앞…
1966번 - 프린터 큐
여러 문서가 큐에 들어 있고, 각 문서마다 중요도가 있음 맨 앞 문서를 확인했을 때, 더 높은 중요도의 문서가 뒤에 하나라도 있으면 맨 뒤로 보냄 그렇지 않으면 바로 인쇄 특정 위치의 문서가 몇 번째로 인쇄되는지 구하는 문제 이 문제는 프린터의 동작을 그대로 구현하면 되는…
1158 - 요세푸스 문제
1번부터 N번까지 사람이 원형으로 앉아 있음 순서대로 K번째 사람을 제거 모든 사람이 제거될 때까지 반복 제거되는 순서를 출력하는 문제 이 문제는 원형으로 순회하면서 K번째를 제거하는 과정을 그대로 구현하면 된다.
2164번 - 카드2
1부터 N까지 카드가 순서대로 쌓여 있음 맨 위 카드를 버리고, 그다음 맨 위 카드를 맨 아래로 옮기는 과정을 반복 마지막에 남는 카드 번호를 구하는 문제 이 문제는 규칙을 찾기보다, 문제에서 하라는 과정을 그대로 구현하면 된다. 카드 더미에서 반복되는 동작은 두 가지다.