'알고리즘/DFS'에 해당되는 글 6건

2667 단지번호붙이기

문제 해석

가로 세로 크기가 5에서 25사이의 정사작형 배열에서 1이 뭉쳐져있는 구역을 구하고, 각 구역에서 1이 몇개나 있는지 오름차순으로 출력하라는 문제입니다.

1이 상하좌우에 있다면 그것은 같은 그룹에 속합니다. 아래 사진을 보세요.

<그림 1>에서 1의 그룹은 새 개의 구역으로 <그림 2>로 표현될 수 있습니다. 1번 그룹, 2번 그룹, 3번 그룹이 있고, 각각의 그룹은 7, 8, 9개의 1이 뭉쳐져있는 것이죠. 

입력은 가로, 세로의 길이가 주어지고, 위의 그림처럼 띄어지지 않은 문자열형태로 넘어옵니다. 이렇게 말이죠.

출력은 그룹의 갯수와 각 그룹이 포함하고 있는 1의 개수를 오름차순으로 출력합니다. 

풀이

DFS(Depth First Search)를 이용하면 쉽게 풀 수 있습니다. 우선 입력이 불친절하게 들어오니까 이를 정수형 배열로 바꾸어줍니다. 제가 문자 배열은 왠만하면 사용하기 싫거든요.

scanf("%d", &n);
for (int i = 0; i < n; i++) {
	char line[MAX_N];
	scanf("%s", line);
	for (int j = 0; j < n; j++) 
		map[i][j] = line[j] - '0';
}

배열의 길이 n을 입력받은 후에 for루프를 n번 돌면서 문자 배열 line으로 배열의 한줄을 입력받습니다. 그 for문의 내부 for문에서는 map배열에 실제 입력을 시킵니다. 그래서 map에는 입력들을 정수형 배열로 입력됩니다.

int cnt = 0;
for (int i = 0; i < n; i++) 
	for (int j = 0; j < n; j++) 
		if (map[i][j] == 1) {
			groups[cnt]=dfs(i, j);
			cnt = cnt + 1;
		}

입력을 받았으면 map을 전부 이중for문으로 돌며 1이 있는 부분에서 멈춥니다. 1이 있는 부분에서 멈추게 되면 그 지점에서 dfs를 호출하는 것이죠. dfs가 몇번 호출이 되느냐에 따라서 cnt가 커지게 됩니다. 바로 cnt가 그룹의 전체 갯수를 나타냅니다.

groups에는 cnt라는 그룹에 몇개의 1이 포함이 되어있는지 저장됩니다.

dfs에서 무슨 동작을 할까요? 이 문제를 풀기위한 핵심인 dfs를 보도록합시다.

int dfs(int y, int x) {
	if (y < 0 || x < 0 || y >= n || x >= n || map[y][x] == 0) return 0;
	map[y][x] = 0;
	return 1 + dfs(y + 1, x) + dfs(y - 1, x)
		+dfs(y, x + 1) + dfs(y, x - 1);
}

dfs함수는 바로 위와 같이 정의되어 있습니다. y는 행, x는 열만을 인자로 받아들이고 있습니다. y나 x가 배열 범위 밖에 있다면 더이상 dfs를 호출하지 않습니다. 또는 map[y][x]가 0인 부분도 기저사례에 포함이 됩니다. 지금까지 말했던 것들이 첫번째 if문의 조건이 되겠네요.

배열 범위에 포함이 되어있으며 map[y][x]=1이라면 바로 그 지점을 0으로 바꿔줍니다. 왜 바꿔주냐면 더 이상 이 점을 방문할 필요가 없으니까요. 만약 map[y][x]=0이 없다면 이 프로그램은 영원히 끝나지 않을겁니다.

그 후에는 상(y-1)하(y+1)좌(x-1)우(x+1)에 dfs를 호출합니다. return에 1을 더해야만 최종 dfs에는 그룹의 1의 개수가 return됩니다.

