백준 BOJ 2667 - 단지번호붙이기

매일 문제 하나씩은 풀어보려 하고 있다.

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

2667번: 단지번호붙이기

일단 25x25의 상대적으로 좁은 공간이라

배열을 좀 넉넉히 선언해줬고,

배열을 한번 다 훝고지나가면서 탐색해도 시간복잡도는 문제가 없겠다 싶어서

배열을 싹 훝고

만약 값이 1이라면 재귀함수를 돌려서

그와 인접한 건물들을 싹다 0으로 만들고(중복 없애려고)

카운터를 하나씩 올려줬다.

#include <stdio.h>
#include <algorithm>

int arr[1001] = {0};
char map[31][31] = {0};
int cnt=0, ret=0;

int f(int x, int y){
	ret+=1;
	map[x][y] = 0;
	if(map[x+1][y] == '1')dfs(x+1,y);
	if(map[x-1][y] == '1')dfs(x-1,y);
	if(map[x][y+1] == '1')dfs(x,y+1);
	if(map[x][y-1] == '1')dfs(x,y-1);
	return ret;
}

int main(){
	char tmp;
	int n,t=0;
	scanf("%d\n", &n);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			scanf("%c", &map[i][j]);
		}
		scanf("%c", &tmp);
	}
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(map[i][j] == '1'){
				cnt++;
				ret=0;
				arr[t] = f(i,j);
				t++;
			}
		}
	}
	printf("%d\n", cnt);
	std::sort(arr, arr+t);
	for(int i=0; i<t; i++) printf("%d\n", arr[i]);
	return 0;
}

우선 n을 입력받고 포문을 돌려서 값들을 입력을 받는데

​

int값의 경우에는 1010111을 한 숫자로 취급해서 기각.

문자열의 경우에는 1010101을 [1]부터 받아야하는데 어떻게 그리 받는지 모르겠어서 기각

(탐색시 [x-1]을 방문하기때문에 0의 경우는 [-1]을 방문함)

마지막으로 문자를 이용해서 구현했다 ㅠ.

\n도 일단 문자기 때문에 배열에 들어갈수 있어서

n 입력받을때 \n붙여서 받아주고

나머지 \n들은 tmp 변수에 들어간다.

​

그다음 1번부터 n번까지 돌아다니면서

만약 값이 '1'이라면(아까 문자로 받았으므로)

f()함수를 실행시켜 단지의 집의 수를 가져와 배열에 저장하고

배열의 인덱스 t를 1 올려준다.

​

f()함수에서는 먼저 받은 x,y좌표를 0으로 만들고, ret에 단지수를 저장한뒤,

사방으로 단지가 있는지 찾아서 방문한다.

방문하면 또다시 0으로 만들고.... 하는 과정을 반복하도록 재귀로 짰고,

마지막에 모든 값을 싹 모아서 ret로 반환해준다.

​

이제 배열에 있는 내용을 정렬하고, cnt값과 같이 출력해주면 된다.

(cnt는 총 단지수)

​

아직 프로그래밍을 잘 못해서 소스코드가 좀 더러울수 있다.