[백준] 2667번 단지번호붙이기

단계별로 풀어보기 DFS와 BFS의 3단계 문제

2667번: 단지번호붙이기

dfs로 풀었는데 시간이 꽤 많이 걸렸다. 두 시간 넘게 걸린 것 같다.

그래프의 탐색이나 이렇게 배열이 주어졌을 때의 탐색이나 방법은 똑같은데 괜히 복잡하게 생각한 것 같다.

덕분에 이제 dfs가 조금 익숙해진 것 같다.

def dfs(row, col, clist):
    if li[row][col] == '0' or visited[row][col]:
        return 0
    stack = []
    stack.append((row, col))
    c = 0
    while stack:
        cur = stack.pop()
        if not visited[cur[0]][cur[1]]:
            visited[cur[0]][cur[1]] = True
            c += 1
        if li[cur[0] - 1][cur[1]] == '1' and not visited[cur[0] - 1][cur[1]]:
            if 1 <= cur[0] - 1 <= n and 1 <= cur[1] <= n:
                stack.append((cur[0] - 1, cur[1]))
        if li[cur[0] + 1][cur[1]] == '1' and not visited[cur[0] + 1][cur[1]]:
            if 1 <= cur[0] + 1 <= n and 1 <= cur[1] <= n:
                stack.append((cur[0] + 1, cur[1]))
        if li[cur[0]][cur[1] - 1] == '1' and not visited[cur[0]][cur[1] - 1]:
            if 1 <= cur[0] <= n and 1 <= cur[1] - 1 <= n:
                stack.append((cur[0], cur[1] - 1))
        if li[cur[0]][cur[1] + 1] == '1' and not visited[cur[0]][cur[1] + 1]:
            if 1 <= cur[0] <= n and 1 <= cur[1] + 1 <= n:
                stack.append((cur[0], cur[1] + 1))
    clist.append(c)
    return 1
n = int(input())
from sys import stdin

li = []
clist = []
for i in range(n):
    rawInput = stdin.readline()
    li.append(list(rawInput))
    li[i].insert(0, '0')
li.insert(0, [0] * (n + 2))
li.append([0] * (n + 2))
for i in range(1, n + 1):
    li[i][n + 1] = '0'
visited = [[False for j in range(n + 2)] for i in range(n + 2)]
count = 0
for i in range(1, n + 1):
    for j in range(1, n + 1):
        count += dfs(i, j, clist)
clist.sort()
print(count)
for i in clist:
    print(i)

 

27일 뒤 C++로 다시 풀어보기

다시 풀어보니 정말 쉽게 풀었다.

#include <iostream>
#include <tuple>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
using namespace std;


int main() {
	int n;
	cin >> n;
	vector<string> map(n);
	for (int i = 0; i < n; i++) {
		cin >> map[i];
	}
	vector<int> countApartment;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == '1') {
				queue<pair<int, int>> q;
				q.push(make_pair(i, j));
				int count = 0;
				while (!q.empty()) {
					pair<int, int> cur = q.front();
					q.pop();
					if (map[cur.first][cur.second] == '1') {
						map[cur.first][cur.second] = '2';
						count++;
						if (cur.first - 1 >= 0 && map[cur.first - 1][cur.second] == '1') {
							q.push(make_pair(cur.first - 1, cur.second));
						}
						if (cur.first + 1 < n && map[cur.first + 1][cur.second] == '1') {
							q.push(make_pair(cur.first + 1, cur.second));
						}
						if (cur.second - 1 >= 0 && map[cur.first][cur.second - 1] == '1') {
							q.push(make_pair(cur.first, cur.second - 1));
						}
						if (cur.second + 1 < n && map[cur.first][cur.second + 1] == '1') {
							q.push(make_pair(cur.first, cur.second + 1));
						}
					}
				}
				countApartment.push_back(count);
			}
			else continue;
		}
	}
	sort(countApartment.begin(), countApartment.end());
	cout << countApartment.size() << endl;
	for (int i = 0; i < countApartment.size(); i++) {
		cout << countApartment[i] << endl;
	}
	return 0;
}