본문 바로가기
C/자료구조와 알고리듬

Chapter 14. DFS

by GameStudy 2021. 11. 28.

Def) 그래프 순회(Graph Traversal)

  - 하나의 정점에서 시작하여 모든 정점들을 한 번씩 방문하는 작업

  - 많은 문제들이 그래프 순회를 이용하여 해결될 수 있음.

    ex. 두 정점 사이의 연결 경로가 있는지 검사, 최단 거리 검사 등등

  - 대표적인 그래프 순회 방법으로는

    깊이 우선 탐색(Depth First Search), 너비 우선 탐색(Breadth First Search)

 

Def) 깊이 우선 탐색(DFS, Depth First Search)

  - 현재 정점과 인접한 정점 중 하나를 선택하여 이동하는 과정을 반복.

    더이상 이동할 정점이 없을 경우, 뒤쪽으로 백트래킹(Backtracking)하여

    다시 이동할 경로를 탐색.

  - 시작 정점으로부터 거리가 멀어지는(깊이가 깊어지는) 방식으로 정점을 탐색

  - 보통 재귀 또는 스택을 이용하여 구현

Thm) DFS 구현 With 재귀함수

<hide/>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

enum {
    FALSE = 0,
    TRUE = 1,
    INVALIED_INDEX = -1,
    MAX_COUNT = 101
};

int g_nAdjMatrix[MAX_COUNT][MAX_COUNT] = { 0, };
int g_nVisitMatrix[MAX_COUNT] = { 0, };
size_t g_uVertexCount, g_uEdgeCount, g_uStartVertex = 1;

void DFS(size_t _uCurrentVertex);

int main(void)
{
    size_t i, uVertex1, uVertex2;
    
    scanf("%zu %zu", &g_uVertexCount, &g_uEdgeCount);
    for (i = 1; i <= g_uEdgeCount; ++i)
    {
        scanf("%zu %zu", &uVertex1, &uVertex2);
        g_nAdjMatrix[uVertex1][uVertex2] = TRUE;
        g_nAdjMatrix[uVertex2][uVertex1] = TRUE;
    }

    DFS(g_uStartVertex);

    return 0;
}

void DFS(size_t _uCurrentVertex)
{
    size_t i;

    g_nVisitMatrix[_uCurrentVertex] = TRUE;
    for (i = 1; i <= g_uVertexCount; ++i)
    {
        if (FALSE == g_nVisitMatrix[i] && TRUE == g_nAdjMatrix[_uCurrentVertex][i])
        {
            printf("%zu -> %zu\n", _uCurrentVertex, i);
            DFS(i);
        }
    }
}

 

Thm) 재귀함수 With 스택

 

 

Ex) 바이러스

<hide/>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

enum {
    FALSE = 0,
    TRUE = 1,
    INVALIED_INDEX = -1,
    MAX_COUNT = 101
};

int g_nAdjMatrix[MAX_COUNT][MAX_COUNT] = { 0, };
int g_nVisitMatrix[MAX_COUNT] = { 0, };
size_t g_uVertexCount, g_uEdgeCount, g_uStartVertex = 1;
size_t g_uCount = 0;

void DFS(size_t _uCurrentVertex);

int main(void)
{
    size_t i, uVertex1, uVertex2;
    
    scanf("%zu %zu", &g_uVertexCount, &g_uEdgeCount);
    for (i = 1; i <= g_uEdgeCount; ++i)
    {
        scanf("%zu %zu", &uVertex1, &uVertex2);
        g_nAdjMatrix[uVertex1][uVertex2] = TRUE;
        g_nAdjMatrix[uVertex2][uVertex1] = TRUE;
    }

    DFS(g_uStartVertex);

    printf("%zu", g_uCount);

    return 0;
}

void DFS(size_t _uCurrentVertex)
{
    size_t i;

    g_nVisitMatrix[_uCurrentVertex] = TRUE;
    for (i = 1; i <= g_uVertexCount; ++i)
    {
        if (FALSE == g_nVisitMatrix[i] && TRUE == g_nAdjMatrix[_uCurrentVertex][i])
        {
            ++g_uCount;
            DFS(i);
        }
    }
}
<hide/>

// TestCase 1
7
6
1 2
2 3
1 5
5 2
5 6
4 7
// Expected
4

// TestCase 2
11
14
11 8
5 6
10 11
8 2
2 7
9 7
4 11
1 8
2 3
2 11
7 8
5 3
1 8
2 11
// Expected
10

 

