[백준/baekjoon] Silver1 2667. 단지번호붙이기

DFS 연습용으로 들어갔는데

예전에 BFS로 풀었던 것이랑 비슷한 문제(👇)여서

https://jolly-note.tistory.com/43

[programmers] Lv.2 카카오프렌즈 컬러링북(c++)

DFS, BFS 두 방법으로 풀어봤다.

 

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<algorithm>

using namespace std;

int cnt = 0;
vector<int> house;
vector<vector<int>> map;

vector<int> dir_x = { 1, -1, 0, 0 };
vector<int> dir_y = { 0, 0, 1, -1 };

void dfs(int i, int j, int idx) {
	if (map[i][j] != -1) return;
	house[idx]++;
	map[i][j] = cnt;

	for (int k = 0; k < 4; k++) {
		if (i + dir_x[k] < 0 || i + dir_x[k] >= map.size() ||
			j + dir_y[k] < 0 || j + dir_y[k] >= map.size()) continue;
		dfs(i + dir_x[k], j + dir_y[k], idx);
	}
}

void bfs(int i, int j, int idx) {
	queue<pair<int, int>> que;
	que.push({ i, j });
	map[i][j] = cnt;

	while (!que.empty()) {
		auto[x, y] = que.front(); que.pop();
		house[idx]++;
		for (int k = 0; k < 4; k++) {
			if (x + dir_x[k] < 0 || x + dir_x[k] >= map.size() ||
				y + dir_y[k] < 0 || y + dir_y[k] >= map.size() ||
				map[x+dir_x[k]][y+dir_y[k]] != -1) continue;
			que.push({ x + dir_x[k], y + dir_y[k] });
			map[x + dir_x[k]][y + dir_y[k]] = cnt;
		}
	}
}

int main() {
	int N;
	cin >> N;
	map = vector<vector<int>>(N, vector<int>(N, 0));

	string num;
	for (int i = 0; i < N; i++) {
		cin >> num;
		for (int j = 0; j < N; j++) {
			if (num[j] == '1') map[i][j] = -1;
		}
	}
	/*
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == -1) {
				cnt++;
				house.push_back(0);
				dfs(i, j, cnt-1);
			}
		}
	}
	*/

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == -1) {
				cnt++;
				house.push_back(0);
				bfs(i, j, cnt-1);
			}
		}
	}
	
	sort(house.begin(), house.end());
	cout << cnt << endl;
	for (int n : house) cout << n << endl;
}

---

문제

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

2667번: 단지번호붙이기

728x90

---

[접근1] - 공통

지도의 크기 N과 N개의 자료를 받아온다.

각 숫자들은 스페이스로 분리되어있지 않아서 직접 분리했다.

visit했는지 여부를 쉽게 파악하기 위해서 1로 표시된것을 -1로 바꿔서 입력하였다.

int N;
cin >> N;
map = vector<vector<int>>(N, vector<int>(N, 0));

string num;
for (int i = 0; i < N; i++) {
    cin >> num;
    for (int j = 0; j < N; j++) {
        if (num[j] == '1') map[i][j] = -1;
    }
}

---

DFS

https://jolly-note.tistory.com/62?category=993245 

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

---

[접근2]

지도를 0, 0부터 돌면서 -1인 구간을 찾는다.

-1이면 단지 수인 cnt를 1 증가시키고 집 개수를 적어둘 house vector에 0을 집어넣어 사용할 준비를 한다.

dfs 함수에 i, j, 집 개수를 적어둘 house vector의 위치를 나타내는 idx를 넣는다.

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if (map[i][j] == -1) {
            cnt++;
            house.push_back(0);
            dfs(i, j, cnt-1);
        }
    }
}

---

[접근3] - dfs 함수 내부

우선 그 위치에 집이 있는지 확인한다. 없으면 함수를 끝낸다.

집의 개수를 1 증가시켜주고 해당 위치의 집에 번호를 부여한다.

4방향을 확인하면서 dfs함수를 불러온다.

if (map[i][j] != -1) return;
house[idx]++;
map[i][j] = cnt;

for (int k = 0; k < 4; k++) {
    if (i + dir_x[k] < 0 || i + dir_x[k] >= map.size() ||
        j + dir_y[k] < 0 || j + dir_y[k] >= map.size()) continue;
    dfs(i + dir_x[k], j + dir_y[k], idx);
}

---

BFS

https://jolly-note.tistory.com/63?category=993245 

BFS (Breadth First Search, 너비 우선 탐색)

---

[접근2]

dfs함수의 접근2와 동일하다. 사용하는 함수만 bfs일 뿐임.

지도를 0, 0부터 돌면서 -1인 구간을 찾는다.

-1이면 단지 수인 cnt를 1 증가시키고 집 개수를 적어둘 house vector에 0을 집어넣어 사용할 준비를 한다.

bfs 함수에 i, j, 집 개수를 적어둘 house vector의 위치를 나타내는 idx를 넣는다.

---

[접근3] - bfs 함수 내부

que에 i, j를 넣고 해당 위치의 map에 번호를 부여한다.

que가 빌때까지 반복하는데,

que의 맨 앞의 원소를 가져오고, 집의 개수를 1 증가시킨다.

4방향을 확인하면서 방문한적 있거나 해당 위치에 집이 없으면 건너 뛰고 방문하지 않은 집이 있으면 que에 집의 위치를 집어넣는다. 또한 해당 위치의 집에 번호를 부여한다.

void bfs(int i, int j, int idx) {
	queue<pair<int, int>> que;
	que.push({ i, j });
	map[i][j] = cnt;

	while (!que.empty()) {
		auto[x, y] = que.front(); que.pop();
		house[idx]++;
		for (int k = 0; k < 4; k++) {
			if (x + dir_x[k] < 0 || x + dir_x[k] >= map.size() ||
				y + dir_y[k] < 0 || y + dir_y[k] >= map.size() ||
				map[x+dir_x[k]][y+dir_y[k]] != -1) continue;
			que.push({ x + dir_x[k], y + dir_y[k] });
			map[x + dir_x[k]][y + dir_y[k]] = cnt;
		}
	}
}