printf("%d\n", cnt);
sort(groups, groups + cnt);
for (int i = 0; i < cnt; i++) 
	printf("%d\n",groups[i]);

이제 답은 전부 구했네요. cnt를 출력하고 오름차순으로 1의 개수를 출력하라 하였으니 정렬 후에 groups를 출력하면 됩니다.

아래는 전체코드입니다.

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

#define MAX_N 26

int n;
int map[MAX_N][MAX_N];
int groups[MAX_N*MAX_N];
int dfs(int y, int x) {
	if (y < 0 || x < 0 || y >= n || x >= n || map[y][x] == 0) return 0;
	map[y][x] = 0;
	return 1 + dfs(y + 1, x) + dfs(y - 1, x)
		+dfs(y, x + 1) + dfs(y, x - 1);
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		char line[MAX_N];
		scanf("%s", line);
		for (int j = 0; j < n; j++) 
			map[i][j] = line[j] - '0';
	}

	int cnt = 0;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) 
			if (map[i][j] == 1) {
				groups[cnt]=dfs(i, j);
				cnt = cnt + 1;
			}
		
	
	printf("%d\n", cnt);
	sort(groups, groups + cnt);
	for (int i = 0; i < cnt; i++) 
		printf("%d\n",groups[i]);
	
	return 0;
}

dfs만 알면 그리 어렵지 않게 풀수 있는 문제였습니다.

BOJ [1260] DFS와 BFS

문제해석

그래프를 DFS와 BFS 순으로 탐색한 결과를 반환하면 되겠습니다.

제약조건

간선 M은 10000개 이하, 정점 N은 1000 이하입니다.

그냥 묻지도 따지지도 않고 DFS, BFS 오지게 코딩하시면 됩니다.

문제풀이

DFS와 BFS에 대한 설명은 아래의 링크를 통해서 확인해주세요.

DFS https://reakwon.tistory.com/4?category=300866

BFS https://reakwon.tistory.com/7?category=300867

코드

#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

vector<int> dfs_order = vector<int>();
vector<int> bfs_order = vector<int>();
vector<bool> visited;
int map[1001][1001];

int V,E;

void dfs(int here) {
	
	visited[here] = true;
	dfs_order.push_back(here);

	for (int to = 1; to<=V; to++) 
		if (!visited[to] && map[here][to] == 1) 
			dfs(to);
}

void bfs(int start) {

	queue<int> q;
	q.push(start);
	bfs_order.push_back(start);
	visited[start] = true;

	while (!q.empty()) {
		int here = q.front();
		q.pop();
		for (int next = 1; next<=V; next++) 
			if (!visited[next] && map[here][next] == 1) {
				q.push(next);
				bfs_order.push_back(next);
				visited[next] = true;
			}
	}
}

void print_order(vector<int> &order) {
	for (int i = 0; i < order.size(); i++)
		printf("%d ", order[i]);
	printf("\n");
}


int main() {
	
	scanf("%d %d", &V, &E);

	int start;
	scanf("%d", &start);
	for (int i = 0; i<E; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		map[a][b] = map[b][a] = 1;
	}

	visited = vector<bool>(V + 1);
	dfs(start);
	visited = vector<bool>(V + 1);
	bfs(start);

	print_order(dfs_order);
	print_order(bfs_order);

}

dfs_order와 bfs_order는 각각 dfs 순으로 방문된 순서를 저장하는 벡터, bfs 순으로 방문된 순서를 저장하는 벡터입니다.

1012번 유기농 배추

문제 해석

문제는 여러가지 방법으로 풀 수 있습니다.

문제는 간단히 말해 이렇답니다.

그냥 1이 뭉쳐저 있는 곳을 세는 겁니다. 

단, 1은 상하좌우를 통해서 연결되어 집니다. 대각선으로 1은 서로 다른 지역으로 인식하게 되는 겁니다.

위의 예제에서는 1이 뭉쳐져 있는 곳이 총 5부분입니다. 그래서 답이 5가 되는 것입니다.

