[백준] 11725번 - 부모의 트리찾기 (Java)(○)

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

[첫번째]

<문제 분석>

1. 입력함수에서 인접행렬로 정점과 간선을 표현하자.

2. 방향이 없기 때문에 양쪽 모두 행렬로 표현해야 한다.

3. dfs 파라미터는 다음 정점 번호를 넘겨주자.

4. 1번의 루트 고정이므로 2번 정점부터 각 정점의 부모 노드가 뭔지 출력하면 된다.

5. 위의 출력 예제에서 2번 정점의 부모는 4번, 3번의 부모는 6번인 셈이다.

6. 1번부터 dfs 탐색을 해서 이미 방문한 노드가 부모인 셈이므로 그 번호를 출력하면 된다.

 

<코드 구현 - 인접행렬>

import java.util.*;

/*
[백준] 11725번 - 부모의 트리찾기 (Java)
*/

public class Main {
    static int N;
    static int A[][];
    static boolean visited[];

    void InputData() {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        A = new int[N+1][N+1];
        for (int i=0; i<N-1; i++) {
                int s = in.nextInt();
                int e = in.nextInt();
                A[s][e] = 1;
                A[e][s] = 1;
        }
    }
    
    void DFS(int v) {
        visited[v] = true;

        for (int i=1; i<=N; i++) {
            if (A[v][i] == 0) continue;
            if (visited[i]) {
                parent[v] = i;
                continue;
            }
            DFS(i);
        }
    }

    int parent[];
    void Solve() {
        visited = new boolean[N+1];
        parent = new int[N+1];
        DFS(1);
        for (int x : parent) {
            if (x == 0) continue;
            System.out.println(x);
        }

    }
    
	public static void main(String[] args) {
		Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

<제출 결과 - 메모리 초과>

<코드 구현 - 인접리스트>

import java.util.*;

/*
[백준] 11725번 - 부모의 트리찾기 (Java)
*/

public class Main {
    static int N;
    ArrayList<Integer> A[];    
    static boolean visited[];

    void InputData() {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        A = new ArrayList[N+1];
        for (int i=1; i<=N; i++)
            A[i] = new ArrayList<Integer>();
        
        for (int i=0; i<N-1; i++) {
            int s = in.nextInt();
            int e = in.nextInt();
            A[s].add(e);
            A[e].add(s);
        }
    }
    
    void DFS(int v) {
        visited[v] = true;
        for (int x : A[v]) {
            if (!visited[x]) {
                parent[x] = v;
                DFS(x);
            }
        }
    }

    int parent[];
    void Solve() {
        visited = new boolean[N+1];
        parent = new int[N+1];
        for (int i=1; i<=N; i++) {
            if (visited[i]) continue;
            DFS(i);
        }
        for (int i=2; i<=N; i++) {
            System.out.println(parent[i]);
        }

    }
    
	public static void main(String[] args) {
		Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

 

<복기>

익숙했던 인접행렬 방식으로 사용하니 메모리 제한이 걸린 문제에서는 실패하는 경우가 생긴다. 

앞으로는 왠만하면 메모리 이점이 있는 인접리스트 방식으로 사용해서 풀어야겠다.

 

[두번째]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;

/*
1. 그래프를 인접리스트 형태로 구현한다.
2. 방향성이 없는 그래프이지만 root가 1번으로 정해지면서 트리의 형태가 된다.
3. root부터 연결된 자식 노드로 탐색을 시작한다.
4. Solve()에서 loop를 돌릴필요는 없이 DFS(1)/BFS(1)로 시작하면 된다.
5. 현재 방문한 노드에서 자식 노드가 있고, 이미 방문한 노드가 아니라면 이것은 부모노드가 된다.
*/

public class Main {
    static int N;
    static boolean visited[];
    static int parent[];
    static ArrayList<Integer> A[];

    void DFS(int now) {
        visited[now] = true;
        // v노드의 연결된 자식 노드는 다 탐색
        for (int next : A[now]) {
            if (visited[next]) continue; // 방문한 노드면 패스
            parent[next] = now; // x의 부모노드는 v이다
            DFS(next);
        }
    }

    void BFS(int root) {
        Queue<Integer> Q = new LinkedList<>();
        visited[root] = true;
        Q.add(root);
        while(!Q.isEmpty()) {
            int now = Q.poll();
            // v노드의 연결된 자식 노드는 다 탐색
            for (int next : A[now]) {
                if (visited[next]) continue; // 방문한 노드면 패스
                visited[next] = true;
                Q.add(next);
                parent[next] = now; // x의 부모노드는 v이다
            } 
        }
    }
    
	void Solve() {
        visited = new boolean[N+1];
        parent = new int [N+1];
        // root부터 탐색 시작
        //DFS(1);
        BFS(1);
        // 부모노드 출력(2 to N)
        for (int i=2; i<=N; i++) {
            System.out.println(parent[i]);
        }
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        // 인접리스트 구현
        A = new ArrayList[N+1]; // 전체 ArrayList[] 할당
        for (int i=1; i<=N; i++)
            A[i] = new ArrayList<Integer>(); // 각 A[i]에 ArrayList 할당
        
        for (int i=0; i<N-1; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            A[s].add(e);
            A[e].add(s);
        }
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }
}

<후기>

1. Solve()에서 쓸데없이 for문을 돌리던 것을 제거했다. (FloodFill알고리즘이 아닌데 잘못 사용했었음)

2. DFS와 BFS의 시간복잡도는 큰 차이가 없다.