Ex) 그림 개수 세기

<hide/>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

enum {
	FALSE = 0,
	TRUE = 1,
	INVALIED_INDEX = -1,
	MAX_COUNT = 101,
	DIRECTION = 4
};

int g_nAdjMat[MAX_COUNT][MAX_COUNT] = {0,};
int g_nVisitMat[MAX_COUNT][MAX_COUNT] = {0,};
size_t g_uVCount = 10, g_uECount;
int g_nDirMatix[DIRECTION][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

void DFS(size_t _uCurrVRow, size_t _uCurrVCol);

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

	for (i = 1; i <= g_uVCount; ++i)
	{
		for (j = 1; j <= g_uVCount; ++j)
		{
			if (FALSE == g_nVisitMat[i][j] && TRUE == g_nAdjMat[i][j])
			{
				++uPictureCount;
				DFS(i, j);
			}
		}
	}

	printf("%zu", uPictureCount);

	return 0;
}

void DFS(size_t _uCurrVRow, size_t _uCurrVCol)
{
	size_t i, j;

	g_nVisitMat[_uCurrVRow][_uCurrVCol] = TRUE;
	for (i = 0; i < DIRECTION; ++i)
	{
		size_t uNextVRow = _uCurrVRow + g_nDirMatix[i][0];
		size_t uNextVCol = _uCurrVCol + g_nDirMatix[i][1];
		if (TRUE == g_nVisitMat[uNextVRow][uNextVCol]) continue;
		if (TRUE == g_nAdjMat[uNextVRow][uNextVCol] &&
			1 <= uNextVRow && uNextVRow <= g_uVCount &&
			1 <= uNextVCol && uNextVCol <= g_uVCount)
		{
			DFS(uNextVRow, uNextVCol);
		}
	}
}
<hide/>

// TestCase 1
0 0 0 1 1 1 1 0 0 0
0 0 0 1 1 1 1 0 0 0
1 1 1 0 0 0 0 1 1 1
1 0 1 0 0 0 0 1 0 1
1 1 1 0 1 1 0 1 1 1
0 0 0 0 1 1 0 0 0 0
1 1 1 1 0 0 1 1 1 1
1 0 0 1 0 0 1 0 0 1
1 0 0 1 0 0 1 0 0 1
1 1 1 1 0 0 1 1 1 1
// Expected
6

// TestCase 2
1 1 0 1 1 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 1 1 1 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
// Expected
4

 

Ex) 호수의 수

<hide/>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

enum {
    FALSE = 0,
    TRUE = 1,
    MAX_COUNT = 101,
    DIRECTION = 8
};

int g_nAdjMat[MAX_COUNT][MAX_COUNT] = { 0, };
int g_nVisitMat[MAX_COUNT][MAX_COUNT] = {0,};
size_t g_uHeight, g_uWidth;
int g_nDirMat[DIRECTION][2] = { {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1} };

void DFS(int _nCurrVRow, int _nCurrVCol);

void print(void);

int main(void)
{
    size_t i, j, uCnt = 0;

    scanf("%zu %zu", &g_uWidth, &g_uHeight);
    for (i = 1; i <= g_uHeight; ++i)
    {
        for (j = 1; j <= g_uWidth; ++j)
        {
            scanf("%c ", &g_nAdjMat[i][j]);
        }
    }

    for (i = 1; i <= g_uHeight; ++i)
    {
        for (j = 1; j <= g_uWidth; ++j)
        {
            if (FALSE == g_nVisitMat[i][j] && 'L' == g_nAdjMat[i][j])
            {
                ++uCnt;
                DFS(i, j);
                print();
            }
        }
    }

    printf("%zu", uCnt);

    return 0;
}

void DFS(int _nCurrVRow, int _nCurrVCol)
{
    size_t i, j;

    g_nVisitMat[_nCurrVRow][_nCurrVCol] = TRUE;
    for (i = 0; i < DIRECTION; ++i)
    {
        int uNextVRow = _nCurrVRow + g_nDirMat[i][0];
        int uNextVCol = _nCurrVCol + g_nDirMat[i][1];
        if (TRUE == g_nVisitMat[uNextVRow][uNextVCol]) continue;
        if ('L' == g_nAdjMat[uNextVRow][uNextVCol] &&
            1 <= uNextVRow && uNextVRow <= g_uHeight &&
            1 <= uNextVCol && uNextVCol <= g_uWidth)
        {
            DFS(uNextVRow, uNextVCol);
        }
    }
}

