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

문제링크 : https://www.acmicpc.net/problem/2667

💻 문제 풀이 : C++

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

#define MAX_MAP_SIZE 30

using namespace std;

struct Coord {
	int row;
	int col;
};

int N;
int MAP[MAX_MAP_SIZE][MAX_MAP_SIZE];
int VISITED[MAX_MAP_SIZE][MAX_MAP_SIZE];
vector<int> house;

int dr[4] = {0,0,-1,1};
int dc[4] = {-1,1,0,0};

void bfs(Coord now)
{
	int cnt = 0;
	queue<Coord> nowQ;
	nowQ.push(now);
	while (!nowQ.empty())
	{
		int now_r = nowQ.front().row;
		int now_c = nowQ.front().col;
		nowQ.pop();
		for (int i = 0; i < 4; i++)
		{
			int next_r = now_r + dr[i];
			int next_c = now_c + dc[i];
			if (next_r < 0 || next_c < 0 || next_r >= N || next_c >= N) continue;
			if (VISITED[next_r][next_c] != 0) continue;
			if (MAP[next_r][next_c] == 0) continue;
			VISITED[next_r][next_c] = 1;
			nowQ.push({ next_r, next_c });
			cnt++;
		}
	}
	house.push_back(cnt+1);
}

int main()
{
	cin >> N;
	
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			char input;
			cin >> input;
			MAP[i][j] = input - 48;
		}
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (MAP[i][j] == 1 && VISITED[i][j] != 1)
			{
				Coord now = { i, j };
				VISITED[i][j] = 1;
				bfs(now);
			}
		}
	}
	sort(house.begin(), house.end());

	cout << house.size() << endl;
	for (int i = 0; i < house.size(); i++)
		cout << house[i] << endl;

	return 0;
}

💻 문제 풀이 : Python

import sys
from collections import deque

n = int(input())
graph = [list(map(int, input())) for _ in range(n)]

def bfs(graph, row, col):
    dr = [0, 0, -1, 1]
    dc = [-1, 1, 0, 0]
    queue = deque()
    queue.append((row, col))
    graph[row][col] = 0
    cnt = 1

    # MAP행렬 전체탐색하기??
    while queue:
        row, col = queue.popleft()

        for i in range(4):
            nr = row + dr[i]
            nc = col + dc[i]

            if nr < 0 or nc < 0 or nr >= n or nc >= n:
                continue

            if graph[nr][nc] == 1:
                graph[nr][nc] = 0
                queue.append((nr, nc))
                cnt += 1
    return cnt

count = [bfs(graph, i, j) for i in range(n) for j in range(n) if graph[i][j] == 1]

count.sort()
print(len(count))
for i in range(len(count)):
    print(count[i])ㅍ

---

📌 memo

😊 Python

MAP 전체탐색하기

while queue:
	# code~~

이중포문 + 조건문

count = [bfs(graph, i, j) for i in range(n) for j in range(n) if graph[i][j] == 1]

---

ref)
https://velog.io/@falling_star3/%EB%B0%B1%EC%A4%80Python-2667%EB%B2%88-%EB%8B%A8%EC%A7%80%EB%B2%88%ED%98%B8%EB%B6%99%EC%9D%B4%EA%B8%B0