기록을

큐를 활용한 BFS 풀이가 궁금하다면 아래 글을 참고하기 바란다.

 https://hugssy.tistory.com/56?category=843457

평소 무의식적으로 bfs로만 풀이를 진행한 것 같아서, 이렇게 가끔 bfs로 풀이했던 문제들을 DFS로 풀이해보려고 한다.

확실히 코드가 간결해지긴 하는 것 같다. 무리 없이 재귀를 따라갈 수 있다면 쉽게 사용할 수 있을 것 같다.

일단 큐 따위를 사용하지 않기 때문에 pair 자료구조도 사용할 필요 없이 그냥 dfs 함수의 인자로는 row 값과 col 값을 담으면 되겠다.

방문한 적 없는 지점이면서 집이 있는 지점에서 최초로 dfs를 시작한다. 즉 main 함수에서 dfs를 실행시키는 것이, 새로운 단지를 찾았다는 것이 되겠다. 따라서 main 함수에서 dfs를 몇 번 수행하는지를 계산하면 단지의 전체 수를 찾을 수 있겠다.

필자는 이것을 벡터로 처리했다. 벡터를 사용하면 단지의 개수가 총 몇 개 나올 것인지 생각할 필요가 없기 때문에 좀 더 편하고 빠르게 문제를 풀 수 있다.

dfs 함수 내에서는, 범위 조건을 만족하고, 방문할 가치가 있는 곳이라면 이어서 dfs를 수행한다.

이어서 dfs를 실행할 상황이 온다는 것은, 곧 집을 하나 더 찾았다는 것을 의미한다.

이때 처음 dfs를 수행하기 시작한 곳도 집이라는 것을 생각해서 homeCnt를 1로 초기화해줘야 한다.

main 함수에서 한 번의 dfs가 모두 끝났다는 것은 단지 하나를 전부 돌았다는 것이다.

따라서 이 타이밍에 집의 개수를 추가해주고 다시 집의 개수를 초기화해주면 되겠다.

#pragma warning(disable :4996)
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n, m[26][26];
bool vis[26][26];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
int homeCnt = 1;
vector<int> v;
void dfs(int row, int col) {
	vis[row][col] = true;

	for (int i = 0; i < 4; i++) {
		int nr = row + dr[i];
		int nc = col + dc[i];

		if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
		if (vis[nr][nc] || m[nr][nc] == 0) continue;
		
		homeCnt++;
		dfs(nr, nc);
	}
}

int main(void) {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			scanf("%1d", &m[i][j]);
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!vis[i][j] && m[i][j] == 1) {
				dfs(i, j);
				v.push_back(homeCnt);
				homeCnt = 1;
			}
		}
	}
	sort(v.begin(), v.end());

	cout << v.size() << '\n';
	for (int i = 0; i < v.size(); i++)
		cout << v[i] << '\n';
	return 0;
}

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

문제 설명

방문 처리가 되지 않은 지점이면서 집인 경우에 bfs를 수행해준다.

한 번 수행할 때마다 단지를 하나씩 찾게 되므로, bfs 함수가 실행될 때 단지의 수를 증가시킨다.

이어서 각 단지마다 집의 개수를 파악해야 한다.

이는 bfs를 수행하면서 큐에 push 되는 횟수를 저장해주면 된다. 당연하게도 집인 경우에만 다음에 이어서 탐색을 하도록 구현했으니까.

주의할 것은, 시작지점 즉 bfs를 시작하는 지점도 집이라는 사실이다. 따라서 단지 내 집의 개수를 저장하는 변수인 homeCnt를 1로 초기화했다.

그리고 초기에는 단지 전체의 수를 저장할 변수도 있었는데, 벡터를 사용하게 되면 벡터의 크기가 곧 단지의 개수가 될 것이기 때문에 이것으로 대신했다.

문제 링크이다.

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

사이클을 탐색할 수 있으면 해결할 수 있는 문제이다.

팀이 결정되는 조건이 결국 사이클을 이루는 조건이기 때문이다.

사이클을 검사할 때 템플릿처럼 활용할 수 있을 것 같다.

먼저 방문처리 배열을 두 개를 둔다.