void print(void)
{
    size_t i, j;

    for (i = 1; i <= g_uHeight; ++i)
    {
        for (j = 1; j <= g_uWidth; ++j)
        {
            printf("%d ", g_nVisitMat[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}
<hide/>

//TestCase
12 10
L . . . . . . . . L . .
. L . . . . . . . L L .
L L . . . . . . . . L .
. L . . . . . . . . . L
. . L . . . . . . . . L
. . . . . . L . . . . .
. . . . . L . L . . . .
. . . . L . L . L . . .
. . . . . L . L . . . .
. . . . . . L . . . . L
//Expected
4

 

Ex) 단지 번호 붙이기 (추후에 버블소트나 퀵소트 구현해서 붙히기.)

<hide/>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <bits/stdc++.h>
#include <algorithm>

bool comp(const int &a, const int &b)
{
    return a < b;
}

enum {
    FALSE = 0,
    TRUE = 1,
    MAX_COUNT = 101,
    DIRECTION = 4
};

int g_nAdjMat[MAX_COUNT][MAX_COUNT] = {0,};
int g_nVisitMat[MAX_COUNT][MAX_COUNT] = {0,};
size_t g_uSize;
int g_nDirMat[DIRECTION][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
int g_uCntArr[MAX_COUNT] = {0,};
size_t g_uCnt = 0;

void DFS(int _nCurrVRow, int _nCurrVCol);

int main(void)
{
    size_t i, j;

    scanf("%zu", &g_uSize);
    for (i = 1; i <= g_uSize; ++i)
    {
        for (j = 1; j <= g_uSize; ++j)
        {
            scanf("%1d", &g_nAdjMat[i][j]);
        }
    }

    for (i = 1; i <= g_uSize; ++i)
    {
        for (j = 1; j <= g_uSize; ++j)
        {
            if (FALSE == g_nVisitMat[i][j] && TRUE == g_nAdjMat[i][j])
            {
                ++g_uCntArr[g_uCnt];
                DFS(i, j);
                ++g_uCnt;
            }
        }
    }

    printf("%zu\n", g_uCnt);
    std::sort(g_uCntArr, g_uCntArr + g_uCnt, comp);
    for (i = 0; i < g_uCnt; ++i)
    {
        printf("%zu\n", g_uCntArr[i]);
    }


    return 0;
}

void DFS(int _nCurrVRow, int _nCurrVCol)
{
    size_t i, j;

    g_nVisitMat[_nCurrVRow][_nCurrVCol] = TRUE;
    for (i = 0; i < DIRECTION; ++i)
    {
        int nNextVRow = _nCurrVRow + g_nDirMat[i][0];
        int nNextVCol = _nCurrVCol + g_nDirMat[i][1];
        if (TRUE == g_nVisitMat[nNextVRow][nNextVCol]) continue;
        if (TRUE == g_nAdjMat[nNextVRow][nNextVCol] &&
            1 <= nNextVRow && nNextVRow <= g_uSize &&
            1 <= nNextVCol && nNextVCol <= g_uSize)
        {
            ++g_uCntArr[g_uCnt];
            DFS(nNextVRow, nNextVCol);
        }
    }

}
<hide/>

//TestCase
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000
//Expected
3
7
8
9

//TestCase
17
10111010110101111
11111110110101000
01111111001011101
10110101100000100
01001111000110111
11110000110111101
10111001101011100
11010101100111111
00101100010110100
01101100111100100
11000111111111111
11101011001101010
01001100001000111
00101011001110100
10001001011001001
11110101100001010
01011111011000010
//Expected
18
1
1
1
1
1
1
2
2
2
2
4
5
6
9
12
17
28
70

 

Ex) 친구인지 확인하기

<hide/>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

enum {
	FALSE = 0,
	TRUE = 1,
	MAX_COUNT = 56
};

int g_nAdjMat[MAX_COUNT][MAX_COUNT] = {0,};
int g_nVisitMat[MAX_COUNT] = {0,};
size_t g_uECnt;
int g_nBeginV, g_nFinishV, g_nFlag;

size_t change(char _ch);
void DFS(int _nCurrV);

int main(void)
{
	size_t i, j, uV1, uV2;
	char trash, ch1, ch2;

	scanf("%zu", &g_uECnt);
	fflush(stdin);
	getchar();
	for (i = 0; i < g_uECnt; ++i)
	{
		scanf("%c %c", &ch1, &ch2);
		getchar();
		uV1 = change(ch1);
		uV2 = change(ch2);
		g_nAdjMat[uV1][uV2] = TRUE;
		g_nAdjMat[uV2][uV1] = TRUE;
	}

	scanf("%c %c", &ch1, &ch2);
	getchar();
	g_nBeginV = change(ch1);
	g_nFinishV = change(ch2);
	DFS(g_nBeginV);

	if (g_nFlag == 0)
	{
		printf("none\n");
	}

	return 0;
}

size_t change(char _ch)
{
	if ('A' <= _ch && _ch <= 'Z') return (size_t)(_ch - 'A');
	else return (size_t)(_ch - 'a' + 26);
}

void DFS(int _nCurrV)
{
	size_t i;

	g_nVisitMat[_nCurrV] = TRUE;

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

		if (g_nFinishV == _nCurrV)
		{
			g_nFlag = 1;
			printf("friend\n");
			exit(0);
		}

		if (TRUE == g_nAdjMat[_nCurrV][i] && FALSE == g_nVisitMat[i])
		{
			DFS(i);
		}
	}
}

 

<hide/>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

enum {
    FALSE = 0,
    TRUE = 1,
    MAX_COUNT = 101
};

int g_nAdjMat[MAX_COUNT][MAX_COUNT] = {0,};
int g_nVisitMat[MAX_COUNT] = {0,};
size_t g_uVCnt, g_uECnt, g_uStartV, g_uFinishV, g_uFlag, g_uCnt;

void DFS(size_t _uCurrV);

int main(void)
{
    size_t i, j, uV1, uV2;

    scanf("%zu %zu %zu %zu", &g_uVCnt, &uV1, &uV2, &g_uECnt);

    g_uStartV = uV1 <= uV2 ? uV2 : uV1;
    g_uFinishV = uV1 <= uV2 ? uV1 : uV2;

    for (i = 0; i < g_uECnt; ++i)
    {
        scanf("%zu %zu", &uV1, &uV2);
        g_nAdjMat[uV1][uV2] = TRUE;
        g_nAdjMat[uV2][uV1] = TRUE;
    }

    DFS(g_uStartV);

    if (g_uFlag == 0)
    {
        printf("-1");
    }
    /*
    printf("%zu %zu %zu %zu\n", g_uVCnt, g_uStartV, g_uFinishV, g_uECnt);
    for (i = 0; i < g_uVCnt; ++i)
    {
        for (j = 0; j < g_uVCnt; ++j)
        {
            printf("%zu ", g_nAdjMat[i][j]);
        }
        printf("\n");
    }
    */
    return 0;
}

void DFS(size_t _uCurrV)
{
    size_t i;

    g_nVisitMat[_uCurrV] = TRUE;
    for (i = g_uVCnt; i > 0; --i)
    {
        if (g_uFinishV == _uCurrV)
        {
            printf("%zu", g_uCnt);
            exit(0);
        }
        if (TRUE == g_nAdjMat[_uCurrV][i] && FALSE == g_nVisitMat[i])
        {

            printf("[%zu]: %zu => %zu\n", g_uCnt, _uCurrV, i);
            DFS(i);
        }
    }
}

 

Ex) 촌수 구하기

<hide/>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

enum {
    FALSE = 0,
    TRUE = 1,
    MAX_COUNT = 101
};

int g_nAdjMat[MAX_COUNT][MAX_COUNT] = {0,};
int g_nVisitMat[MAX_COUNT] = {0,};
size_t g_uVCnt, g_uECnt, g_uStartV, g_uFinishV, g_uFlag, g_uCnt;

void DFS(size_t _uCurrV);

int main(void)
{
    size_t i, j, uV1, uV2;

    scanf("%zu %zu %zu %zu", &g_uVCnt, &uV1, &uV2, &g_uECnt);

    g_uStartV = uV1 <= uV2 ? uV2 : uV1;
    g_uFinishV = uV1 <= uV2 ? uV1 : uV2;

    for (i = 0; i < g_uECnt; ++i)
    {
        scanf("%zu %zu", &uV1, &uV2);
        g_nAdjMat[uV1][uV2] = TRUE;
        g_nAdjMat[uV2][uV1] = TRUE;
    }

    DFS(g_uStartV);

    if (g_uFlag == 0)
    {
        printf("-1");
    }
    /*
    printf("%zu %zu %zu %zu\n", g_uVCnt, g_uStartV, g_uFinishV, g_uECnt);
    for (i = 0; i < g_uVCnt; ++i)
    {
        for (j = 0; j < g_uVCnt; ++j)
        {
            printf("%zu ", g_nAdjMat[i][j]);
        }
        printf("\n");
    }
    */
    return 0;
}

void DFS(size_t _uCurrV)
{
    size_t i;

    g_nVisitMat[_uCurrV] = TRUE;
    for (i = 1; i <= g_uVCnt; ++i)
    {
        if (g_uFinishV == _uCurrV)
        {
            printf("%zu", g_uCnt);
            exit(0);
        }
        if (TRUE == g_nAdjMat[_uCurrV][i] && FALSE == g_nVisitMat[i])
        {
            ++g_uCnt;
            printf("[%zu]: %zu => %zu\n", g_uCnt, _uCurrV, i);
            DFS(i);
        }
    }
}

 

 

Ex) 캔디팡

