[SWEA] 5. 그래프 탐색

SWEA의 5번째 내용은 그래프 탐색에 관한 내용이었다. 그래프 탐색에는 여러 가지 이론들이 있지만 강의에서는 대표적인 DFS와 BFS에 관한 내용이 나왔다. 강의는 너무 쉬운 내용이라 금방 넘겼고 바로 문제 풀이에 들어갔다.

 

기초 DFS와 BFS라는 제목을 가진 문제 두 개를 풀었는데 DFS와 BFS를 활용하는 문제였는데 문제가 굉장히 불친절했다. 입력값도 트리를 파악할 수 없게 만들어 직접 출력해보아야 했고 입력값에 쓰레기 값도 들어있어서 문제 풀이에 굉장히 난항이 있었다. BFS 문제는 그보다 나았지만 행과 열 순서로 주지 않고 열 과 행 순서로 좌표를 주고 인덱스는 (0,0)부터 주지만 실제 좌표는 (1,1)부터 시작하여 굉장히 혼란스러웠다.

 

그리고 난 후 기본문제를 풀기 시작했는데 프로세서 연결하기 문제였다. 한 좌표에서 벽으로 선을 뻗는데 여러가지 방향으로 뻗을 수 있어 재귀로 짰는데 짜면 짤수록 모든 경우를 확인하는 완전 탐색으로 풀고 있어서 이 코드는 틀린 것 같았지만 코드 짜던 게 아까워서 마저 짰더니 역시나 시간 초과가 떴다. 코드에 손 대기 전에 조금 더 생각 보아야겠다! 쉬운 내용이라고 문제가 쉽게 풀리라는 법은 없나 보다.

 

다른 문제로 영준이의 진짜 BFS 문제를 풀었다. LCA 알고리즘을 활용하여 풀 수 있다고 먼저 힌트를 받아 LCA 알고리즘을 공부하고 문제 풀이를 시작했다. 하지만 풀이가 잘 진행되지 않았다. 여러가지 실수 및 모르는 것들이 있었는데

1. 연습에서는 floor(log2(N))를 define 해서 사용하였는데 이번에는 그냥 17이라고 바로 써서 LCA 함수의 i = MAX_H로 시작하는 부분을 바로 17 로 바꾸었더니 접근할 수 없는 인덱스였다.

2. LCA를 공부하면서도 굳이 인접행렬에 자식노드->부모노드는 할 필요는 없다고는 생각했는데 이 문제에서는 하면 안되었다. 이 부분은 연습 문제도 바꾸어 보아야겠다.

3. depth를 구할때 DFS 로 구했는데 SWEA 는 스택메모리가 백준보다 작아서 BFS로 depth를 구해야 했다.

4. 공통 조상이 주어진 두 노드중 하나가 아닌 경우에도 sum 을 더하는 것을 분기할 필요가 없었다. 

5. 주어진 입력값을 잘 안봐서 이진트리의 순서로 주어진다고 착각했는데 이진트리도 아니었고 순서도 뒤죽박죽이었다.

6. 다른 블로그들을 통해 공부할때 parent 의 default 값을 -1로 설정하는 곳이 많았는데 Visual Studio 와 백준 사이트에서는 -1이 인덱스로 들어가도 무시가 되는데 채점 사이트에서는 그렇지 않았다. 백준 문제를 풀었던 코드를 디버깅 해보니 인덱스로 -1이 들어가는 부분이 꽤 많았다. 이 부분은 당연히 잘못된 접근이라고 어디서든 안될 줄 알았는데 신기했다.

위와 같은 실수들을 친구의 도움도 받아가며 이겨내고 결국 문제를 풀긴 했다. 그래도 새로운 지식과 LCA 연습이 된 것 같아 의미는 있던 것 같다!

#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define swap(a,b) {int tmp=a; a = b ; b= tmp;}

vector<int> adj[100001];
queue<int> q;
int parent[100001][19];
int depth[100001];
int N;
long long sum;

void make_depth(int node) {
	int prev = 1;
	for (int next : adj[1]) {
		q.push(next);
		depth[next] = 1;
	}
	while (!q.empty()) {
		int cur = q.front(); q.pop();
		for (int next : adj[cur]) {
			q.push(next);
			depth[next] = depth[cur] + 1;

		}
	}
}

void connect() {
	for (int k = 1; k < 19; k++) {
		for (int cur = 1; cur <= N; cur++) {
			parent[cur][k] = parent[parent[cur][k - 1]][k - 1];
		}
	}
}

int LCA(int u, int v) {
	if (depth[u] < depth[v])
		swap(u, v);
	int diff = depth[u] - depth[v];
	for (int i = 0; diff != 0; i++) {
		if ((diff & 1))
			u = parent[u][i];
		diff = diff >> 1;
	}
	if (u != v) {
		for (int i = 16; i >= 0; i--) {
			if (parent[u][i] != 0 && parent[u][i] != parent[v][i]) {
				u = parent[u][i];
				v = parent[v][i];
			}
		}
		u = parent[u][0];
	}
	return u;
}

void BFS() {
	int prev = 1;
	for (int next : adj[1]) {
		q.push(next);
	}
	while (!q.empty()) {
		int cur = q.front(); q.pop();
		for (int next : adj[cur]) {
			q.push(next);

		}
		int ac = LCA(cur, prev);
		sum += depth[cur] + depth[prev] - 2 * depth[ac];
		prev = cur;
	}
}

int main(int argc, char** argv)
{
	int test_case;
	int T;
	//freopen("input.txt", "r", stdin);
	cin >> T;
	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> N;
		memset(parent, 0, sizeof(parent));
		memset(depth, -1, sizeof(depth));
		q = queue<int>();
		depth[1] = 0; sum = 0;
		for (int i = 0; i <= N; i++) {
			adj[i].clear();
		}
		for (int i = 2; i <= N; i++) {
			cin >> parent[i][0];
			adj[parent[i][0]].push_back(i);
		}
		make_depth(1);
		connect();
		BFS();
		cout << "#" << test_case << " " << sum << "\n";
	}

	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}