vis배열은 0인 경우 아예 방문을 하지 않은 것이고, -1인 경우에는 방문을 했고, 더 이상 방문할 필요가 없다는 것이다.

1인 경우에는 현재 방문 중이라는 의미이다.

Done배열은 사이클을 이루는 성분인지 여부를 저장한다.

만약 학생 x를 한번 방문해서 vis[x]가 1인 상태라고 해보자. 즉 방문하고 있는 중이라는 것인데,

이 상태에서 x를 누군가가 또 방문한다는 것은? 학생 1을 포함하는 사이클이 존재한다는 의미이다.

따라서 x는 사이클이라는 것이 확실하기 때문에 done[x]를 true로 설정해준다.

그리고 cycle 검사를 마치면 (재귀를 탈출하면) 더 이상 방문할 필요가 없다는 의미이기 때문에 vis[x]를 -1로 만들어준다.

결과적으로 cycle검사의 탈출 조건은 이미 방문할 필요가 없는 곳이거나(vis가 -1인 경우)

이미 사이클을 이루고 있는 경우(Done이 1인 경우)인 것이다.

문제 링크는 다음과 같다.

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

수열에 오름차순이라는 조건이 존재하기 때문에 수열을 만들기 전에 입력받은 수들을 오름차순 정렬해준다.

또한 증가수열로 나타내야 하기 때문에 특정 자리의 숫자로는, 이 전 자리의 숫자보다 큰 숫자만 올 수 있다.

즉 길이 3인 수열을 만들어야 하는데, 첫 번째 숫자를 3으로 정해놨다고 하자.

3 _ _

이런 상태인데, 2번째 자리에 올 수 있는 숫자는 3보다 큰 숫자라는 뜻이다.

따라서 arr[k - 1] < num[i] 이 조건을 추가해서 구현해주면 된다.

물론 다음 재귀로 들어가기 전에 전역변수를 둬서 i를 저장해두거나, 재귀 함수의 인자로 몇 번째 index의 숫자를 사용했는지 관리해주는 방법도 있다.

func(1)은 이제 첫번째 자리의 숫자를 정해야 한다는 의미이다.

따라서 base condition은 이제 M+1번째 자리의 숫자를 정할 타이밍 일 것이다. 이때가 M번째 숫자까지 결정되었다는 의미이기 때문이다.

#include<iostream>
#include<algorithm>
using namespace std;
int N, M, num[10], arr[10];
bool isused[10];
void func(int k) {
	if (k == M + 1) {
		for (int i = 1; i <= M; i++)
			cout << arr[i] << ' ';
		cout << '\n';
		return;
	}
	
	for (int i = 1; i <= N; i++) {
		if (!isused[i] && num[i] > arr[k - 1]) {
			arr[k] = num[i];
			isused[i] = true;
			func(k + 1);
			isused[i] = false;
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		cin >> num[i];
	sort(num + 1, num + N + 1);
	
	func(1);
	return 0;
}

문제 링크

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

사용할 수 있는 수들을 입력으로 받는다.

수열들을 오름차순으로 뽑아내야 한다.

사용되는 숫자들을 사전에 오름차순으로 정렬해두면 된다.

재귀함수의 인자는 숫자의 번호라고 생각하면 되겠다. 즉 k가 1인경우는, 첫번째 숫자를 결정할 차례라는 뜻이다.

길이를 M으로 입력받기 때문에, k가 M+1이 되면 M+1번째 숫자를 결정할 차례라는 의미이므로 이미 M번째 까지는 결정이 되었다는 의미이다.

따라서 k == M+1인 경우를 base condition으로 설정해주면 된다.

또한 재귀를 빠져나온 이후에는, 숫자를 사용중이 아닌 것이 되기때문에, isused값을 다시 false로 바꿔줘야한다.

만약 k를 전역변수로 두고 코딩을 한다면 k또한 재귀를 들어가기전에는 증가, 재귀에서 빠져 나온 이후에는 감소를 해줘야 할 것이다.

#include<iostream>
#include<algorithm>
using namespace std;
int N, M;
int arr[10], num[10];
bool isused[10];

void func(int k) {
	if (k == M + 1) {
		for (int i = 1; i <= M; i++)
			cout << arr[i] << ' ';
		cout << '\n';
		return;
	}
	
	for (int i = 1; i <= N; i++) {
		if (!isused[i]) {
			arr[k] = num[i];
			isused[i] = true;
			func(k + 1);
			isused[i] = false;
		}
	}

}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> num[i];
	}
	sort(num + 1, num + N + 1);

	func(1);

	return 0;
}

