[BOJ] DFS 1206번 2606번 2667번 1012번

1260번

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

1260번: DFS와 BFS

//
//  main.cpp
//  BOJ1260
//
//  Created by JSChang on 2020/02/09.
//  Copyright © 2020 JSChang. All rights reserved.
//

#include <bits/stdc++.h>
#define MAX 1000

using namespace std;

int adjacent[MAX+2][MAX+2] = {0};
int visited[MAX+2] = {0};
int n, m, v;

void dfs(int v) {
	cout << v << " ";
	visited[v] = 1;
	for (int i=1; i<=n; i++) {
		if(adjacent[v][i] && !visited[i]) dfs(i);
	}
}

void bfs(int v) {
	queue<int> q;
	q.push(v);
	visited[v] = 0;
	while (!q.empty()) {
		int v  = q.front();
		q.pop();
		cout << v << " ";
		for (int i=1; i<=n; i++) {
			if(adjacent[v][i] && visited[i]) {
				q.push(i);
				visited[i] = 0;
			}
		}
	}
	cout << "\n";
}

int main(int argc, const char * argv[]) {
	cin >> n >> m >> v;
	for (int i=0; i<m; i++) {
		int x, y; cin >> x >> y;
		adjacent[x][y] = 1;
		adjacent[y][x] = 1;
	}
	dfs(v);
	cout << "\n";
	bfs(v);
	return 0;
}

---

2606번

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

2606번: 바이러스

//
//  main.cpp
//  BOJ2606
//
//  Created by JSChang on 2020/02/09.
//  Copyright © 2020 JSChang. All rights reserved.
//

#include <bits/stdc++.h>
#define MAX 100

using namespace std;

int n, m;
int adjacent[MAX+2][MAX+2] = {0};
int visited[MAX+2] = {0};

int dfs(int v) {
	int cnt = 1;
	visited[v] = 1;
	for (int i=1; i<=n; i++) {
		if(adjacent[v][i] && !visited[i]) cnt += dfs(i);
	}
	return cnt;
}

int main(int argc, const char * argv[]) {
	cin >> n >> m;
	for (int i=0; i<m; i++) {
		int x, y; cin >> x >> y;
		adjacent[x][y] = 1;
		adjacent[y][x] = 1;
	}
	cout << dfs(1)-1 << endl;
	return 0;
}

---

2667번

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

2667번: 단지번호붙이기

//
//  main.cpp
//  BOJ2667
//
//  Created by JSChang on 2020/02/09.
//  Copyright © 2020 JSChang. All rights reserved.
//

#include <bits/stdc++.h>
#define MAX 26
#define endl '\n'

using namespace std;

int n;
int adjacent[MAX+1][MAX+1] = {0};
vector<int> group;

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

int main(int argc, const char * argv[]) {
	cin >> n;
	for (int i=0; i<n; i++) {
		string s; cin >> s;
		for(int j=0; j<n; j++) adjacent[i+1][j+1] = (s[j]=='0') ? 0 : 1;
	}
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=n; j++) {
			if(adjacent[i][j]==1) group.push_back(dfs(i, j));
		}
	}
	sort(group.begin(), group.end());
	cout << group.size() << endl;
	for (int x : group) cout << x << endl;
	return 0;
}

---

1012번

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

1012번: 유기농 배추

//
//  main.cpp
//  BOJ1012
//
//  Created by JSChang on 2020/02/09.
//  Copyright © 2020 JSChang. All rights reserved.
//

#include <bits/stdc++.h>
#define MAX 50
#define endl '\n'

using namespace std;

int garo, sero, num;
int adjacent[MAX+1][MAX+1] = {0};

void dfs(int y, int x) {
	if(x>garo || y>sero || x<1 || y<1) return;
	adjacent[y][x] = 0;
	if(adjacent[y][x+1]) dfs(y, x+1);
	if(adjacent[y][x-1]) dfs(y, x-1);
	if(adjacent[y+1][x]) dfs(y+1, x);
	if(adjacent[y-1][x]) dfs(y-1, x);
}

int main(int argc, const char * argv[]) {
	int testCase;
	cin >> testCase;
	for (int testIdx=0; testIdx<testCase; testIdx++) {
		cin >> garo >> sero >> num; int cnt = 0;
		memset(adjacent, 0, sizeof(int)*(MAX+1)*(MAX+1));
		for (int i=1; i<=num; i++) {
			int x, y; cin >> x >> y;
			adjacent[y+1][x+1] = 1;
		}
		for (int i=1; i<=garo; i++) {
			for (int j=1; j<=sero; j++) {
				if(adjacent[j][i]) {
					dfs(j, i);
					cnt++;
				}
			}
		}
		cout << cnt << endl;
	}
	return 0;
}