[C] 백준 - 3584번: 가장 가까운 공통 조상

9월 14일(목) - 트리 (3584번)

3584번: 가장 가까운 공통 조상

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 입력은 테스트케이스의 개수인 T,

   테스트케이스마다 노드의 개수 N,

   N-1개의 줄에 A, B를 입력받아야하며

   마지막 줄인 N번째 줄에 가장 가까운 공통 조상을 구해야하는 두 노드가 주어진다

- 그러므로 parents[ 10001 ]과 visited[ 10001 ] 을 전역변수로 선언한다

- while( T--) 조건문안에서

  for문을 N번 돌리면서 visited[ ]는 false로, parents[ ]는 i 값으로 저장하고

  for문을 N-1번 돌리면서 parents[ B ] = A 를 통해서, B의 부모노드가 A라는 것을 저장해준다

- 공통조상을 구해야하는 두 노드가 주어지면, visited[ ]는 true로 바꾸고

- 출력은 테스트케이스마다 가장 가까운 공통 조상을 출력한다

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

		// 수정 전
        
		while (true)
		{
			if (visited[v])
			{
				printf("%d\n", v);
				break;
			}
			v = parent[v];
		}
		
        	// 수정 후

		while (true)
		{
			if (visited[v] == true || v == parent[v])
			{
				break;
			}
			else
			{
				v = parent[v];
			}
		}

1. 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

(풀이출처 -> https://restudycafe.tistory.com/396)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>
#include <stdbool.h>

int parent[10001];
bool visited[10001];

int main(void)
{
	int T, N, A, B, u, v;
	scanf("%d", &T);

	while (T--)
	{
		scanf("%d", &N);

		for (int i = 1; i <= N; i++)
		{
			visited[i] = false;
			parent[i] = i;
		}

		for (int i = 0; i < N - 1; i++)
		{
			scanf("%d %d", &A, &B);
			parent[B] = A;
		}

		scanf("%d %d", &u, &v);
		visited[u] = true;

		while (u != parent[u])
		{
			u = parent[u];
			visited[u] = true;
		}
	
		while (true)
		{
			if (visited[v] == true || v == parent[v])
			{
				break;
			}
			else
			{
				v = parent[v];
			}
		}

		printf("%d\n", v);
	}

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