백준 - 사촌

문제 설명

사촌 노드의 개수를 구하는 문제이다.

사촌 노드의 사전적 정의

• 같은 레벨의 노드 여야 한다.
  • 단 같은 부모를 가지면 안된다(:= 형제 노드이면 안된다)

생각한 아이디어

1. Map을 이용하여 같은 레벨의 노드를 담아냈다. 하지만 형제노드인지를 구별 할 수 없었다. FAIL
2. 각 노드의 부모를 나타내는 배열을 선언하고 같 정점의 값이 부모를 향하도록 구성하였다. SUCCESS

풀이

public static void main(String[] args) throws IOException {
		StringBuilder answers = new StringBuilder();
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

		while (true) {
			StringTokenizer st = new StringTokenizer(reader.readLine());

			int n = Integer.parseInt(st.nextToken());
			int target = Integer.parseInt(st.nextToken());

			if (n == 0 && target == 0) {
				break;
			}

			int arr[] = new int[n];
			int targetIdx = 0;
			st = new StringTokenizer(reader.readLine());
			for (int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(st.nextToken());

				if (arr[i] == target) {
					targetIdx = i;
				}
			}

			int parent[] = new int[n];
			parent[0] = -1;
			int parentIdx = -1;
			// 간선의 정보를 바탕으로 트리 만들기 (core) -> 답을 도출해내야 한다.
			for (int i = 1; i < n; i++) {
				if (arr[i - 1] + 1 != arr[i]) { // 연속 적이지 않다면
					parentIdx++;
				}

				parent[i] = parentIdx;
			}

			int cousin = 0;
			for (int i = 1; i < n; i++) {
				if (parent[i] == parent[targetIdx]) {
					// 같은 부모 이면 := 형제 노드이면
					continue;
				} else if (parent[parent[i]] == parent[parent[targetIdx]]) {
					// 부모의 부모가 같다면 := 사촌이 맞다면
					cousin++;
				}
			}

			answers.append(cousin).append("\\n");
		}

		System.out.println(answers);
	}

주의 사항

해당 코드에 if 문의 순서 또는 하나로 합치게 되면 이슈가 생긴다.

왜냐하면 부모의 부모를 찾는 과정에서 루트 노드 바로 밑에있는 자식노드를 탐색하게 되면

parent[ -1 ]로 대입될 수 있기 때문에 예외가 발생한다.

그래서 먼저 if문에 부모가 같은지부터 판별하고 → 그다음 부모의 부모를 탐색해야 한다.

for (int i = 1; i < n; i++) {
				if (parent[i] == parent[targetIdx]) {
					// 같은 부모 이면 := 형제 노드이면
					continue;
				} else if (parent[parent[i]] == parent[parent[targetIdx]]) {
					// 부모의 부모가 같다면 := 사촌이 맞다면
					cousin++;
				}
}