문제 링크는 다음과 같다.

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

문제 요약

- 내 위치에서 친구의 위치까지 수직선 위에서 움직이면 된다.

- 움직이는 방법은, 내 위치가 X였다면 1초 이후에 X-1, X+1, 그리고 2*X 이렇게 가능하다.

- 이때 한 번 움직일 때 1초씩 흐른다.

- 나의 위치 X에서 친구의 위치까지 이동하는 데에는 몇 초가 걸릴까?

위의 상황을 착실하게 구현해주면 된다.

먼저 이 문제는 기계적으로 배열 크기를 잡는 모든 이들을 위한 문제라고 할 수 있다.

(물론 거기에는 나도 포함되었다)

이 문제의 구현 수준은, 절대 24%대의 정답률이 나올만한 것이 아니다.

다만 대부분의 사람들이 배열의 크기를 잡을 때 n값의 범위만을 고려했기 때문에 '맞왜틀'을 반복했을 것이다.

나 또한 초반에는 그렇게 생각했다.

1차적으로 이것을 파악할 수 있는 부분은 문제의 힌트에 있다.

5에서 17을 가는 길에 18을 거친다. 이것을 보고 내가 만약에 10,0000을 목적지로 잡았다고 하면, 이 위치보다 큰 값을 거쳐서 저 위치로 다다를 가능성도 없지 않다는 것이다.

필자의 경우에는, 이 힌트를 보고도 이것을 파악하지 못했고, 몇 가지의 예시를 가지고 print를 찍어보는 방식으로 디버깅을 하던 도중에 깨달았다.

또, 여러가지의 예시를 넣어보는 과정을 거친 이후에도 해결되지 않는 문제들은 대부분이 극값 혹은 그 근처에서 발생하는 문제였다. 이번 경우에도 그렇다고 볼 수 있다.

정확한 배열 크기는 알아내지 못하였고. 그저 배열의 크기를 넉넉하게 잡아주는 방법으로 해결했다.

#include<iostream>
#include<queue>
using namespace std;
int n, k;
int vis[300000];
queue<int> q;
int sec = 0;
void bfs(int start) {
	q.push(start);
	vis[start]++;

	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int i = 0; i < 3; i++) {
			int np;
			if (i == 0)
				np = cur - 1;
			else if (i == 1)
				np = cur + 1;
			else
				np = 2 * cur;

			if (np < 0 || np > 100000 || vis[np] >= 0) continue;

			q.push(np);
			vis[np] = vis[cur] + 1;
			if (np == k) return;
		}
	}
}
int main(void) {
	cin >> n >> k;
	for (int i = 0; i < 300000; i++)
		vis[i] = -1;
	bfs(n);
	cout << '\n';
	for (int i = 0; i < 30; i++)
		printf("%d 에서 %d\n", i, vis[i]);
	cout << '\n';
	cout << vis[k] << '\n';
	return 0;
}

문제 링크이다. 

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

두 번째 토마토 문제이다.

첫번째 토마토 문제와 동일하지만 높이 조건이 추가되었다. 차원이 하나 더 추가된 것이다.

다만 2차원 상황일 때는 queue에 pair 자료구조를 넣어서 활용했다.

이번에는 세개라서 간단하게 구조체를 선언해서 활용했다.

또한 점의 움직임을 정의하는 배열도, 동서남북 이외에 위아래가 추가되었기 때문에 크기를 6으로 잡아주고, 높이 움직임을 처리할 배열을 추가해주었다.

마찬가지로 update가 되지 않은 경우에는 큐가 비어있지 않아도 수행을 마치게 하였다.

여담으로, 삼성 소프트웨어 역량테스트 A형의 경우, 여러개의 테스트 케이스를 처리해야 하기때문에 초기화가 중요하다.

이 상황을 가정하고 코드를 정리하던 도중, 큐가 비어있지 않은 상태로 다음 테스트 케이스에서 이용할 수 있는 여지가 있다는 것을 생각해냈다.