<hide/>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

enum {
    FALSE = 0,
    TRUE = 1,
    MAX_COUNT = 8,
    DIRECTION = 4
};

int g_nAdjMat[MAX_COUNT][MAX_COUNT] = {0,};
int g_nVisitMat[MAX_COUNT][MAX_COUNT] = {0,};
size_t g_uVCnt = 7, g_uStartVRow = 1, g_uStartVCol = 1, g_uCnt;
int g_nDirMat[DIRECTION][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

void DFS(size_t _uCurrVRow, size_t _uCurrVCol, int _nWeight);

int main(void)
{
    size_t i, j, uV, uPangCnt = 0;
    for (i = 1; i <= g_uVCnt; ++i)
    {
        for (j = 1; j <= g_uVCnt; ++j)
        {
            scanf("%d", &g_nAdjMat[i][j]);
        }
    }

    for (i = 1; i <= g_uVCnt; ++i)
    {
        for (j = 1; j <= g_uVCnt; ++j)
        {
            DFS(i, j, g_nAdjMat[i][j]);
            if (2 <= g_uCnt) ++uPangCnt;
            g_uCnt = 0;
        }
    }

    printf("%zu", uPangCnt);

    return 0;
}

void DFS(size_t _uCurrVRow, size_t _uCurrVCol, int _nWeight)
{
    size_t i;

    g_nVisitMat[_uCurrVRow][_uCurrVCol] = TRUE;
    for (i = 0; i < DIRECTION; ++i)
    {
        size_t uNextVRow = _uCurrVRow + g_nDirMat[i][0];
        size_t uNextVCol = _uCurrVCol + g_nDirMat[i][1];
        if (TRUE == g_nVisitMat[uNextVRow][uNextVCol]) continue;
        if (_nWeight == g_nAdjMat[uNextVRow][uNextVCol] &&
            1 <= uNextVRow && uNextVRow <= g_uVCnt &&
            1 <= uNextVCol && uNextVCol <= g_uVCnt)
        {
            ++g_uCnt;
            // printf("(%zu,%zu) => (%zu,%zu)\n", _uCurrVRow, _uCurrVCol, uNextVRow, uNextVCol);
            DFS(uNextVRow, uNextVCol, g_nAdjMat[uNextVRow][uNextVCol]);
        }
    }
}

 

Ex) 안전지대

