[백준 2667][🤍1] 단지 번호 붙이기 (DFS, BFS)

🚀 난이도

🤍 실버 1

🚀 문제

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

🚀 내 풀이

• 그래프 하나를 “단지”에 대응 시킨다. 즉, 연결된 그래프(= 단지)가 여러개일 수 있기 때문에 하나의 그래프 탐색이 끝나도 아직 방문 안한 집이 보이면 새로운 그래프라는 뜻이므로 또 탐색을 시도한다.
  • DFS, BFS 를 지도의 모든 지점에 대해 방문 안한 집이면 실행하도록 함
• DFS 로도 풀이했고, BFS 로도 풀이했다.
  • DFS 👉 그 바로 즉시 방문 (깊이 우선)
  • BFS 👉 큐에 삽입해놓고 나중에 방문 예약 (너비 우선)

🔥 DFS 풀이 ⭕

#include <bits/stdc++.h>

using namespace std;

// 상,하,좌,우 방향
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };

struct Pos {
	int y;
	int x;
};

void DFS(vector<string>& map, vector<vector<bool>>& checked, int& count, Pos now) {
	int n = map.size();
	for (int i = 0; i < 4; ++i) {
		Pos next{ now.y + dy[i], now.x + dx[i] };
	    
		if (next.x < 0 || next.x >= n || next.y < 0 || next.y >= n) continue; // 범위를 벗어난 곳이면 못 감
		if (map[next.y][next.x] == '0') continue; // 집이 아닌 곳은 방문할 이유가 없음
		if (checked[next.y][next.x]) continue; // 이미 방문 했던 곳이면 X

		checked[next.y][next.x] = true; // 방문 체크
		count++; // 집 카운트
		DFS(map, checked, count, next); // 방문 하러 ㄱㄱ
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int n;
	cin >> n; 
	vector<string> map(n);
	for (int i = 0; i < n; ++i)
		cin >> map[i];

	vector<int> group;
	vector<vector<bool>> checked(n, vector<bool>(n));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (map[i][j] == '1' && !checked[i][j]) {
				Pos start{ i, j };
				checked[start.y][start.x] = true;
				int count = 1; // 출발 집
				DFS(map, checked, count, start);
                // DFS 를 다 돌고오면 해당 그래프(=단지) 내의 연결된 집 개수가 count 에 담기게 된다.
				group.push_back(count);
			}
		}
	}
	cout << group.size() << '\n';
	sort(group.begin(), group.end());
	for (int i = 0; i < group.size(); ++i)
		cout << group[i] << '\n';
}

🔥 BFS 풀이 ⭕

#include <bits/stdc++.h>

using namespace std;

int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };

struct Pos {
	int y;
	int x;
};

void BFS(vector<string>& map, vector<vector<bool>>& checked, int& count, Pos start) {
	queue<Pos> q;
	q.push(start);
	checked[start.y][start.x] = true;
	count = 1;

	int n = map.size();
	while (!q.empty()) {
		Pos now = q.front();
		q.pop();

		for (int i = 0; i < 4; ++i) {
			Pos next{ now.y + dy[i], now.x + dx[i] };

			if (next.x < 0 || next.x >= n || next.y < 0 || next.y >= n) continue;
			if (map[next.y][next.x] == '0') continue;
			if (checked[next.y][next.x]) continue;

			checked[next.y][next.x] = true;
			count++;
			q.push(next);
		}
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int n;
	cin >> n; 
	vector<string> map(n);
	for (int i = 0; i < n; ++i)
		cin >> map[i];

	vector<int> group;
	vector<vector<bool>> checked(n, vector<bool>(n));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (map[i][j] == '1' && !checked[i][j]) {
				Pos start{ i, j };
				int count;
				BFS(map, checked, count, start);

				group.push_back(count);
			}
		}
	}
	cout << group.size() << '\n';
	sort(group.begin(), group.end());
	for (int i = 0; i < group.size(); ++i)
		cout << group[i] << '\n';
}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기