Week5 - DFS | Herring

📝 문제 목록

개인적으로 공부한 내용을 작성한 것으로 틀린 부분이 있을 수 있습니다
틀린 부분이 있다면 지적해주시면 감사하겠습니다🙏

1. 연결 요소의 개수

정점의 개수와 (연결된 두 정점으로 표현된)간선 데이터가 주어지면, 연결 덩어리가 몇개인지를 세는 전형적인 DFS 문제다.
문제에서 나와있듯 무방향 그래프이므로 간선 정보를 받아 저장 시 양쪽 모두 연결해주어야 하고,
그룹 개수를 세는 것이므로 모든 정점에 대하여 DFS를 해 주되 방문 체크를 해 주어 이전에 이미 방문한 정점은 패스하도록 했다.

간선 정보를 저장하는 그래프의 표현 방식은 크게 두 가지가 있는데, 둘은 상반된 특성을 가지므로 경우에 따라 적절한 방식을 선택해야 한다.
(V: 정점 개수, E: 간선 개수)

인접 행렬: O(V^2)
모든 정점에 대하여 DFS()를 호출 => O(V)
한 정점에 연결된 정점들을 순회할 경우 모든 V개의 정점에 대해 연결되었는지 체크 => O(V)
Good: 어떤 간선이 존재하는지에 대한 정보 접근이 빠르다. 즉 두 정점 간 연결 여부를 바로 알 수 있다.(O(1))
Bad: 간선이 적을 때 메모리 효율이 좋지 않고 불필요한 탐색 시간이 많아진다.
인접 리스트: O(V+E)
모든 정점에 대하여 DFS()를 호출 => O(V)
한 정점에 연결된(=리스트에 저장된) 정점만을 순회 => 총 O(E)
Good: 간선이 적을 때 연결된 정점 정보만이 저장되므로 메모리 효율이 좋다.
Bad: 어떤 간선의 존재여부를 알려고 할 때 리스트를 일일이 뒤져야 하므로 비교적 접근이 느리다.(최악의 경우 O(V))

그러므로 간선이 별로 없는 희소 그래프(sparse graph)에서는 메모리와 시간 낭비가 발생하는 인접 행렬보다 인접 리스트가 적합하겠지만
간선이 많은 밀집 그래프(dense graph)의 경우라면 인접 행렬과 인접 리스트가 사용하는 메모리의 양이 비슷해질 것이고, 그렇다면 리스트를 만드는 데 필요한 오버헤드나 간선 탐색 시간을 고려했을 때 오히려 인접 행렬이 나을 것이다.

아래 코드에서는 간선 정보를 인접 행렬 방식으로 저장했지만 bool형 2차원 벡터를 사용했기 때문에 int형 2차원 벡터를 사용한 인접 리스트보다 메모리와 시간이 적게 나왔다. 만약 간선에 가중치가 있거나 해서 인접 리스트와 같은 int형으로 저장한다면 사용 메모리와 시간이 더 크게 나올 것이다.

코드

#include<iostream>
#include<vector>

using namespace std;

bool isVisited[1001] = { false };
int cnt = 0;
vector<vector<bool>> adj;

void dfs(int v) {
	isVisited[i] = true;
	for (int i = 1; i < adj[v].size(); i++) {
		if (adj[v][i] && !isVisited[i]) {
			dfs(i);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	cin >> n >> m;

	adj.assign(n + 1, vector<bool>(n+1, false));

	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		adj[u][v] = true;
		adj[v][u] = true;
	}

	for (int i = 1; i <= n; i++) {
		if (!isVisited[i]) {
			dfs(i);
			cnt++;
		}
	}

	cout << cnt;
}

2. BFS와 DFS

제목이 곧 내용…정점 개수 N, 간선 개수 M, 시작 정점 V와 간선 정보가 주어지면 DFS와 BFS를 사용해 탐색 순서를 출력하는 문제이다.

코드

#include<iostream>
#include<queue>

using namespace std;

bool isVisited[1001]{ false };
bool isConnected[1001][1001]{ false };
int n;

void dfs(int v) {
	cout << v << " ";
	isVisited[v] = true;

	for (int i = 1; i <= n; i++) {
		if (isConnected[v][i] && !isVisited[i]) {
			dfs(i);
		}
	}
}

void bfs(int v) {
	queue<int> q;
	isVisited[v] = true;
	q.push(v);

	while (!q.empty()) {
		int cur = q.front();
		cout << cur << " ";
		q.pop();
		for (int i = 1; i <= n; i++) {
			if (isConnected[cur][i] && !isVisited[i]) {
				isVisited[i] = true;
				q.push(i);
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int m, v;
	cin >> n >> m >> v;

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		isConnected[a][b] = true;
		isConnected[b][a] = true;
	}

	dfs(v);
	
	cout << "\n";
	fill_n(isVisited, n+1, false);

	bfs(v);
}

3. 욕심쟁이 판다

가장 깊은 탐색 경로를 찾는 문제이다. 한 지역에서 다른 지역으로 이동 시 현재 위치의 상/하/좌/우 중 한 곳으로 이동하며, 이동가능 조건은 다음과 같다.

① 주어진 맵(n×n) 내
② 현재 지역의 값보다 큰 곳

이렇게 더 이상 이동할 수 없을 때까지 이동했을 때 어느 칸에서 시작해야 가장 많은 칸을 방문할 수 있는지를 찾아 최대 이동 칸 수를 출력해야 한다. 다만 주의해야 할 점이 있다.
처음에 제출한 코드에서 시간초과가 발생했는데, 불필요한 반복 연산을 했기 때문이다.
어차피 어떤 칸에 대한 최대 이동 횟수는 정해져 있으므로 한번 DFS를 수행해서 그 칸에 대한 최대 이동 횟수를 구했다면 이후 재방문 시 DFS를 또 할 필요가 없다.
(현재 경로에서는 재방문할 일이 없지만 다른 경로에서 재방문할 수 있다.)
즉 DP를 사용해서 값을 저장(메모이제이션)해놓고, 다음에 다시 방문할 때 저장해놓은 값만을 반환하면 된다.
따라서 이런식으로 어떤 칸에서 상하좌우를 탐색하여 이동 가능한 칸 중 가장 큰 값에 1을 더한 값이 현재 칸의 최대 이동 칸 수가 된다.
DP를 사용했을 때 전체 시간복잡도는 O(n^2)이 된다.

코드

#include<iostream>
#include<queue>

using namespace std;

int n;
int map[501][501];
int cnt[501][501]{ 0 };
int dir[4][2]{ {-1,0},{1,0},{0,-1},{0,1} };

int dfs(int x, int y) {
	if (cnt[x][y] == 0) {
		for (int i = 0; i < 4; i++) {
			int next_x = x + dir[i][0];
			int next_y = y + dir[i][1];
			if (next_x > 0 && next_x <= n && next_y > 0 && next_y <= n &&
				map[x][y] < map[next_x][next_y]) {
				int tmp = dfs(next_x, next_y) + 1;
				if (cnt[x][y] < tmp) cnt[x][y] = tmp;
			}
		}
	}
	return cnt[x][y];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int max = 0;

	cin >> n;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int tmp = dfs(i, j);
			if (max < tmp) max = tmp;
		}
	}

	cout << max+1;
}

Week5 - DFS

📝 문제 목록

1. 연결 요소의 개수

코드

2. BFS와 DFS

코드

3. 욕심쟁이 판다

코드

Further Reading

Week12 - 스터디 문제집(1)

Week13 - 스터디 문제집(2) (끝)

Week8 - Bellman Ford

Trending Tags