<hide/>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

enum
{
    FALSE = 0,
    TRUE = 1,
    MAX_COUNT = 101,
    DIRECTION = 4
};

int g_nAdjMat[MAX_COUNT][MAX_COUNT] = {};
int g_nVisitMat[MAX_COUNT][MAX_COUNT] = {};
size_t g_nVCnt;
int g_nDirMat[DIRECTION][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

void DFS(size_t _uCurrVRow, size_t _uCurrVCol, size_t _uHeight);

int main(void)
{
    size_t uHeight, i, j, cnt = 0, max_cnt = 0;

    scanf("%zu", &g_nVCnt);
    for (i = 1; i <= g_nVCnt; ++i)
    {
        for (j = 1; j <= g_nVCnt; ++j)
        {
            scanf("%zu", &g_nAdjMat[i][j]);
        }
    }
    for (uHeight = 1; uHeight <= MAX_COUNT; ++uHeight)
    {
        for (i = 1; i <= g_nVCnt; ++i)
        {
            for (j = 1; j <= g_nVCnt; ++j)
            {
                if (FALSE == g_nVisitMat[i][j] && uHeight < g_nAdjMat[i][j])
                {
                    ++cnt;
                    DFS(i, j, uHeight);
                }
                
            }
        }

        if (cnt == 0) break;
        else
        {
            if (max_cnt < cnt)
            {
                max_cnt = cnt;
            }
        }
        cnt = 0;
        for (i = 1; i <= g_nVCnt; ++i)
        {
            for (j = 1; j <= g_nVCnt; ++j)
            {
                g_nVisitMat[i][j] = FALSE;
            }
        }

    }

    printf("%zu", max_cnt);


    return 0;
}

void DFS(size_t _uCurrVRow, size_t _uCurrVCol, size_t _uHeight)
{
    size_t i;

    g_nVisitMat[_uCurrVRow][_uCurrVCol] = TRUE;
    for (i = 0; i < DIRECTION; ++i)
    {
        size_t uNextVRow = _uCurrVRow + g_nDirMat[i][0];
        size_t uNextVCol = _uCurrVCol + g_nDirMat[i][1];
        if (TRUE == g_nVisitMat[uNextVRow][uNextVCol]) continue;
        if (_uHeight < g_nAdjMat[uNextVRow][uNextVCol] &&
            1 <= uNextVRow && uNextVRow <= g_nVCnt &&
            1 <= uNextVCol && uNextVCol <= g_nVCnt)
        {
            DFS(uNextVRow, uNextVCol, _uHeight);
        }
    }
}
<hide/>

// TestCase1
5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7
// Expected
5
// TestCase2
7
9 9 9 9 9 9 9
9 2 1 2 1 2 9
9 1 8 7 8 1 9
9 2 7 9 7 2 9
9 1 8 7 8 1 9
9 2 1 2 1 2 9
9 9 9 9 9 9 9
// Expected
6

 

Ex) 키 순서

