개요

백준 2644번: 촌수 계산

• 입력
  사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.

각 사람의 부모는 최대 한 명만 주어진다.

• 출력
  입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다.

접근 방식

1. bfs를 통해 각 노드의 레벨이 몇만큼 차이나는지 구하려했다.
2. 그래프 클래스를 작성하여 시작노드와 타겟노드를 매개변수로 받는 bfs함수를 작성하였다.
   bfs함수에 시작노드와 타겟 노드를 넣으면 그 둘이 몇레벨만큼 떨어져있는지 출력한다.

코드

#include<iostream>
#include<queue>
using namespace std;

int people = 0, targetPersonA = 0, targetPersonB = 0, relationsAmount= 0;

class Graph {
public:
	int Nodes;
	vector<vector<int>> adj;

	Graph(int N) :Nodes(N) {
		adj.resize(N+1);
	}

	void addEdge(int u, int v) {
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	/// <summary>
	/// Node값에서 다른 값 까지 몇 개의레벨이 존재하는지 계산하는 함수
	/// </summary>
	/// <param name="시작 노드"></param>
	void bfs(int Node,int target) {
		//bfs에서 사용될 큐
		queue<int> q;
		//방문 벡터 false로 초기화
		vector<int> visited(Nodes+1, false);
		//q에 임시로 0값 푸시해줌(시작에서 pop해줄것)
		q.push(Node);
		//visited에 true넣어줌
		visited[0]=true;
		//해당 값과 어느정도 떨어져있는지 체크
		int size = 1;
		
		while (!q.empty()) {
			//큐 사이즈 임시변수에 저장(반복문에서 종결조건 변하면 안되므로)
			int qSize = q.size();

			//각 큐에 사이즈가 한 레벨에 들어있는 노드들의 갯수이므로 반복문이 끝나면 레벨하나가 증가해서 탐색하게된다.
			for (int i = 0; i < qSize; i++) {
				//큐의 front값 cur에 저장
				int cur = q.front();
				//큐 pop
				q.pop();
				//큐의 front값의 인접노드(다음 레벨)들에 대해 반복
				for (int elem : adj[cur]) {
					//elem노드를 방문하지 않았다면
					if (!visited[elem]) {
						//해당 노드가 타겟이라면 지금까지 size 출력
						if (elem == target) {
							cout << size;
							return;
						}
						//방문했다고 체크
						visited[elem] = true;
						//큐에 해당 노드 push
						q.push(elem);
					}
				}
			}
			//level 증가
			size ++ ;
		}
		//반복문을 다 돌았는데 타겟노드를 발견못하면 다른 컴퍼넌트이므로 -1 출력
		cout << -1;
	}
};

Graph* graph;

void input() {
	int tmp1=0, tmp2 = 0;
	cin >> people >> targetPersonA >> targetPersonB >> relationsAmount;
	graph = new Graph(people);
	for (int i = 0; i < relationsAmount; i++) {
		cin >> tmp1 >> tmp2;
		graph->addEdge(tmp1, tmp2);

	}
}
void solution() {
	graph->bfs(targetPersonA, targetPersonB);
}


int main() {

	input();
	solution();
}

문풀후생

vector<int> v(Nodes, false);

이렇게 벡터를 초기화할시 Nodes 인덱스까지 0으로 초기화하게 된다.
v벡터의 0번째 인덱스를 1로 바꿔주려 할 때, v[0]=1 이 아니라
바보같이 여기다가 v.push_back(1)을 하여 Nodes인덱스 다음 인덱스에 1이 들어갔다.