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

5월 18일(목) - 그래프와 순회 (2667번)

2667번: 단지번호붙이기

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

1. 단지를 구성하기 위해서 상하좌우의 집의 존재 여부를 확인하는 방법을 만들어내지 못 함

-> 다른 풀이를 찾아보니 (-1,0), (1,0), (0,-1), (0,1) 을 x와 y값으로 나누어서 각각을 더해주며 집의 존재여부를 확인

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

(풀이참고 -> https://velog.io/@ohdowon064/BOJ-2667번-단지번호붙이기-C언어 )

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int graph[26][26] = { 0 };
int apart[26 * 26] = { 0 };
int n, count, sum = 0;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

int dfs(int x, int y)
{
    if (x < 0 || y < 0 || x >= n || y >= n)
    {
        return 0;
    }

    if (graph[x][y] == 1)
    {
        graph[x][y] = 0;
        count++;

        for (int i = 0; i < 4; i++)
        {
            dfs(x + dx[i], y + dy[i]);
        }
        return 1;

    }
    return 0;

}

int main(void)
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%1d", graph[i] + j);
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (dfs(i, j) == 1)
            {
                apart[count]++;
                count = 0;
                sum++;
            }
        }
    }

    printf("%d\n", sum);
    for (int i = 0; i < 26 * 26; i++)
    {
        if (apart[i] != 0)
        {
            int k = apart[i];
            for (int j = 0; j < k; j++)
            {
                printf("%d\n", i);
            }
        }
    }

    return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