https://www.acmicpc.net/problem/11725
트리의 부모 찾기
트리 문제다.
문제에서 1이 트리의 root로 고정되어 있기때문에 1을 시작으로 dfs를 하면 쉽게 풀릴것이라 예상했다.
- 입력으로 받은 두 정점들을 인접행렬로 구현하여 dfs 방법을 통해 부모들을 출력하는데 성공했다.
예제는 통과가 되어 그대로 제출!!
-
'메모리 초과'라는 결과를 받았다.
-
n의 최대치가 10만이기 때문에 이를 인접배열의 형태로 구현을 한다면 10만X10만이기 때문에 메모리 제한에 걸리게 된다.
그렇다면 인접리스트다!!
- 인접리스트로 두 정점간의 관계를 구현했다.
- 메모리 초과는 극복했다.
- 하지만 시간초과를 만났다.
기존에 작성했던 코드는 2중 for문을 사용했기때문에 n이 10만이라면 시간초과도 발생할 수 있다는 점을 간과했다.
여기서 막혔버렸다.
n^2으로 풀리지 않는다면 n으로 풀어야한다는 건데 방법을 잘 몰랐다.
결국 힌트를 봐버렸다.
기존의 코드는 1부터 시작해서 2의 부모찾고 다시 1부터 시작해서 3의 부모찾고...
이런 방식의 반복이었다.
이렇게하니 시간의 낭비가 있을 수 밖에 없었다.
힌트의 핵심은 1부터 dfs로 트리를 순회하면 트리를 순회하면서 자식의 부모를 저절로 찾을 수 있다는 것이다.
1번 예제의 그래프이다.
1. 1번부터 출발하여 dfs를 하면 다음으로 진입할 노드는 4이지만 코드에서는 리스트 형태로 구현했기때문에 먼저 입력받은 6으로 진입한다.
2. 진입하면서 배열에 6의 부모는 1이라고 갱신해준다.
3. 6은 3을 자식으로 가지기 때문에 3으로 진입하면서 배열의 3번째 인덱스 값을 6으로 바꿔준다.
4. 트리를 전체 탐색할 때까지 반복한다.
위와 같은 방법을 사용해서 for문을 한번만 사용하는 것으로 해결이 가능해 시간초과의 문제에서 벗어날 수 있었다.
import java.io.*;
import java.util.ArrayList;
public class Main {
/*static int count = -1;
static int[] dx = {-2, -2, -1, -1, 1, 1, 2, 2};
static int[] dy = {1, -1, 2, -2, 2, -2, 1, -1};*/
//static boolean visited[];
static int n;
//static int graph[][];
static ArrayList<ArrayList<Integer>> queue;
static int list[];
public static void main(String[] args) throws IOException {
// write your code here
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String num = br.readLine();
n = Integer.parseInt(num);
list = new int[n+1];
queue = new ArrayList<>();
for (int i = 0; i <= n; i++) {
ArrayList<Integer> tmp = new ArrayList<>();
queue.add(tmp);
}
for (int i = 0; i < n - 1; i++) {
String[] tmp = br.readLine().split(" ");
int a = Integer.parseInt(tmp[0]);
int b = Integer.parseInt(tmp[1]);
queue.get(a).add(b);
queue.get(b).add(a);
}
dfs(1);
for (int i = 2;i<list.length;i++)
bw.write(list[i] + "\n");
br.close();
bw.close();
}
private static void dfs(int start) {
for (int i = 0; i < queue.get(start).size(); i++) {
int index = queue.get(start).get(i);
if (list[index] == 0) {
list[index] = start;
dfs(index);
}
}
}
}
