[코딩테스트] 트리의 부모 찾기

ㆍ문제

ㆍ통과 못한 나의 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        // 횟수값을 저장한 변수
        int seq = Integer.parseInt(bf.readLine());
        // 부모노드값을 저장한 배열
        int[] valueArr = new int[seq + 1];
        // 실질적인 동작을 가지고 있는 큐
        LinkedList<String[]> queue = new LinkedList<>();
        // BufferedReader로 가져온 값을 저장한 변수들
        int aa = 0;
        int bb = 0;
        // 0을 비교해서 확인 -> -1로 값 입력해서 오류없도록 설정
        valueArr[0] = -1;
        valueArr[1] = -1;

		// 모든 동작을 큐에 저장
        for(int i = 1; i < seq; i++) {
            queue.addFirst(bf.readLine().split(" "));
        }

		// 큐가 비일 때까지 실행
        // 0이 아니면 부모노드이기 0을 기준으로 비교
        // 둘 다 0이면 아직 부모노드가 안정해졌기 때문에 다시 queue에 입력
        while(!queue.isEmpty()) {
            String[] a = queue.removeLast();
            aa = Integer.parseInt(a[0]);
            bb = Integer.parseInt(a[1]);
            if(valueArr[aa] != 0) {
                valueArr[bb] = aa;
            } else if(valueArr[bb] != 0) {
                valueArr[aa] = bb;
            } else {
                queue.addFirst(a);
            }
        }

		// 출력
        for(int i = 2; i < valueArr.length; i++) {
            bw.write(String.valueOf(valueArr[i]));
            if(i == valueArr.length - 1) {
                break;
            }
            bw.newLine();
        }

        bw.close();
    }
}

 

ㆍ결과

ㆍ내가 생각하는 통과가 안된 이유

일일이 비교하고 값을 삽입하는 작업을 해서 시간이 많이 잡아먹었기 때문일 것이다.

 

ㆍ수정 후 코드

import java.io.*;
import java.util.*;

public class Main {
	// 횟수용 변수
    static int seq;
    // dfs를 하기위한 배열
    static ArrayList<Integer>[] arr;
    // 노드들을 체크하기 위한 배열
    static boolean[] isVisit;
    // 결과 출력용 배열
    static int[] result;

    public static void main(String[] args) throws IOException {
    	// 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // 각 변수, 배열 초기화
        seq = Integer.parseInt(br.readLine());
        arr = new ArrayList[seq + 1];
        result = new int[seq + 1];
        isVisit = new boolean[seq + 1];

		// dfs를 하기위한 배열내부를 초기화
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

		// dfs배열에 값 삽입
        for (int i = 1; i < seq; i++) {
            String[] s = br.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);

            arr[a].add(b);
            arr[b].add(a);
        }

		// dfs를 위한 초기세팅
        isVisit[1] = true;
        // dfs실행
        dfs(1);

		// 출력
        for (int i = 2; i <= seq; i++) {
            System.out.println(result[i]);
        }
    }


	// dfs를 하기위한 메소드
    public static void dfs(int i) {
    	// true를 배열에 삽입하므로서 해당 노드를 확인했다는 표시
        isVisit[i] = true;

		// 내부 정수값들을 확인하는 반복문
        // 만약 해당 정수값의 노드를 확인하지 않았다면
        // 결과출력 배열에 값 삽입 후 재귀
        for (int a : arr[i]) {
            if (!isVisit[a]) {
                result[a] = i;
                dfs(a);
            }
        }
    }
}

 

ㆍ느낀 점

알고리즘 공부를 나태하게 한 것을 후회하게 되는 문제였다.

그리고 트리부터 DFS같은 것들에 익숙하지 않아서 시간이 오래걸려서 많이 힘들었다.

앞으로 비슷한 문제나 해당 알고리즘문제를 잘 풀기위해 개념을 많이 공부를 해야겠다는 생각을 들었다.