[BOJ] 2644 촌수계산

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

Note

헛다리를 너무 많이 짚은 문제..
이번에는 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;
}

2018-12-28 21:57:00에 Tistory에서 작성되었습니다.