BFS&DFS 문제 코드 - 4963, 1012, 16236번

문제에 대한 해설은 그래프 기초 강의에 있습니다!

 

백준 4963번 - 섬의 개수

www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

코드

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;
int w, h;
int check[60][60];
int map[60][60];
queue < pair<int, int>> q;
int dr[8] = { -1,-1,-1,1,1,1,0,0 };
int dc[8] = { -1,0,1,-1,0,1,-1,1 };
int cnt = 0;
void bfs(int r, int c) {
	q.push(make_pair(r, c));
	check[r][c] = 1;
	while (!q.empty()) {
		r = q.front().first;
		c = q.front().second;
		q.pop();
		for (int k = 0; k < 8; k++) {
			int nr = r + dr[k];
			int nc = c + dc[k];
			if (0 <= nr && nr < h && 0 <= nc && nc < w) {
				if (check[nr][nc] == 0 && map[nr][nc] == 1) {
					q.push(make_pair(nr, nc));
					check[nr][nc] = 1;
				}
			}
		}
	}
}

int main(void) {
	while (1) {
		scanf("%d %d", &w, &h);
		if (w == 0 && h == 0) break;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				scanf("%d", &map[i][j]);
			}
		}
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (map[i][j] == 1 && check[i][j] == 0) {
					bfs(i, j);
					cnt += 1;
				}
			}
		}
		printf("%d\n", cnt);
		cnt = 0;
		memset(check, 0, sizeof(check));
		memset(map, 0, sizeof(map));
	}
}

 

백준 1012번 - 유기농 배추

www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

코드

#include <iostream>
#include <cstring>
#include <queue>
#pragma warning(disable:4996)
using namespace std;
int bat[51][51];
queue <pair<int,int>>q;
int cnt = 0;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int n, m;
int check[51][51];

void bfs(int p, int s) {
	q.push(make_pair(p, s));
	check[p][s] = 1;
	while (!q.empty()) {
		p = q.front().first;
		s = q.front().second;
		q.pop();
		for (int kk = 0; kk < 4; kk++) {
			int np = p + dx[kk];
			int ns = s + dy[kk];
			if (0 <= np && np < n && 0 <= ns && ns < m) {
				if (check[np][ns] == 0 && bat[np][ns]==1) {
					q.push(make_pair(np, ns));
					check[np][ns] = 1;
				}
			}
		}
	}
}

int main(void) {
	int t, k;
	scanf("%d", &t);
	while (t--) {
		scanf("%d %d %d", &n, &m, &k);
		while (k--) {
			int x, y;
			scanf("%d %d", &x, &y);
			bat[x][y] = 1;
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (check[i][j] == 0 && bat[i][j] == 1) {
					bfs(i, j);
					cnt += 1;
				}
			}
		}
		printf("%d\n", cnt);
		cnt = 0;
		memset(check, 0, sizeof(check));
		memset(bat, 0, sizeof(bat));
	}
}

 

백준 16236번 - 아기 상어

www.acmicpc.net/problem/16236

16236번: 아기 상어

 

코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <tuple>
#include <cstring>
#pragma warning(disable:4996)
using namespace std;

int n, x, y;
int baby = 2;
int cnt = 0;
int map[21][21];
int dx[4] = { -1,0,0,1 }; //북,서,동,남
int dy[4] = { 0,-1,1,0 };
bool check[21][21] = { false };
int dis[21][21];
vector<tuple<int,int, int>>v;

int count(int a, int b) {
	int ans = 0;
	while (1) {
		memset(check, false, sizeof(check));
		memset(dis, 0, sizeof(dis));
		v.clear();
		queue<pair< int, int >> q;
		q.push(make_pair(a, b));
		check[a][b] = true;
		dis[a][b] = 0;
		int c = 0;
		while (!q.empty()) {
			a = q.front().first;
			b = q.front().second;
			q.pop();
			for (int i = 0; i < 4; i++) {
				int nx = a + dx[i];
				int ny = b + dy[i];
				if (0 <= nx && nx < n && 0 <= ny && ny < n) {
					if (check[nx][ny] == false && baby >= map[nx][ny]) {
						q.push(make_pair(nx, ny));
						check[nx][ny] = true;
						dis[nx][ny] = dis[a][b] + 1;
						if (baby > map[nx][ny] && map[nx][ny] != 0) v.push_back(make_tuple(dis[nx][ny], nx, ny));
					}
				}
			}
		}
		if (!v.empty()) {
			sort(v.begin(), v.end());
			//이동(몇초걸리는지 계산)
			tie(c, a, b) = v.front();
			map[a][b] = 0;
			cnt++;
			if (cnt == baby) {
				cnt = 0;
				baby++;
			}
			ans += dis[a][b];
		}
		else break;
	}
	return ans;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 9) {
				x = i;
				y = j; //아기상어의 위치
				map[i][j] = 0;
			}
		}
	}
	printf("%d\n", count(x, y));
}