<hide/>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

enum {
	FALSE = 0,
	TRUE = 1,
	MAX_COUNT = 501,
};

int g_nAdjMat[MAX_COUNT][MAX_COUNT] = {0,};
int g_nVisitMat[MAX_COUNT] = {0,};
size_t g_uVCnt, g_uECnt, g_uCnt;

void DFS(size_t _uCurrV1, size_t _uCurrV2);
void DFS1(size_t _uCurrV);
void DFS2(size_t _uCurrV);

int main(void)
{
	size_t i, j, k, uV1, uV2, sum = 0, uPersonCnt = 0;

	scanf("%zu %zu", &g_uVCnt, &g_uECnt);
	for (i = 1; i <= g_uECnt; ++i)
	{
		scanf("%zu %zu", &uV1, &uV2);
		g_nAdjMat[uV1][uV2] = TRUE;
	}

	for (i = 1; i <= g_uVCnt; ++i)
	{
		DFS1(i);
		sum += g_uCnt;
		g_uCnt = 0;
		for (j = 1; j <= g_uVCnt; ++j)
			g_nVisitMat[j] = FALSE;

		DFS2(i);
		sum += g_uCnt;
		g_uCnt = 0;
		if (g_uVCnt - 1 == sum)
		{
			++uPersonCnt;
		}
		
		for (j = 1; j <= g_uVCnt; ++j)
				g_nVisitMat[j] = FALSE;
		sum = 0;
				
	}

	printf("%zu", uPersonCnt);

	return 0;
}

void DFS(size_t _uCurrV1, size_t _uCurrV2)
{
	size_t i;

	g_nVisitMat[_uCurrV2] = TRUE;
	for (i = 1; i <= g_uVCnt; ++i)
	{
		if (FALSE == g_nVisitMat[i] &&
			TRUE == g_nAdjMat[_uCurrV2][i])
		{
			++g_uCnt;
			printf("(%zu, %zu) -> (%zu, %zu)\n", _uCurrV1, _uCurrV2, _uCurrV2, i);
			DFS(_uCurrV2, i);
		}
	}
}

void DFS1(size_t _uCurrV)
{
	size_t i;

	g_nVisitMat[_uCurrV] = TRUE;
	for (i = 1; i <= g_uVCnt; ++i)
	{
		if (FALSE == g_nVisitMat[i] &&
			TRUE == g_nAdjMat[_uCurrV][i])
		{
			++g_uCnt;
			DFS1(i);
		}
	}
}

