[CodeUp]No.4421 단지 번호 붙이기

약간, 정말로 약간의 난이도가 있는 문제입니다.

난이도 : ★★☆☆☆ (2/ 5)

문제정보

이 문제는 "Flood Fill"이라는 알고리즘을 이용하여 해결할 수 있습니다.

Flood Fill 알고리즘에 대한 설명은 아래 링크에서 봐주세요. 

URL : https://ko.wikipedia.org/wiki/%ED%94%8C%EB%9F%AC%EB%93%9C_%ED%95%84

문제 풀이 소스

 

#include <stdio.h>

#include <stdlib.h>

#include <algorithm>




using namespace std;

 

void f(int y, int x, int num);

 

char Map[30][30];

int ans[170];

int Map_Size;

 

int main(void)

{

    int i, j, apt_num=0;

    scanf("%d", &Map_Size);

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

        scanf("%s", Map[i]);

    }

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

        for(j=0;j<Map_Size;j++) {

            if(Map[i][j]=='1') {

                f(i, j, apt_num);

                apt_num++;

            }

        }

    }

    sort(ans, ans+apt_num);

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

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

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

    }

    return 0;

}

void f(int y, int x, int num)

{

    Map[y][x] = '0';

    ans[num]++;

    if(y-1>=0 && Map[y-1][x] == '1')

        f(y-1, x, num);

    if(y+1<=Map_Size && Map[y+1][x] == '1')

        f(y+1, x, num);

    if(x-1>=0 && Map[y][x-1] == '1')

        f(y, x-1, num);

    if(x+1<=Map_Size && Map[y][x+1] == '1')

        f(y, x+1, num);

}

함수 f는 Flood Fill 알고리즘을 이용하여 

현재 지도의 좌표에서 상하좌우로 연결된 곳이 또 있다면 그 곳으로 이동하여 번호를 표시하는 함수입니다.

자신의 상하좌우에 연결된 부분이 있는지 그리고 자신이 탐색한 부분이 Map을 벗어나지 않는지 확인할 if문이 필요합니다.

특히 지정된 Map을 벗어나지 않도록 하는 것이 가장 중요합니다.

(Map을 벗어나서 탐색을 할 경우 정답으로 인정되지 않고 오류가 납니다.)

저의 소스코드가 무조건 가장 효율적인 방법이라고 장담할 수는 없습니다. 

그렇기 때문에 소스코드를 분석하셔서 참고용으로만 사용하시는 것을 추천드립니다.

감사합니다.

(수정)

백준온라인저지 2667번 입니다.