백준 9489 (사촌) <부모 노드 활용>

문제

9489번: 사촌

 

왼쪽 그림과 같이 n개의 노드가 주어지면 트리를 형성할 수 있다.

트리는 연속된 숫자여야 한다. 연속된 숫자는 하나의 집합이다.

연속된 숫자가 아니면 다음 집합으로 넘어간다.

이 때 K가 주어지는데 K의 사촌 수를 구하는 문제이다.

사촌 이란 두 노드의 부모는 다르지만, 두 부모가 형제(sibling)일 때 두 노드를 사촌이라고 한다.

n개의 수는 오름차순으로 주어진다.

왼쪽의 예시는 1, 3, 4, 5, 8, 9, 15, 30, 31, 32 이다.

 

 

---

처음에는 단순히 정렬된 수를 보고 for 문을 돌면서 집합의 번호와 depth를 설정해 K와 같은 depth이면서 다른 집합의 번호의 개수를 세려 했지만 어느부분인지는 모르겠지만 틀렸다.

다른 사람의 코드를 참고한 결과 parent배열을 사용해 i 노드의 부모노드를 저장해주었다. 코드를 보면 아래와 같다.

int []arr = new int[n+1];
            int []parent = new int[n+1];
            parent[0] = -1;
            arr[0] = -1;
            int target=-1;
            int idx = -1;
            st = new StringTokenizer(br.readLine());
            for(int i=1;i<=n;i++){
                arr[i] = Integer.parseInt(st.nextToken());

                if(arr[i] == k)target = i;
                if(arr[i] != arr[i-1] + 1)idx++; //연속 되지 않을 경우 집합 바꾸기
                parent[i] = idx;
            }

idx를 이용해 parent 배열을 초기화 해주었다.

n= 10이고 수가 1, 3, 4, 5, 8, 9, 15, 30, 31, 32로 주어지면 parent 배열을 아래와 같다.

1	2	3	4	5	6	7	8	9	10
0	1	1	1	2	2	3	4	4	4

int ans = 0;
for(int i=1;i<=n;i++){
	if(parent[i] != parent[target] && parent[parent[i]] == parent[parent[target]])
    	ans++;
}

target의 부모와 같지 않고 target의 부모의 형제이면 ans++ 해준다.

형제라는 것은 결국 같은 부모를 갖기 때문이다.

---

전체 코드이다.

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        while(true){
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            if(n == 0 && k == 0)break;

            int []arr = new int[n+1];
            int []parent = new int[n+1];
            parent[0] = -1;
            arr[0] = -1;
            int target=-1;
            int idx = -1;
            st = new StringTokenizer(br.readLine());
            for(int i=1;i<=n;i++){
                arr[i] = Integer.parseInt(st.nextToken());

                if(arr[i] == k)target = i;
                if(arr[i] != arr[i-1] + 1)idx++;
                parent[i] = idx;
            }
            
            int ans = 0;
            for(int i=1;i<=n;i++){
                if(parent[i] != parent[target] && parent[parent[i]] == parent[parent[target]])
                    ans++;
            }
            System.out.println(ans);

        }
    }
}