BaekJoon 2644 촌수계산

Link : https://www.acmicpc.net/problem/2644

소스 결과 : 2028 KB / 0 ms

출처 : BackJoon, 한국정보 올림피아드 KOI 1999 중등부 1번

 

설명

헛다리를 너무 많이 짚은 문제..

이번에는 queue를 추가하지 않고 간이 형태로 제작해서 사용

처음에 부모가 누구인지만 아는 방법으로 해결하려고 했으나

자식으로 내려가야 되는 경우가 존재해서 2차원 행렬로 제작하는 방향으로 변환

굳이 2차원 행렬이 아니라 희소행렬로도 가능할 것 같다.

 

소스코드

#include <iostream>


using namespace std;

int relation[100][100];
int check[100];

int queue[100];
int pos = -1;

void push(int val)
{
	queue[++pos] = val;
}

int pop()
{
	return queue[pos--];
}

bool isEmpty()
{
	return pos == -1;
}

int main()
{
	int n;
	int m;
	int t_x, t_y; // target_x, target_y
	int res = 0;
	bool isFind = false;

	cin >> n >> t_x >> t_y >> m;

	for (int i = 0; i < m; i++)
	{
		int x, y; // x - parent, y - child
		cin >> x >> y;
		relation[x][y] = 1;
		relation[y][x] = 1;
	}

	push(t_x);
	check[t_x] = 1;
	while (!isEmpty())
	{
		int cur = pop();

		if (cur == t_y)
		{
			isFind = true;
			res = check[cur] -1 ;
			break;
		}

		for (int i = 1; i < n+1; i++)
		{
			if (relation[cur][i] == 1 && check[i] == 0)
			{
				check[i] = check[cur] + 1;
				push(i);
			}
		}
	}

	if (isFind)
		cout << res;
	else
		cout << -1;

	return 0;
}