이런 문제는 조금 흔한 문제라서 딱 보면 그거네~ 하실 거에요.

제약 조건

테스트케이스 T가 주어지고 N과 M은 1이상 50 이하입니다. 배추가 심어져 있는 점은 Y, X로 주어집니다.

최대 50*50이 주어질 수가 있겠군요. 

풀이

이 유기농배추가 있는 지도를 그래프로 생각을 해보도록 하겠습니다. 탐색 방법은 어떤 방향이든 좋습니다. 하지만 상하좌우 네 방향을 전부 탐색해야합니다. 단, 1인 정점만 탐색합니다.

현재 위치를 y,x라고 치고 상하좌우를 탐색합니다. 위쪽 정점은 현재 정점의 y-1, x 아래 정점은 현재 정점의 y+1,x, 왼쪽 정점은 현재 정점의 y, x-1, 오른쪽 정점은 현재 정점의 y, x+1입니다.

하지만 이미 방문되었다면 그 정점은 탐색하지 않습니다.

따라서 dfs가 몇번 호출되었는가가 이 문제의 답이됩니다. 코드를 통해서 살펴보도록 할까요?

#include <cstdio>
#include <string.h>
#define M 51
#define VISITED 0
using namespace std;

int n, m, k;
int map[M][M];

void dfs(int y, int x) {
	
	if ( y<0 || y >= n || x < 0 || x >= m || map[y][x] == VISITED )
		return;

	map[y][x] = VISITED;
	dfs(y + 1, x);	dfs(y, x + 1);
	dfs(y - 1, x);	dfs(y, x - 1);
}

int main() {
	int T;

	scanf("%d",&T);
	for (int t = 0; t < T; t++) {

		memset(map, 0, sizeof(map));

		scanf("%d %d %d", &m, &n, &k);
		for (int i = 0; i < k; i++) {
			int y, x;
			scanf("%d %d", &y, &x);
			map[x][y] = 1;
		}

		int count = 0;
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < m; x++)
				if (map[y][x] == 1) {
					dfs(y, x);
					count++;
				}
		}
	
		printf("%d\n", count);
	}
}

이중 for문을 돌며 1이 등장하면 그 정점부터 dfs를 실행합니다.  dfs는 그 정점이 0이거나 y, x가 범위 밖이면 바로 return 됩니다.

그렇다면 우리는 그냥 0을 방문되었다고 표현하면 더 간단하게 문제를 풀 수 있지 않을까요?

아래 사진처럼 0,0에서 1을 만났다고 치겠습니다. 그렇다면 그 지점 0,0에서 dfs를 수행하면 앞뒤 양옆을 dfs로 순차적으로 돌아 전부 방문됩니다. 그러면 0으로 값이 변하게 되지요. 이 부분이 두번째 사진의 빨간색으로 된 0으로 표현을 했네요.

dfs가 끝났으니 for문을 계속 수행합니다. 하지만 이미 dfs가 돌아 0으로 값이 변했으므로 skip됩니다.

이런 식으로 dfs를 한번 돌게 되면 하나의 덩어리를 구할 수 있습니다. 이 덩어리의 수를 세는 것이 답입니다.

답은 위 코드의 count로 표현됩니다.

시간 복잡도는 N*M이 됩니다. 

이외에도 BFS를 통해서도 문제의 해답을 구할 수도 있습니다. 

마찬가지로 for문 속에서 일일이 루프를 돌면서 아직 방문되지 않는 점이 있으면 bfs를 돌고 count에 1을 더해 주기만 하면 되거든요.

BFS나 DFS나 둘 중 하나만 알아도 이 문제는 풀 수 있습니다.

또 어떤 방법으로 풀 수 있을까요??

DFS(Depth First Search : 깊이 우선 탐색)