void DFS2(size_t _uCurrV)
{
	size_t i;

	g_nVisitMat[_uCurrV] = TRUE;
	for (i = 1; i <= g_uVCnt; ++i)
	{
		if (FALSE == g_nVisitMat[i] &&
			TRUE == g_nAdjMat[i][_uCurrV])
		{
			++g_uCnt;
			DFS2(i);
		}
	}
}
<hide/>

// TestCase1
6 6
1 5
3 4
5 4
4 2
4 6
5 2
// Expected
1
// TestCase2
10 40
3 6
7 10
6 2
3 2
1 8
9 2
1 3
5 6
8 4
2 4
1 10
1 2
7 3
9 6
5 4
7 5
9 3
5 3
8 2
10 6
6 4
7 4
5 2
9 4
7 1
7 6
9 8
7 9
1 5
1 4
7 8
3 4
7 2
10 5
1 6
9 10
10 3
9 5
8 3
9 1
// Expected
7

 

Ex) 영역 구하기

<hide/>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

enum
{
    FALSE = 0,
    TRUE = 1,
    MAX_COUNT = 101,
    DIRECTION = 4
};

int g_nAdjMat[MAX_COUNT][MAX_COUNT] = {0,};
int g_nVisitMat[MAX_COUNT][MAX_COUNT] = {0,};
size_t g_uVRow, g_uVCol, g_uArea = 0;
int g_nDirMat[DIRECTION][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

void change(int* _pX, int* _pY);
void DFS(size_t _uCurrVRow, size_t _uCurrVCol);

int main(void)
{
    size_t i, j, k, uRectCnt, cnt = 0, uArrArea[MAX_COUNT] = {0,};
    int LBx, LBy, RTx, RTy;

    scanf("%zu %zu %zu", &g_uVRow, &g_uVCol, &uRectCnt);
    for (j = 0; j < g_uVRow; ++j)
    {
        for (k = 0; k < g_uVCol; ++k)
        {
            g_nAdjMat[j][k] = TRUE;
        }
    }

    for (i = 1; i <= uRectCnt; ++i)
    {
        scanf("%d %d %d %d", &LBx, &LBy, &RTx, &RTy);

        change(&LBx, &LBy);
        change(&RTx, &RTy);

        for (j = RTx; j < LBx; ++j)
        {
            for (k = LBy; k < RTy; ++k)
            {
                g_nAdjMat[j][k] = FALSE;
            }
        }
    }

    for (j = 0; j < g_uVRow; ++j)
    {
        for (k = 0; k < g_uVCol; ++k)
        {
            if (FALSE == g_nVisitMat[j][k] && TRUE == g_nAdjMat[j][k])
            {
                ++cnt;
                DFS(j,k);
                uArrArea[cnt - 1] = g_uArea + 1;
                g_uArea = 0;
            }
        }
    }

    printf("%zu\n", cnt);
    std::sort(uArrArea, uArrArea + cnt);
    for (i = 0; i < cnt; ++i)
        printf("%zu ", uArrArea[i]);
    /*
    printf("\n");
    for (j = 0; j < g_uVRow; ++j)
    {
    	for (k = 0; k < g_uVCol; ++k)
    	{
    		printf("%d ", g_nAdjMat[j][k]);
    	}
    	printf("\n");
    }
    */

    return 0;
}

void change(int* _pX, int* _pY)
{
    int temp;

    *_pY = g_uVRow - *_pY;
    *_pY = abs(*_pY);

    temp = *_pX;
    *_pX = *_pY;
    *_pY = temp;
}

void DFS(size_t _uCurrVRow, size_t _uCurrVCol)
{
    size_t i;

    g_nVisitMat[_uCurrVRow][_uCurrVCol] = TRUE;
    for (i = 0; i < DIRECTION; ++i)
    {
        size_t uNextVRow = _uCurrVRow + g_nDirMat[i][0];
        size_t uNextVCol = _uCurrVCol + g_nDirMat[i][1];
        if (TRUE == g_nVisitMat[uNextVRow][uNextVCol]) continue;
        if (TRUE == g_nAdjMat[uNextVRow][uNextVCol] &&
                0 <= uNextVRow && uNextVRow < g_uVRow &&
                0 <= uNextVCol && uNextVCol < g_uVCol)
        {
            ++g_uArea;
            DFS(uNextVRow, uNextVCol);
        }
    }
}
<hide/>

// TestCase
5 7 3
0 2 4 4
1 1 2 5
4 0 6 2
// Expected
3
1 7 13

 

Ex) 전광판 전구 