따라서 초기화를 해줄 때에는, 단순히 전역변수로 사용한 여러가지 변수들과 더불어서, 큐 또한 비워주는 방식의 초기화를 해줘야 할 것이다.

아래 코드는 한 개의 테스트 케이스만 처리하면 될 때의 코드이다.

#include<iostream>
#include<queue>
using namespace std;
int col, row, H, m[100][100][100];
bool vis[100][100][100];
struct pt {
	int h;
	int row;
	int col;
};
queue<pt> q;
int dh[6] = { 0,0,0,0,1,-1 };
int dr[6] = { 0,0,1,-1,0,0 };
int dc[6] = { 1,-1,0,0,0,0 };
int Day = 0;
bool updated = false;

void bfs() {
	while (!q.empty()) {
		int cnt = q.size();
		updated = false;
		while (cnt--) {
			pt cur = q.front();
			q.pop();
			for (int i = 0; i < 6; i++) {
				int nh = cur.h + dh[i];
				int nr = cur.row + dr[i];
				int nc = cur.col + dc[i];
				
				if (nh < 0 || nr < 0 || nc < 0 || nh >= H || nr >= row || nc >= col) continue; //범위 밖이면 pass
				if (m[nh][nr][nc] != 0 || vis[nh][nr][nc]) continue; //토마토가 익지 않은 자리가 아니거나 이미 방문한 지점이면 pass
				
				m[nh][nr][nc] = 1;
				q.push({ nh, nr, nc });
				vis[nh][nr][nc] = true;
				updated = true;
			}
		}
		if (!updated) break; //하루 지났는데 변화가 없었으면 break;
		Day++;
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
		cin >> col >> row >> H;

		for (int h = 0; h < H; h++) {
			for (int i = 0; i < row; i++) {
				for (int j = 0; j < col; j++) {
					cin >> m[h][i][j];
					if (m[h][i][j] == 1) {
						q.push({ h, i, j });
						vis[h][i][j] = true;
					}
				}
			}
		}
		bfs();
		for (int h = 0; h < H; h++) {
			for (int i = 0; i < row; i++) {
				for (int j = 0; j < col; j++) {
					if (m[h][i][j] == 0) {
						cout << -1 << '\n';
						return 0;
					}
				}
			}
		}
		cout << Day << '\n';
	return 0;
}

문제 링크이다.

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

첫 번째 토마토 문제이다.

토마토가 몇 번째 날에 어떤 토마토들이 익는 것인지 파악하는 게 중요하다.

여러 가지 방법이 있겠지만, 우선 직관적으로 입력을 받으면서 처음부터 익어있는 토마토들을 큐에 담았다.

당연하게 초기부터 익어있는 토마토들로부터 확산이 시작될 것이기 때문이다.

따라서 입력이 1인 지점들을 큐에 미리 넣어둔다.

이후에는 bfs를 수행해주면 되는데 일반적인 bfs 템플릿과 차이가 있는 점은 날짜를 카운트해야 한다는 것이다.

이를 위해서는 탐색을 시작할 때, 큐에 몇개가 있는지 생각해서 그 수만큼만 탐색을 탐색을 진행해야 한다.

이해를 쉽게 하기 위해 시작할 때를 생각해보자.

가령 2 * 2로 상자의 크기가 들어오고,

0 0

1 1

위와 같이 입력이 들어왔다고 가정해보자. 그렇다면 첫 번째 날에는 4방향 확산이 두 번만 일어나야 한다. 1이 두 개이기 때문이다. 즉 확산의 중심이 되는 지점인 1이 두 개이기 때문에 첫 번째 날에는 딱 직전의 1의 개수만큼 실행해줘야 한다.

따라서 탐색 직전에 cnt라는 변수를 두어서 그때의 큐의 크기를 잡아두고, 최대 이 크기만큼만 탐색을 수행하도록 했다.

그리고 당연하게도, 더 이상 탐색을 할 필요가 없을 때는 탐색을 하지 않도록 해줘야 한다.

따라서 토마토의 익은 상태의 변화가 있는지 없는지 확인을 해주는 isChanged라는 변수를 활용했다.

변화가 없으면 탐색을 그만두도록 했다. 그래야 Day count를 정확하게 할 수 있다.

시작부터 모두 익어있는 경우는 Day가 0일 것이므로 특별한 처리를 해주지 않았다.

안 익은 토마토가 있는지는 마지막에 0이 있는지 확인하는 loop로 처리를 해주었다.

#include<iostream>
#include<queue>
using namespace std;
int col, row, m[1000][1000];
queue<pair<int, int> > q;
bool vis[1000][1000];
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };
int Day = 0;
bool isChanged = false;
void bfs() {
	
	while (!q.empty()) {
		int cnt = q.size();
		isChanged = false;
		while (cnt--) {
			pair<int, int> cur = q.front();
			q.pop();
			
			for (int i = 0; i < 4; i++) {
				int nr = cur.first + dr[i];
				int nc = cur.second + dc[i];
				if (nr < 0 || nc < 0 || nr >= row || nc >= col) continue;
				if (m[nr][nc] == -1 || vis[nr][nc] == true || m[nr][nc] == 1) continue;

				m[nr][nc] = 1;
				q.push({ nr, nc });
				vis[nr][nc] = true;
				isChanged = true;
			}
		}
		if (!isChanged) break;
		Day++;
		
	}
	
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> col >> row;
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			cin >> m[i][j];
			if (m[i][j] == 1) {
				q.push({ i, j });
				vis[i][j] = true;
			}
		}
	}
	bfs();
	
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			if (m[i][j] == 0) {
				cout << -1 << '\n';
				return 0;
			}
		}
	}
	
	cout << Day <<'\n';
	return 0;
}

