[구름 알고리즘 먼데이 챌린지] Week3 : 3. 구름이의 여행

 

1.DFS

문제를 읽고 바로 DFS로 해결할 수 있을 거라 판단하여 바로 구현을 시작했다.

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

int n, m, k, u, v, visited[1001], flag;
vector<int> bridge[1001];

void dfs(int cur, int move) {
	if (move > k) return;
	if (visited[cur]) return;
	visited[cur] = 1;
	if (cur == n) { flag = 1; return; }
	for (auto& n : bridge[cur]) {
		if (flag) return;
		dfs(n, move + 1);
		visited[n] = 0;
	}
	return;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		bridge[u].push_back(v);
		bridge[v].push_back(u);
	}
	dfs(1, 0);
	if (flag) cout << "YES";
	else cout << "NO";
	return 0;
}

한번 방문한 섬을 다시 돌아 오는 것은 k개 이하의 다리를 사용해야만 하는 조건에서 불필요한 이동이기 때문에 visited 배열을 통해 방지해 주었다. 이동 횟수 move를 통해 종료 조건을 설정해 주었고 k개 이하의 다리를 사용하여 N번 섬에 도착하지 못한 경우 백트래킹을 통해 다른 경로를 마저 올바르게 탐색할 수 있도록 해주었다.

결과는...

4개의 테스트케이스에서 시간초과가 발생했다.

이후, dfs탐색에서 불필요한 노드 방문을 최소화 하기 위해 로직을 약간 수정해주었다.

 

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

int n, m, k, u, v, visited[1001], flag;
vector<int> bridge[1001];

void dfs(int cur, int move) {
	for (auto& next : bridge[cur]) {
		if (flag) return;
		if (visited[next]) continue;
		if (move + 1 <= k) {
			if (next == n) { flag = 1; return; }
			visited[next] = 1;
			dfs(next, move + 1);
			visited[next] = 0;
		}
	}
	return;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		bridge[u].push_back(v);
		bridge[v].push_back(u);
	}
	visited[1] = 1;
	dfs(1, 0);
	if (flag) cout << "YES";
	else cout << "NO";
	return 0;
}

 

여전히 31번 테케에서는 시간초과가 발생했다...

에초에 N번 섬에 연결된 다리가 존재하지 않은 경우 시간초과가 발생하나 싶어 해당 부분을 추가해 보았지만 마찬가지로 시간초과가 발생했다.

 

2.BFS

DFS와 BFS의 시간복잡도는 O(N)으로 같지만, DFS를 재귀를 사용하여 구현할 경우 스텍 영역에 임시 메모리를 생성하는 등의 과정에서 BFS보다 실제 속도 측면에서 불리한 것을 알고 있었다. 따라서, BFS로 로직을 수정해 보았다.

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

int n, m, k, u, v, visited[1001], flag;
vector<int> bridge[1001];

bool bfs() {
	int cur, next, move;
	visited[1] = 1;
	queue<pair<int, int>> q;
	q.push({ 1, 0 });
	while (!q.empty()) {
		cur = q.front().first;
		move = q.front().second;
		q.pop();
		if (move > k) continue;
		if (cur == n) return true;
		for (int i = 0; i < bridge[cur].size(); i++) {
			next = bridge[cur][i];
			if (visited[next]) continue;
			visited[next] = 1;
			q.push({ next, move + 1 });
		}
	}
	return false;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		bridge[u].push_back(v);
		bridge[v].push_back(u);
	}
	if(bfs()) cout << "YES";
	else cout << "NO";
	return 0;
}

띠로리~ BFS로 수정하니 통과하였다.

 

이 문제 같은 경우 시간 조건이 충분하다면 DFS와 BFS 중 어떤 것을 사용해도 답을 구할 수 있다. 하지만  k개 이하의 다리를 사용해야 한다는 조건에서 최단 경로 문제라고 판단할 수 있고 최단 경로의 경우 BFS를 사용하는 것이 합리적이라는 것을 알 수 있다. 앞으로 문제를 잘 읽고 DFS/BFS 중 어느 것이 효율적인지 잘 판단하고 선택해야겠다고 생각했다.