[백준 알고리즘] 2667번 단지번호붙이기

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력과 출력

첫 번째 줄에는 지도의 크기 N(5<=N<=25)이 입력되고, 그 다음에는 N줄에 N개의 자료가 입력된다

결과값은 총 단지수를 출력하고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하는것이다

풀이

유기농 배추, 방금 풀었던 음식물 피하기 문제처럼 행렬로 input이 들어오게된다. 엄청 자세히 생각해보자면 이전에 푼 두 방법이 DFS가 아니라고 할 수도 있고 DFS라고 할 수도있는 것 같다 사실 약간 헷갈린다.. 처음엔 내가 DFS로 안풀었네! 라고 생각했는데 또 어떻게 보면 계속 깊이 탐색하는 부분에서 DFS니까... 그렇게 풀어도 틀리지않아서 맞습니다였지만 이 문제는 vector를 이용해서 만든 그 DFS를 이용해서 풀어보고싶다.

고민되는게 N*N 만큼 vertex가 있다고 생각해야하는지 아닌지..가 일단 첫번째고 두번째는 두자리인덱스를 그대로 사용할건지인데..

근데 n*n만큼 정점을 안만든다 생각하니 문제를 더 풀기어려울거같으니 일단 n*n만큼 vertex를 만들고 vector<vector<vector<int>>> v;  이렇게 선언하면될것같은데 괜찮은...생각일지 모르겠다. visited 벡터도 2차원으로 만든 다음에 없는 정점일 경우 -1로 두고 있다면 0으로 두고 첫번째 DFS할때는 1로 바꿔주고 그 이후 컴포넌트 증가할때마다 ++해줘서 visited값을 바꿔주고 하면 되겠다.

* 결국 또 만들어놓은거 말고 전에 풀었던 문제 코드처럼 짰다 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ...

점점 비효율적으로 짜는거 같다........

+ 2018.11.03 추가

풀었던 문제를 다시 보며, 어떻게 풀었는지 어떻게 생각이 변화하는지 보는데 이 당시에는 꼭 그래프가 있어야 DFS를 푼다고 생각을 했나보다. 백준에서 이 문제를 지나가다?가 틀렸습니다 이길래 다시 풀게 됐는데 위의 캡쳐결과가 런타임 에러로 바뀌어 있었고 로직 자체는 그 당시와 같이 생각해서 금방 다시 풀었다. 밑에 코드를 내려보니까 확실히 눈으로 보기 어렵게 짠.. 것 같긴하다. 그냥 dx, dy 더해줄 수 있도록 배열만들어두고 for문으로 4번 반복하면 5줄이면 가능한데.. 다른 문제를 풀면서 이러한 부분들은 자연스레 고쳐지는 것 같다! 역시 많이 풀어봐야함을 오늘도 느낀다.

2018.01.18 코드

#include<stdio.h>

#define max(x, y) x > y ? x : y

void check(int i, int j);

int a[26][26];

int results[26];

int n, m;

int cnt; 

void sorting(int t);

void main()

{

int i, j, t=0;

char c;

int result=0;

scanf("%d\n", &n);

for(i=1; i<=n ;i++){

for(j=1; j<=n ; j++){

scanf("%c", &c);

a[i][j] = c-'0';

}

scanf("%c", &c);

}

for(i=1; i<=n; i++)

{

for(j=1; j<=n; j++){

cnt = 0;

if(a[i][j] == 1){

check(i, j);

results[t++]=cnt; 

}

}

}

sorting(t);

printf("%d\n", t);

for(i=0; i<t; i++)

printf("%d\n", results[i]);

}

void sorting(int t)

{

int i, j, tmp;

for (i = 0; i < t; i++) {

        for (j = 0; j < t - i-1 ; j++) {

            if (results[j] > results[j+1]) {

                tmp = results[j];

results[j] = results[j+1];

results[j+1] = tmp;

            }

        }

    }

}

void check(int i, int j)

{

int result=0;

a[i][j]=0;

cnt++;

if(i < 1  || j < 1 || i > n || j > n)

return ;

//오른쪽 보기

if(j+1<=n && a[i][j+1] == 1)

{

check(i, j+1);

}

//왼쪽보기

if(j-1>=0 && a[i][j-1] == 1)

{

check(i, j-1);

}

//위쪽보기

if(i-1>=0 && a[i-1][j] == 1)

{

check(i-1, j);

}

//아래쪽보기

if(i+1<=n && a[i+1][j] == 1)

{

check(i+1, j);

}

}

2018.11.03 코드

#include<cstdio>

#include<algorithm>

#include<vector>

#include<functional>

using namespace std;

int N;

int map[26][26];

int visit[26][26];

int cnt;

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

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

void DFS(int x, int y){

visit[x][y] = 1;

cnt++;

for(int i=0; i<4; i++){

if(x+dx[i] < 0 || x+dx[i] >= N ||

y+dy[i] <0 || y+dy[i] >= N)

continue;

if(visit[x+dx[i]][y+dy[i]] == 0)

DFS(x+dx[i], y+dy[i]);

}

}

int main(){

vector<int> result;

scanf("%d", &N);

for(int i=0; i<N; i++){

for(int j=0; j<N; j++){

scanf("%1d", &map[i][j]);

visit[i][j] = !map[i][j];

}

}

for(int i=0; i<N; i++){

for(int j=0; j<N; j++){

if(visit[i][j] == 0){

cnt=0;

visit[i][j] = 1;

DFS(i, j);

result.push_back(cnt);

}

}

}

printf("%d\n", result.size());

sort(result.begin(), result.end());

for(int i=0; i<result.size(); i++)

printf("%d\n", result[i]);

return 0;

}