문제 링크

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

중복을 허용하면서 감소하지 않는 수열로 만들어야 한다.

따라서 재귀를 이전 자리에 쓰인 숫자부터 진행하면 된다. 

첫번째 자리의 숫자를 정할 때, 이전에 쓰인 숫자가 없기 때문에, 이 경우에만 st를 1로 정해주면 된다.

#include<iostream>
using namespace std;
int N, M;
int arr[9];
void func(int k) {
	if (k > M) {
		for (int i = 1; i <= M; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}
	int st = 1;
	if (k != 1) st = arr[k - 1];
	for (int i = st ; i <= N; i++) {
		
		arr[k] = i;
		func(k + 1);
	}
}
int main(void) {
	cin >> N >> M;
	func(1);
	return 0;
}

문제는 아래와 같다.

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

이번에는 숫자를 중복해서 사용할 수 있다.

이전까지는 숫자의 중복을 제한하기 위해서 isused배열을 사용했다. 숫자가 arr배열을 이루는 데에 사용되고 있다면 true 값을 가지도록 하고 그렇지 않은 경우 false 값을 가지도록 하였다.

이번에는 이것이 필요하지 않다.

또한 문제를 풀이하는 과정에 있어서, 배열을 인자로 넘기지 않고 전역변수로 사용해도 좋다.

k값도 마찬가지이다. k값을 인자로 넘기지 않으려면, 재귀에 들어가기 전에 k값을 증가시키고,

재귀에서 탈출한 이후에는 k값을 줄여줘야한다.

또한 k를 0부터 시작할지 1부터 시작할지도 편한 데로 선택하면 되겠다.

나 같은 경우에는 k를 0부터 시작하는 경우, ~까지는 수열이 만들어져 있다는 의미로 보았다.

1부터 시작하는 경우에는, 이번에는 ~번째 자리의 숫자를 채울 차례다라는 의미로 생각하면 되겠다.

당연하게도 의미가 다르기 때문에 base condition의 조건도 달라져야 한다.

전자의 경우 k==m인 경우가 기저 조건이고, 후자의 경우 k > m 인 경우를 기저 조건이라고 보면 된다.

//전역변수 활용
#include<iostream>
using namespace std;
int arr[8], N, M; //1 indexed
//int k = 0;
void func(int k) {
	if (k > M) {
		for (int i = 1; i <= M; i++)
			cout << arr[i] << ' ';
		cout << '\n';
		return;
	}

	for (int i = 1; i <= N; i++) {
		arr[k] = i;
		func(k + 1);
	}
}
int main(void) {
	cin >> N >> M;
	func(1); 
	return 0;
}