<hide/>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

enum {
    FALSE = 0,
    TRUE = 1,
    MAX_COUNT = 101,
    DIRECTION = 4
};

int g_nAdjMat[MAX_COUNT][MAX_COUNT] = {0,};
int g_nVisitMat[MAX_COUNT][MAX_COUNT] = {0,};
size_t g_uVRow, g_uVCol;
int g_nDirMat[DIRECTION][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

void DFS_off(size_t _uCurrVRow, size_t _uCurrVCol);
void DFS_on(size_t _uCurrVRow, size_t _uCurrVCol);

int main(void)
{
    size_t i, j, uOnCnt = 0, uOffCnt = 0;

    scanf("%zu %zu", &g_uVRow, &g_uVCol);
    for (i = 1; i <= g_uVRow; ++i)
    {
        for (j = 1; j <= g_uVCol; ++j)
        {
            scanf("%d", &g_nAdjMat[i][j]);
        }
    }

    for (i = 1; i <= g_uVRow; ++i)
    {
        for (j = 1; j <= g_uVCol; ++j)
        {
            if (FALSE == g_nVisitMat[i][j] && TRUE == g_nAdjMat[i][j])
            {
                ++uOffCnt;
                DFS_off(i, j);
            }
        }
    }

    for (i = 1; i <= g_uVRow; ++i)
    {
        for (j = 1; j <= g_uVCol; ++j)
        {
            g_nVisitMat[i][j] = FALSE;
        }
    }

    for (i = 1; i <= g_uVRow; ++i)
    {
        for (j = 1; j <= g_uVCol; ++j)
        {
            if (FALSE == g_nVisitMat[i][j] && FALSE == g_nAdjMat[i][j])
            {
                ++uOnCnt;
                DFS_on(i, j);
            }
        }
    }
    printf("%zu %zu", uOnCnt, uOffCnt);

    return 0;
}

void DFS_off(size_t _uCurrVRow, size_t _uCurrVCol)
{
    size_t i;

    g_nVisitMat[_uCurrVRow][_uCurrVCol] = TRUE;
    for (i = 0; i < DIRECTION; ++i)
    {
        size_t uNextVRow = _uCurrVRow + g_nDirMat[i][0];
        size_t uNextVCol = _uCurrVCol + g_nDirMat[i][1];
        if (TRUE == g_nVisitMat[uNextVRow][uNextVCol]) continue;
        if (TRUE == g_nAdjMat[uNextVRow][uNextVCol] &&
            1 <= uNextVRow && uNextVRow <= g_uVRow &&
            1 <= uNextVCol && uNextVCol <= g_uVCol)
        {
            DFS_off(uNextVRow, uNextVCol);
        }
    }
}

void DFS_on(size_t _uCurrVRow, size_t _uCurrVCol)
{
    size_t i;

    g_nVisitMat[_uCurrVRow][_uCurrVCol] = TRUE;
    for (i = 0; i < DIRECTION; ++i)
    {
        size_t uNextVRow = _uCurrVRow + g_nDirMat[i][0];
        size_t uNextVCol = _uCurrVCol + g_nDirMat[i][1];
        if (TRUE == g_nVisitMat[uNextVRow][uNextVCol]) continue;
        if (FALSE == g_nAdjMat[uNextVRow][uNextVCol] &&
            1 <= uNextVRow && uNextVRow <= g_uVRow &&
            1 <= uNextVCol && uNextVCol <= g_uVCol)
        {
            DFS_on(uNextVRow, uNextVCol);
        }
    }
}
<hide/>

// TestCase
5 6
0 0 1 0 1 1
0 1 1 0 0 0
0 0 1 0 0 0
1 1 1 1 1 1
0 0 0 1 0 0
// Expected
4 2
저작자표시 비영리 변경금지

'C > 자료구조와 알고리듬' 카테고리의 다른 글

Chapter 16. Backtracking  (0) 2021.12.12
Chapter 15. BFS  (0) 2021.12.02
Chapter 13. 그래프(Graph)  (0) 2021.11.26
Chapter 12. 힙(Heap)  (0) 2021.11.25
Chapter 11. 이진 탐색 트리(Binary Search Tree)  (0) 2021.11.21

관련글

댓글

티스토리툴바