백준 11724 (DFS를 사용한 풀이) C++

SMALL

꾸준히 알고리즘을 풀어가면서 다이나믹 프로그래밍, 정렬, 이분탐색등을 배워나갔다, 하지만 그래프 탐색 (DFS, BFS)는 아무리 책을 보고 인터넷에 찾아가며 공부를 해봐도 쉽게 이해가 되지 않는 분야였다.

하지만 마침내 알고리즘 방식을 이해했고 이를 바탕으로 풀이한 백준 11724번에 대한 풀이이다.

최대한 기초적인 지식을 통해 설명을 해보려고 한다.

먼저 그래프 이론이 무엇인가? 에 대한 정의 부터 짚고 넘어가려고 한다.

컴퓨터 과학에서 말하는 그래프, 그래프이론의 경우 위에 그림과 같이 노드라는 한 점을 서로 연결시켜 놓은 수학 구조를 뜻한다.

이러한 그래프를 이용한 대표적인 알고리즘으로는 BFS,DFS등이 있다.

두개의 차이점의 경우

BFS (Breadth-First Search) DFS (Depth-First Search)

탐색 방식	시작 노드에서 가까운 노드부터 차례로 탐색 (층별 탐색)	시작 노드에서 한 경로를 끝까지 탐색 후, 다른 경로 탐색
구현 방식	큐(Queue) 사용	스택(Stack) 또는 재귀(Recursion) 사용
방문 순서	거리(간선 수)가 짧은 순으로 탐색	한 방향으로 깊게 들어간 후 되돌아옴
최단 거리 보장	가중치가 동일한 그래프에서 최단 경로 보장	최단 경로 보장 X
메모리 사용량	노드 수가 많을수록 큐에 많은 노드 저장 (메모리 사용량 ↑)	경로의 깊이에 따라 메모리 사용 (보통 BFS보다 적음)
적합한 경우	최단 경로, 레벨별 탐색, 네트워크 전파 문제	경로 존재 여부, 미로 탐색, 백트래킹 문제
예시 상황	“가장 빠른 길 찾기”	“갈 수 있는 모든 경로 찾기”

이와 같다.

https://www.acmicpc.net/problem/11724

이제 본격적으로 백준 문제 풀이를 해보겠다.

	vector<int> v[1001];
	bool visited[1001];

먼저 각 노드간의 연결된 선을 표현하기 위해 v라는 벡터를 생성해냈다.

1--- vector<int> v(n);

2--- vector<int> v[1001];

여기서 벡터를 생성하는 2가지 방식에 대해 궁금증이 생겼는데

찾아보니 1번 방식의 경우 1차원 벡터를 형성할떄

2번 방식의 경우 2차원 벡터를 형성할때 자주 쓰인다고 했다.

필자의 경우 각각의 노드간의 상호연결을 표현해야 하기에 2차원 벡터 즉 2번 방식을 활용하였다.

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

다음으로는 노드간의 연결값을 받아서 이를 벡터에 넣어주는 부분이다.

a->b 로 연결되는 부분

b->a 로 연결되는 부분 총 2개가 있기에 push값을 2번 처리해주었다.

		for (int i = 1; i < n+1; i++)
		{
			while (visited[i] != true)
			{
				cnt++;
				dfs(i);
		}

다음으로는 주어진 노드 1번 부터 n+1번까지 돌면서 모든 노드의 방문값이 true인지를 확인하는 코드이다.

i=0으로 착각하는 실수도 있는데 문제설명에서 노드의 시작값은 >=1 이라고 했으므로 0이 아닌 1부터 시작하여야 한다.

	void dfs(int i)
	{
		if (visited[i])
			return;

		visited[i] = true;

		for (auto k : v[i])
		{
			if (visited[k] != true)
				dfs(k);
		}

	}

다음으로는 가장 중요한 dfs의 구현 부분이다.

총 3가지 부분으로 나누어져 있다고 생각하면 되는데,

1. 이미 지나간 노드의 경우 return으로 함수를 벗어나도록 하기

2. 지나가지 않았을 경우 visited 값을 true로 바꿔 이미 지나간 노드라고 변경시켜주기

3. 주어진 노드와 연결되어있는 모든 노드를 dfs(k) 재귀를 통해서 다시 방문시켜주기 이다.

추가적으로 auto k : v[i] <<<<< 이 코드가 굉장히 맘에 들었는데, v[i]라는 벡터의 모든 항목들을 k에 보내면서

다른 설정없이도 노드와 연결된 모든 값을 점검시킬 수 있다.

아래는 11724 풀이 코드의 전문이다.

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

	vector<int> v[1001];
	bool visited[1001];

	void dfs(int i)
	{
		if (visited[i])
			return;

		visited[i] = true;

		for (auto k : v[i])
		{
			if (visited[k] != true)
				dfs(k);
		}

	}

	int main()
	{
		ios::sync_with_stdio(false);
		cin.tie(NULL);
		cout.tie(NULL);
		int n, m;
		int cnt = 0;
		cin >> n >> m;

		for (int i = 0; i < m; i++)
		{
			int a, b;
			cin >> a >> b;
			v[a].push_back(b);
			v[b].push_back(a);
		}
		
		for (int i = 1; i < n+1; i++)
		{
			while (visited[i] != true)
			{
				cnt++;
				dfs(i);
		}

		}
		cout << cnt;

		return 0;

		
	}

1. 그래프 이론과 DFS

2. DFS 알고리즘의 구현 및 작동 방식

3. auto k : v[i] 를 통한 벡터값의 확인

4. 재귀함수와 return 값 반환을 통한 함수 구현

이 4가지를 이문제를 통해 배워 나갔으면 좋겠다.