백준 2667: 단지번호붙이기 (Python, C++) - dfs

문제

2667번: 단지번호붙이기

 

 

유명한  dfs 문제이다. (그림 출처 : 백준사이트)

 

n을 입력받은 뒤 첫 번째 그림처럼 n*n 배열이 주어지는데

1이 상하좌우로 이어지는 영역을 하나의 단지로 구분한다.

한 단지 영역내의 1들은 각 단지의 집의 개수이다.

 

두번재 그림을 보면 3단지가 있고 각각 집의 개수는 7,8,9개씩 이다.

단지의 개수와 집의 개수를 오름차순으로 정렬해 출력하면 되는 문제이다.

 

예전에 C++로 풀었던 문제여서 이번엔 파이썬으로 풀어봤는데

계속 이맞왜틀 ㅡㅡ 상태였는데 집개수가 0인 경우를 출력을 안했었다는걸 알게됨;

 

 

 

풀이1 (python)

dx = [1,0,-1,0]
dy = [0,1,0,-1]

cnt=0
def dfs(x,y):
    global cnt
    v[x][y]=1
    cnt+=1 #집 count
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if(0<=nx<n and 0<=ny<n and v[nx][ny]==0 and arr[nx][ny]==1):
            dfs(nx,ny)

if __name__ == '__main__':
    n = int(input())
    v = [[0]*n for _ in range(n)]
    arr = []
    dan = [] #단지수

    for _ in range(n):
        arr.append(list(map(int,input())))

    for i in range(n):
        for j in range(n):
            if arr[i][j]==1 and v[i][j]==0:
                dfs(i,j)
                dan.append(cnt)
                cnt=0

    dan.sort()
    print(len(dan)) #단지 수
    if len(dan)==0:print(0)
    for d in dan:print(d) #집 수

 

풀이2 (C++)

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N, M, A[25][25], visit[25][25],ny,nx;
int dan_cnt =1, cnt = 1;
int dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 };

vector<int>dan;
vector<pair<int, int>>pos;
queue<pair<int, int>>q;

void BFS(int y, int x, int dan_cnt) {
	q.push({ y,x });
	visit[y][x] = dan_cnt;
	cnt = 1;
	while (!q.empty()) {
		int cy = q.front().first;
		int cx = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = cy + dy[i];
			int nx = cx + dx[i];
			if (A[ny][nx]!=1||visit[ny][nx] !=0|| ny < 0 || nx < 0 || ny >= N || nx >= N)continue;

			visit[ny][nx] = dan_cnt;
			q.push({ ny,nx });
			cnt++;
		}
	}
}

int main() {//플러드필,연결요소
	/*ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);*/
	
	//memset(visit, -1, sizeof(visit));
	
	scanf("%d", &N);
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			scanf("%1d", &A[y][x]);
			if (A[y][x] == 1)  pos.push_back({ y,x });
		}
	}

	for (int i = 0; i < pos.size(); i++) {
		int y = pos[i].first;
		int x = pos[i].second;
		if (visit[y][x] == 0) { BFS(y, x, dan_cnt++); dan.push_back(cnt); }
	}

	sort(dan.begin(),dan.end());
	printf("%d\n", dan_cnt-1);
	for (int i = 0; i < dan.size(); i++) {
		printf("%d\n", dan[i]);
	}
	return 0;
}

C++ 코드는 2년 전 코드여서인지 내가 짰는데도 낯선느낌이다..ㅎ ;;

 

해피엔딩 ~