그래프, 어렵습니다. 그래프에 대한 이론은 많은 걸로 알고 있습니다. 그중에서 대표적인 것이 바로 탐색 기법인데요. DFS와 BFS라는 녀석, 이 둘이 가장 대표적입니다. 먼저 DFS(Depth First Search)라고 하는 놈이 있어요. 깊이 우선 탐색이라고 우리는 말하더군요! 이런 거는 역시 그림으로 한 방에 이해를 해버리는 게 좋거든요? 그래서 제가 그림을 하나 준비해왔답니다. 아래와 같은 무향그래프가 있다고 칩시다! 0에서부터 시작해서 모든 정점을 방문하려고 합니다. DFS탐색기법을 사용해서 정점을 방문할때 어떤 순서로 방문하게 될까요?

단, 규칙은 작은 노드순으로 방문한다는 조건으로요

이름답게 그 정점에서 아주 깊숙히 들어갑니다. 들어가서 더 이상 들어 갈 곳 없을 때까지 깊숙히 말입니다. 하지만 이미 방문된 노드라면 그 노드는 다시 방문하지 않습니다. 그럼 이제부터 탐색을 시작해 보겠습니다.

0에서부터 시작해서 노드번호가 작은 순으로 가려면 1을 방문해야겠지요?? 1과 인접한 가장 작은 노드 번호를 갖고 아직 방문하지 않은 노드는 2가 있네요. 2와 인접한 노드 중 가장 작고 방문하지 않은 노드는 4가 있습니다. 4는 더 이상 갈 곳이 없으므로 다시 돌아옵니다.

이제 3을 방문할 차례입니다. 1에 인접한 노드는 2와 3이었는 데 방금 2쪽 노드를 모두 방문했으니까요. 3은 인접한 노드가 1이 있는 데 이미 방문을 했답니다.

1로 다시 돌아와서 그 다음으로 인접한 노드를 찾아봅시다. 5가 있네요. 5에서 인접한 노드 중 방문하지 않고 가장 작은 노드는 6이 있습니다. 6은 이제 마지막 노드가 되겠습니다. 왜냐면 0도 방문했고 5도 방문했으니까요.

이것으로 모두 방문을 해보았습니다. 순서는 0 - 1 - 2 - 4 - 3 - 5 - 6 이렇게 되겠네요.

그림을 그려보면 이런 순서랍니다.

그렇다면 다음은 DFS를 코드로 구현해볼까요? 우리는 g라는 2차원 배열 변수로 그래프를 표현하게 됩니다. 바로 위와 같은 그래프입니다. 그리고 한가지 더 말씀드리자면 visited라는 변수를 통해서 그 정점이 방문이 되었는지 기록합니다. 이미 방문이 되면 더 이상 그 정점을 방문하면 안되니까요.

c 소스코드는 바로 아래와 같답니다.

#include <stdio.h>

#define N 7

int g[N][N]=
{
	{0,1,0,0,0,1,1},
	{1,0,1,1,0,0,0},
	{0,1,0,0,1,0,0}, 
	{0,1,0,0,0,0,0},
	{0,0,1,0,0,0,0},
	{1,0,0,0,0,0,1},
	{1,0,0,0,0,1,0}
};
int visited[N];
void dfs(int here) {

	//지금 here이 이미 방문된 정점이라면 다시 빠꾸
	if (visited[here]) return;

	printf("정점 %d를 방문\n", here);

	visited[here] = 1;	//지금 here 정점은 방문

	for (int next = 0; next < N; next++) 
		//그래프가 이어져있으면서, 아직 다음 정점이 방문되지 않았으면 ㄱㄱ
		if (g[here][next] == 1 && !visited[next]) dfs(next);
}
int main() {
	dfs(0);
}

결과는 이렇습니다.

네, 뭐 간단합니다. 재귀함수로 dfs를 쉽게 구현해볼 수 있습니다. 그렇다면 dfs를 도대체 어디에 활용할 수 있을까요? 배웠으면 써먹어야 될꺼 아니겠어요? 그런 다음 포스팅에 알아보도록 하겠습니다.