(프로그래머스) 가장 먼 노드

문제 링크

• 프로그래머스

요약

• Weight 가 없는 graph 는 BFS도 할만하다.

최종 §

결과

• 문제를 읽어보니 BFS로도 별 문제가 없을거같아서 그냥 BFS로 풀었다.
• 그래서 코드는:

#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
 
using namespace std;
 
#define i64 long long
#define PACK(step, idx) (((i64)(step) << 32) | (i64)(idx))
#define UNPACK_STEP(pack) ((int)(((pack) >> 32) & 0xFFFFFFFF))
#define UNPACK_IDX(pack) ((int)((pack) & 0xFFFFFFFF))
 
int solution(int n, vector<vector<int>> edge) {
	map<int, vector<int>> conn;
	set<int> visited;
	queue<i64> q;
	int cur_step = 0, cnt = 1;
	
	for (auto &e : edge) {
		conn[e[0] - 1].push_back(e[1] - 1);
		conn[e[1] - 1].push_back(e[0] - 1);
	}
	
	q.push(PACK(0, 0));
	visited.insert(0);
	
	while (!q.empty()) {
		i64 pack = q.front();
		int step = UNPACK_STEP(pack);
		int idx = UNPACK_IDX(pack);
		q.pop();
 
		if (step != cur_step) {
			cnt = 1;
			cur_step = step;
		} else {
			cnt++;
		}
 
		for (auto next : conn[idx]) {
			// If not visited
			if (visited.find(next) == visited.end()) {
				q.push(PACK(step + 1, next));
				visited.insert(next);
			}
		}
	}
	
	return cnt;
}

• 몇가지 메모:
  • conn 은 위처럼 map 으로 만드는게 좋은듯
  • Graph 에서 BFS할 때는 queue에 push한 직후 바로 visited에 넣어줘야 한다. 실제 node에 방문했을 때 넣으면, queue에 push할 시점에는 visited 처리가 안됐기 때문에, 중복으로 방문하는 경우가 생긴다.

삽질기록 §

결과

코드

#include <string>
#include <vector>
#include <set>
#include <queue>
 
using namespace std;
 
#define i64 long long
#define PACK(step, idx) (((i64)(step) << 32) | (i64)(idx))
#define UNPACK_STEP(pack) ((int)(((pack) >> 32) & 0xFFFFFFFF))
#define UNPACK_IDX(pack) ((int)((pack) & 0xFFFFFFFF))
 
int solution(int n, vector<vector<int>> edge) {
	vector<vector<bool>> conn(n, vector<bool>(n, false));
	set<int> visited;
	queue<i64> q;
	int cur_step = 0, cnt = 1;
	
	for (auto &e : edge) {
		conn[e[0] - 1][e[1] - 1] = true;
		conn[e[1] - 1][e[0] - 1] = true;
	}
	
	q.push(PACK(0, 0));
	visited.insert(0);
	
	while (!q.empty()) {
		i64 pack = q.front();
		int step = UNPACK_STEP(pack);
		int idx = UNPACK_IDX(pack);
		q.pop();
 
		if (step != cur_step) {
			cnt = 1;
			cur_step = step;
		} else {
			cnt++;
		}
 
		for (int i = 0; i < n; i++) {
			// If connected
			if (conn[idx][i]) {
				// If not visited
				if (visited.find(i) == visited.end()) {
					q.push(PACK(step + 1, i));
					visited.insert(i);
				}
			}
		}
	}
	
	return cnt;
}

• Graph 문제를 너무 오랜만에 풀어서, conn 을 그냥 $n\times n$ matrix 로 만들었다.
• 통과되긴 하는데, 위 코드랑 비교하면 메모리 사용량이 많고 속도도 좀 느려진다.