[백준] no11725: 트리의 부모 찾기

문제

트리의 루트는 1이다.
N : 노드의 개수
둘째줄부터 N-1개의 간선이 주어진다. (N개의 노드를 연결하므로)

2번 노드부터 순차적으로 각 노드의 부모 노드 번호를 출력.

문제 링크 : https://www.acmicpc.net/problem/11725

---

원리

트리를 미리 만들고, BFS로 구함.

레퍼런스 코드 스니펫에서 보면, 0번 인덱스부터 저장 및 탐색하고 2번 인덱스부터 출력을 위해

-1을 빼주고 시작, 1을 더해주고 종료하는 것을 주의

---

나의 코드

[실패] 시도1. 이중 배열 탐색 방식

1) N*N의 boolean형 이중배열을 만든다.

2) 각 간선의 첫 번째 노드를 행, 두 번째 노드를 열로 보고 해당 칸에 체크한다.

3) 2번부터 순차적으로 탐색하여, 만약 N번 행 또는 N번 열에서 true인 부분이 있다면, 해당 열 또는 행을 출력한다.

private static boolean[][] map;
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());
    map = new boolean[N+1][N+1];
    for(int i=0 ; i<N-1 ; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int low = Integer.parseInt(st.nextToken());
        int cul = Integer.parseInt(st.nextToken());
        map[low][cul] = true;
    }

    OUTER : for(int i=2 ; i<=N ; i++) {
        for(int j=1 ; j<=N ; j++) {
            if(map[i][j]) {
                bw.write(""+j+"\n");
                continue OUTER;
            }
            if(map[j][i]) {
                bw.write(""+j+"\n");
                continue OUTER;
            }
        }
    }

    bw.close();
}

[로컬 성공/백준 메모리초과] 시도2. BFS를 이용한 트리구조 탐색

1) 노드(Node)객체는 부모 노드 값, 자식 노드 값을 갖는다.

2) 행 또는 열이 1인 곳 중, 1과 연결된 노드를 우선적으로 Deque에 넣는다.

3) 1번부터 돌면서 현재 구하고자 하는 노드와 Child값이 같다면, 해당 객체 안에서 부모노드값을 출력한다.

private static int N;
private static boolean[][] map, visit;
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
    N = Integer.parseInt(br.readLine());
    map = new boolean[N+1][N+1];
    for(int i=0 ; i<N-1 ; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int low = Integer.parseInt(st.nextToken());
        int cul = Integer.parseInt(st.nextToken());
        map[low][cul] = true;
    }

    for(int goal=2 ; goal<=N ; goal++) BFS(goal);

    bw.close();
}

private static void BFS (int goal) throws IOException {
    Deque<Node> dq = new ArrayDeque<>();
    visit = new boolean[N+1][N+1];
    for(int i=1 ; i<=N ; i++) {
        for(int j=1 ; j<=N ; j++) {
            if(i==1 && map[i][j]) {
                dq.add(new Node(1, j));
                visit[1][j] = true;
            }
            if(j==1 && map[i][j]) {
                dq.add(new Node(1, i));
                visit[1][i] = true;
            }
        }
    }

    while(!dq.isEmpty()) {
        Node now = dq.poll();
        if(now.Child==goal) {
            bw.write("" + now.Parent + "\n");
            break;
        }

        for(int next=1 ; next<=N ; next++) {
            if(map[now.Child][next]) {
                visit[now.Child][next] = true;
                dq.add(new Node(now.Child, next));
            }
            if(map[next][now.Child]) {
                visit[next][now.Child] = true;
                dq.add(new Node(now.Child, next));
            }
        }
    }
}

private static class Node {
    private int Parent, Child;
    public Node(int parent, int child) {
        this.Parent = parent;
        this.Child = child;
    }
}

---

레퍼런스

참고링크 : darak님의 벨로그

트리를 그리고 BFS로 해결하는 것은 맞지만, 한 번의 탐색에서 모든 부모노드를 체크한다.

public class Main {
    private static int N;
    private static ArrayList<ArrayList<Integer>> tree;
    private static boolean[] visit;
    private static int parents[];
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());

        // 한번의 BFS에서 모든 부모노드를 구하는 방식
        tree = new ArrayList<>();
        for(int i=0 ; i<N ; i++) tree.add(new ArrayList<>());

        StringTokenizer st;
        for(int i=0 ; i<N-1 ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int node1 = Integer.parseInt(st.nextToken())-1;
            int node2 = Integer.parseInt(st.nextToken())-1;
            tree.get(node1).add(node2);
            tree.get(node2).add(node1);
        }
        parents = new int[N];
        visit = new boolean[N];
        BFS();
        for(int i=1; i<N ; i++) bw.write(parents[i]+1+"\n");

        bw.close();
    }

    private static void BFS() {
        Deque<Integer> dq = new ArrayDeque<>();
        dq.add(0);
        visit[0] = true;

        while(!dq.isEmpty()) {
            int now = dq.poll();
            for(int next : tree.get(now)) {

                // 새로운 노드 방문시, 방문체크와 동시에 해당 노드의 부모노드를 저장
                if(!visit[next]) {
                    visit[next] = true;
                    dq.add(next);
                    parents[next] = now;
                }
            }
        }
    }