C언어에서 그래프의 사이클 감지 알고리즘: 구현과 사례

그래프는 데이터 구조에서 가장 중요한 개념 중 하나로, 정점과 간선으로 구성됩니다. 특히 그래프에서 사이클(Loop)의 존재 여부를 판단하는 것은 네트워크 설계, 경로 탐색, 소프트웨어 의존성 해결 등 다양한 분야에서 중요합니다. 본 기사에서는 C언어를 활용하여 그래프에서 사이클을 감지하는 방법을 자세히 다루며, 구현 코드를 통해 실무적인 접근법을 제시합니다. 이를 통해 독자는 그래프와 알고리즘의 기초 개념부터 실질적인 활용까지 깊이 있는 이해를 얻을 수 있습니다.

그래프와 사이클의 정의

그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 구성된 데이터 구조로, 정점 간의 관계를 표현합니다. 그래프는 유향 그래프(Directed Graph)와 무향 그래프(Undirected Graph)로 나뉘며, 여러 응용 분야에서 활용됩니다.

사이클의 정의

그래프에서 사이클(Loop)이란 정점에서 시작하여 다시 같은 정점으로 돌아오는 경로를 의미합니다.

무향 그래프의 사이클: 동일한 간선을 반복하지 않고 정점으로 돌아올 수 있는 경로.
유향 그래프의 사이클: 간선 방향을 따라 이동하며 원점으로 돌아오는 경로.

사이클의 중요성

사이클 감지는 다양한 문제 해결에 필수적입니다.

데드락 방지: 운영체제에서 데드락 발생 여부를 탐지.
의존성 분석: 소프트웨어 패키지 설치 시 순환 의존성 제거.
네트워크 설계: 네트워크 루프 제거로 성능 최적화.

활용 사례

컴퓨터 네트워크: 스패닝 트리 알고리즘에서 네트워크 루프 감지.
데이터베이스: 트랜잭션의 순환 의존성 문제 해결.
게임 개발: 그래프 기반 AI 경로 탐색.

이처럼 사이클 감지는 그래프 알고리즘에서 핵심 역할을 하며, 다양한 분야에서 필수적으로 사용됩니다.

사이클 감지 알고리즘 개요

그래프에서 사이클을 감지하기 위해 다양한 알고리즘이 사용됩니다. 대표적인 방법으로 DFS(깊이 우선 탐색)과 유니온-파인드(Union-Find) 알고리즘이 있습니다. 이 두 알고리즘은 그래프의 구조와 특성에 따라 선택적으로 활용됩니다.

DFS를 활용한 사이클 감지

DFS는 그래프를 깊이 탐색하며 방문한 정점을 추적해 사이클을 감지하는 방법입니다.

무향 그래프: 방문한 정점의 부모 정보를 기록해 사이클을 탐지.
유향 그래프: 방문 상태(미방문, 방문 중, 방문 완료)를 추적해 순환 구조를 확인.
DFS 기반의 방법은 구현이 간단하고, 작은 그래프에 효과적입니다.

유니온-파인드를 활용한 사이클 감지

유니온-파인드는 집합 자료구조를 이용해 그래프의 연결성을 관리하는 방식입니다.

각 정점을 개별 집합으로 초기화한 뒤 간선을 처리하며 두 정점을 병합(Union).
동일 집합에 속한 두 정점이 다시 연결되면 사이클이 존재한다고 판단.
이 방법은 특히 무향 그래프에서 효율적이며, 그래프의 크기가 커질수록 성능상의 장점이 있습니다.

알고리즘 선택 기준

그래프 유형: DFS는 유향 그래프에 적합하고, 유니온-파인드는 무향 그래프에서 효과적입니다.
그래프 크기: 작은 그래프에서는 DFS가 간단하고 빠르며, 큰 그래프에서는 유니온-파인드가 더 적합합니다.
구현 복잡도: DFS는 구현이 간단하지만, 유니온-파인드는 성능 최적화에 유리합니다.

이 두 알고리즘을 이해하고 상황에 따라 적절히 선택하면, 그래프에서 사이클 감지를 효율적으로 수행할 수 있습니다.

DFS를 활용한 사이클 감지 구현

DFS(깊이 우선 탐색)는 그래프를 탐색하며 정점 간의 순환 관계를 감지하는 직관적이고 효과적인 방법입니다. C언어를 사용해 무향 그래프에서 사이클을 감지하는 DFS 기반 알고리즘을 구현해 보겠습니다.

알고리즘 설명

방문 추적: 각 정점의 방문 여부를 기록합니다.
재귀 탐색: 현재 정점에서 연결된 정점을 재귀적으로 탐색합니다.
사이클 조건 확인: 이미 방문한 정점이 현재 정점의 부모가 아니라면, 사이클이 존재합니다.

코드 구현

#include <stdio.h>
#include <stdbool.h>

#define MAX_NODES 100

// 그래프 구조 정의
int graph[MAX_NODES][MAX_NODES];
bool visited[MAX_NODES];

// DFS 함수
bool dfs(int node, int parent, int numNodes) {
    visited[node] = true;

    for (int i = 0; i < numNodes; i++) {
        if (graph[node][i]) {  // 연결된 정점이 있는 경우
            if (!visited[i]) {
                if (dfs(i, node, numNodes)) {
                    return true;  // 사이클 발견
                }
            } else if (i != parent) {
                return true;  // 사이클 조건 만족
            }
        }
    }
    return false;
}

int main() {
    int numNodes, numEdges;
    printf("노드 수와 간선 수를 입력하세요: ");
    scanf("%d %d", &numNodes, &numEdges);

    // 그래프 초기화
    for (int i = 0; i < numNodes; i++) {
        for (int j = 0; j < numNodes; j++) {
            graph[i][j] = 0;
        }
        visited[i] = false;
    }

    // 간선 입력
    printf("간선들을 입력하세요 (시작 노드 끝 노드):\n");
    for (int i = 0; i < numEdges; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u][v] = 1;
        graph[v][u] = 1;  // 무향 그래프
    }

    // DFS로 사이클 감지
    bool hasCycle = false;
    for (int i = 0; i < numNodes; i++) {
        if (!visited[i]) {
            if (dfs(i, -1, numNodes)) {
                hasCycle = true;
                break;
            }
        }
    }

    if (hasCycle) {
        printf("그래프에 사이클이 존재합니다.\n");
    } else {
        printf("그래프에 사이클이 없습니다.\n");
    }

    return 0;
}

코드 설명

그래프 데이터 입력: 인접 행렬로 그래프를 표현하며, 간선 정보를 입력받아 초기화합니다.
DFS 탐색: 각 정점을 방문하며 사이클 조건을 확인합니다.
결과 출력: 탐색 결과에 따라 그래프에 사이클 존재 여부를 출력합니다.

적용 예시

입력:

  노드 수와 간선 수를 입력하세요: 4 4  
  간선들을 입력하세요 (시작 노드 끝 노드):  
  0 1  
  1 2  
  2 3  
  3 0

출력:

  그래프에 사이클이 존재합니다.

DFS 기반 구현은 간단하면서도 효과적으로 무향 그래프에서 사이클을 감지할 수 있는 방법입니다.

유니온-파인드를 활용한 사이클 감지 구현

유니온-파인드(Union-Find)는 집합 자료구조를 이용하여 그래프의 연결 상태를 관리하는 효율적인 알고리즘입니다. 이 방법은 특히 무향 그래프에서 사이클을 감지하는 데 적합합니다.

알고리즘 설명

부모 배열 초기화: 각 정점을 독립된 집합으로 설정합니다.
Find 연산: 특정 정점의 대표 노드를 찾습니다. 경로 압축(Path Compression)을 사용해 탐색 시간을 최적화합니다.
Union 연산: 두 정점을 같은 집합으로 병합합니다.
사이클 조건 확인: 두 정점이 이미 같은 집합에 속한다면 사이클이 존재합니다.

코드 구현

#include <stdio.h>

// 최대 노드 수
#define MAX_NODES 100

// 부모 배열
int parent[MAX_NODES];

// Find 연산: 경로 압축을 사용
int find(int node) {
    if (parent[node] == node) {
        return node;
    }
    return parent[node] = find(parent[node]);
}

// Union 연산: 두 집합을 병합
void unionNodes(int node1, int node2) {
    int root1 = find(node1);
    int root2 = find(node2);

    if (root1 != root2) {
        parent[root2] = root1;
    }
}

int main() {
    int numNodes, numEdges;
    printf("노드 수와 간선 수를 입력하세요: ");
    scanf("%d %d", &numNodes, &numEdges);

    // 부모 배열 초기화
    for (int i = 0; i < numNodes; i++) {
        parent[i] = i;
    }

    // 사이클 감지 플래그
    int hasCycle = 0;

    printf("간선들을 입력하세요 (시작 노드 끝 노드):\n");
    for (int i = 0; i < numEdges; i++) {
        int u, v;
        scanf("%d %d", &u, &v);

        // 두 노드의 루트 노드를 확인
        if (find(u) == find(v)) {
            hasCycle = 1;  // 사이클 존재
            break;
        }

        // 두 노드를 병합
        unionNodes(u, v);
    }

    if (hasCycle) {
        printf("그래프에 사이클이 존재합니다.\n");
    } else {
        printf("그래프에 사이클이 없습니다.\n");
    }

    return 0;
}

코드 설명

부모 배열 초기화: 각 정점이 자기 자신을 부모로 갖도록 설정합니다.
Find 함수: 특정 정점의 대표 노드를 재귀적으로 탐색하며 경로 압축을 통해 효율성을 높입니다.
Union 함수: 두 정점을 병합하며 사이클이 없는 연결 상태를 유지합니다.
사이클 감지: 두 정점이 이미 같은 집합에 속한다면, 해당 간선은 사이클을 형성합니다.

적용 예시

입력:

  노드 수와 간선 수를 입력하세요: 4 4  
  간선들을 입력하세요 (시작 노드 끝 노드):  
  0 1  
  1 2  
  2 3  
  3 0

출력:

  그래프에 사이클이 존재합니다.

유니온-파인드의 장점

시간 복잡도: Find 및 Union 연산은 경로 압축과 랭크 최적화를 사용하여 거의 O(1) 시간 복잡도를 가집니다.
큰 그래프에 적합: 수천 개의 정점과 간선을 가진 대규모 그래프에서도 효율적으로 동작합니다.

유니온-파인드를 사용하면 큰 무향 그래프에서 사이클 감지를 효율적으로 수행할 수 있습니다.

유향 그래프에서의 사이클 감지

유향 그래프(Directed Graph)에서 사이클 감지는 무향 그래프와 다릅니다. 유향 그래프는 간선의 방향성을 가지기 때문에 순환 구조를 탐지하기 위해 DFS(깊이 우선 탐색)와 같은 탐색 기반 알고리즘을 활용합니다.

알고리즘 설명

방문 상태 추적: 각 정점에 대해 방문 상태를 기록합니다.

미방문(0): 아직 탐색하지 않은 정점.
방문 중(1): 현재 탐색 경로에 포함된 정점.
방문 완료(2): 탐색이 끝난 정점.

DFS 탐색: 정점을 탐색하며 방문 상태를 업데이트합니다.
사이클 조건 확인: 방문 중인 정점을 다시 방문하면 순환 구조(사이클)가 있다고 판단합니다.

코드 구현

#include <stdio.h>
#include <stdbool.h>

#define MAX_NODES 100

// 그래프와 방문 상태 배열
int graph[MAX_NODES][MAX_NODES];
int visitStatus[MAX_NODES];

// DFS 함수
bool dfs(int node, int numNodes) {
    visitStatus[node] = 1;  // 방문 중 상태로 설정

    for (int i = 0; i < numNodes; i++) {
        if (graph[node][i]) {  // 연결된 정점 탐색
            if (visitStatus[i] == 0) {  // 미방문 상태
                if (dfs(i, numNodes)) {
                    return true;  // 사이클 발견
                }
            } else if (visitStatus[i] == 1) {
                return true;  // 방문 중 상태에서 재방문 = 사이클
            }
        }
    }

    visitStatus[node] = 2;  // 방문 완료 상태로 설정
    return false;
}

int main() {
    int numNodes, numEdges;
    printf("노드 수와 간선 수를 입력하세요: ");
    scanf("%d %d", &numNodes, &numEdges);

    // 그래프 초기화
    for (int i = 0; i < numNodes; i++) {
        for (int j = 0; j < numNodes; j++) {
            graph[i][j] = 0;
        }
        visitStatus[i] = 0;
    }

    // 간선 입력
    printf("간선들을 입력하세요 (시작 노드 끝 노드):\n");
    for (int i = 0; i < numEdges; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u][v] = 1;  // 유향 그래프
    }

    // DFS로 사이클 감지
    bool hasCycle = false;
    for (int i = 0; i < numNodes; i++) {
        if (visitStatus[i] == 0) {
            if (dfs(i, numNodes)) {
                hasCycle = true;
                break;
            }
        }
    }

    if (hasCycle) {
        printf("그래프에 사이클이 존재합니다.\n");
    } else {
        printf("그래프에 사이클이 없습니다.\n");
    }

    return 0;
}

코드 설명

그래프 데이터 입력: 인접 행렬로 유향 그래프를 표현합니다.
DFS 기반 탐색: 방문 상태를 추적하며 순환 구조를 탐지합니다.
결과 출력: 탐색 결과를 기반으로 사이클 존재 여부를 출력합니다.

적용 예시

입력:

  노드 수와 간선 수를 입력하세요: 4 4  
  간선들을 입력하세요 (시작 노드 끝 노드):  
  0 1  
  1 2  
  2 3  
  3 1

출력:

  그래프에 사이클이 존재합니다.

유향 그래프에서 DFS의 장점

효율성: DFS의 시간 복잡도는 O(V + E)로, 유향 그래프의 사이클 감지에 적합합니다.
적용 범위: 유향 그래프뿐만 아니라 DAG(Directed Acyclic Graph) 검증에도 사용됩니다.

유향 그래프에서의 사이클 감지는 다양한 알고리즘적 문제에서 중요한 역할을 하며, DFS는 이를 해결하는 강력한 도구입니다.

그래프 데이터 입력과 변환

그래프를 다루기 위해서는 데이터를 효율적으로 입력받고 적절한 데이터 구조로 변환하는 과정이 중요합니다. C언어에서는 인접 행렬과 인접 리스트가 그래프 표현을 위해 널리 사용됩니다. 이 섹션에서는 입력 데이터를 처리하고 그래프 구조로 변환하는 방법을 소개합니다.

그래프 표현 방식

인접 행렬

정점 간의 연결 관계를 2차원 배열로 표현.
메모리 사용량: O(V²), 정점 수가 적은 밀집 그래프에 적합.

인접 리스트

각 정점과 연결된 정점의 리스트를 저장.
메모리 사용량: O(V + E), 간선 수가 적은 희소 그래프에 적합.

인접 행렬을 활용한 그래프 입력

#include <stdio.h>

#define MAX_NODES 100

void inputAdjMatrix(int graph[MAX_NODES][MAX_NODES], int numNodes, int numEdges) {
    // 초기화
    for (int i = 0; i < numNodes; i++) {
        for (int j = 0; j < numNodes; j++) {
            graph[i][j] = 0;
        }
    }

    // 간선 입력
    printf("간선들을 입력하세요 (시작 노드 끝 노드):\n");
    for (int i = 0; i < numEdges; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u][v] = 1;  // 유향 그래프
        // graph[v][u] = 1;  // 무향 그래프라면 주석 해제
    }
}

인접 리스트를 활용한 그래프 입력

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

#define MAX_NODES 100

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* adjList[MAX_NODES];

void inputAdjList(int numNodes, int numEdges) {
    // 초기화
    for (int i = 0; i < numNodes; i++) {
        adjList[i] = NULL;
    }

    // 간선 입력
    printf("간선들을 입력하세요 (시작 노드 끝 노드):\n");
    for (int i = 0; i < numEdges; i++) {
        int u, v;
        scanf("%d %d", &u, &v);

        // u에서 v로의 간선 추가
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->vertex = v;
        newNode->next = adjList[u];
        adjList[u] = newNode;

        // 무향 그래프라면 다음 코드를 추가
        // newNode = (Node*)malloc(sizeof(Node));
        // newNode->vertex = u;
        // newNode->next = adjList[v];
        // adjList[v] = newNode;
    }
}

데이터 변환 및 선택 기준

인접 행렬
간단하고 정적인 그래프에서 사용.
간선 존재 여부를 O(1) 시간에 확인 가능.
인접 리스트
동적이고 큰 그래프에서 효율적.
메모리를 절약하고 연결된 정점 순회가 빠름.

예제 입력 및 출력

입력:

노드 수와 간선 수를 입력하세요: 4 4  
간선들을 입력하세요 (시작 노드 끝 노드):  
0 1  
1 2  
2 3  
3 0

출력: (인접 행렬)

출력: (인접 리스트)

0 -> 1  
1 -> 2  
2 -> 3  
3 -> 0

결론

그래프 데이터 입력과 변환은 알고리즘 구현의 기초 단계입니다. 그래프의 특성에 따라 적절한 표현 방식을 선택하면 데이터 처리를 더 효율적으로 수행할 수 있습니다.

디버깅과 문제 해결

그래프에서 사이클 감지 알고리즘을 구현할 때 발생할 수 있는 오류를 찾아내고 해결하는 것은 중요합니다. 이 섹션에서는 디버깅 단계에서 발생할 수 있는 일반적인 문제와 그 해결 방법을 다룹니다.

문제 1: 그래프 데이터 입력 오류

문제:
입력 데이터가 올바르게 처리되지 않아 그래프가 올바르게 초기화되지 않음.
해결 방법:

데이터 입력 후 그래프 구조를 출력하여 확인합니다.
인접 행렬의 경우, 배열 상태를 출력합니다.
인접 리스트의 경우, 각 노드와 연결된 정점을 출력합니다.

예제 코드:

void printAdjMatrix(int graph[MAX_NODES][MAX_NODES], int numNodes) {
    for (int i = 0; i < numNodes; i++) {
        for (int j = 0; j < numNodes; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
}

void printAdjList(Node* adjList[MAX_NODES], int numNodes) {
    for (int i = 0; i < numNodes; i++) {
        printf("%d: ", i);
        Node* temp = adjList[i];
        while (temp != NULL) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

문제 2: 무한 루프 발생

문제:
DFS 또는 유니온-파인드 알고리즘에서 무한 루프가 발생.
해결 방법:

DFS에서 방문 상태 배열이 올바르게 업데이트되었는지 확인합니다.
유니온-파인드에서 부모 배열의 초기화와 Find 함수의 경로 압축이 제대로 작동하는지 확인합니다.

유효성 검사 코드:

void checkVisited(bool visited[], int numNodes) {
    for (int i = 0; i < numNodes; i++) {
        printf("Node %d visited: %d\n", i, visited[i]);
    }
}

문제 3: 잘못된 사이클 감지 결과

문제:
사이클이 없는 그래프에서 사이클이 있다고 잘못 판단하거나, 사이클이 있는 그래프에서 감지하지 못함.
해결 방법:

DFS의 재귀 함수에서 부모 노드 체크 조건이 올바른지 확인합니다.
유니온-파인드에서 Find 함수가 각 노드의 루트를 정확히 반환하는지 확인합니다.

디버깅 전략

DFS:
각 재귀 호출에서 현재 정점과 부모 정점을 출력.
방문 상태 배열의 업데이트를 확인.
유니온-파인드:
간선을 처리할 때 두 정점의 루트 노드를 출력.
Union 연산 후 부모 배열 상태를 확인.

예제 코드:

void debugFind(int parent[], int node) {
    printf("Find(%d): Root = %d\n", node, find(node));
}

void debugUnion(int parent[], int node1, int node2) {
    printf("Union(%d, %d)\n", node1, node2);
    unionNodes(node1, node2);
    for (int i = 0; i < MAX_NODES; i++) {
        printf("Parent[%d] = %d\n", i, parent[i]);
    }
}

문제 4: 메모리 누수

문제:
인접 리스트를 사용하는 경우, 동적 할당된 메모리가 해제되지 않아 메모리 누수가 발생.
해결 방법:

프로그램 종료 전에 할당된 메모리를 순차적으로 해제합니다.

예제 코드:

void freeAdjList(Node* adjList[MAX_NODES], int numNodes) {
    for (int i = 0; i < numNodes; i++) {
        Node* temp = adjList[i];
        while (temp != NULL) {
            Node* toFree = temp;
            temp = temp->next;
            free(toFree);
        }
    }
}

문제 5: 성능 저하

문제:
그래프가 큰 경우 DFS나 유니온-파인드가 느리게 동작.
해결 방법:

DFS의 경우, 불필요한 반복 탐색이 없는지 확인.
유니온-파인드에서 경로 압축과 랭크 기반 병합을 최적화.

결론

그래프에서 사이클 감지를 구현하는 동안 발생할 수 있는 문제를 사전에 예방하거나, 발생 시 신속히 해결하면 알고리즘의 신뢰성과 성능을 보장할 수 있습니다. 디버깅 과정을 통해 정확하고 효율적인 구현을 완성할 수 있습니다.

연습 문제

C언어를 활용해 그래프의 사이클 감지를 학습한 내용을 실전에서 연습할 수 있도록 다양한 문제를 제공합니다. 문제를 통해 알고리즘 구현 능력을 강화하고 실질적인 활용 능력을 키워 보세요.

문제 1: 무향 그래프에서 사이클 감지

문제 설명:
노드 수 ( N )과 간선 수 ( E ), 그리고 간선 목록이 주어질 때, DFS를 사용하여 무향 그래프에 사이클이 존재하는지 판단하세요.

입력 예시:

출력 예시:

그래프에 사이클이 존재합니다.

문제 2: 유향 그래프에서 사이클 감지

문제 설명:
노드 수 ( N )과 간선 수 ( E ), 그리고 간선 목록이 주어질 때, DFS를 사용하여 유향 그래프에 사이클이 존재하는지 판단하세요.

입력 예시:

출력 예시:

그래프에 사이클이 존재합니다.

문제 3: 유니온-파인드 기반 사이클 감지

문제 설명:
노드 수 ( N )과 간선 수 ( E ), 그리고 간선 목록이 주어질 때, 유니온-파인드 알고리즘을 사용하여 무향 그래프에서 사이클이 존재하는지 판단하세요.

입력 예시:

출력 예시:

그래프에 사이클이 없습니다.

문제 4: 그래프 표현 방식 전환

문제 설명:
인접 행렬로 주어진 그래프를 인접 리스트로 변환하는 프로그램을 작성하세요.

입력 예시:

출력 예시:

인접 리스트:  
0 -> 1  
1 -> 0 -> 2  
2 -> 1 -> 3  
3 -> 2

문제 5: 다중 사이클 감지

문제 설명:
그래프에서 여러 개의 사이클이 존재하는 경우, 모든 사이클을 탐지하는 프로그램을 작성하세요.

입력 예시:

출력 예시:

사이클 1: 0 -> 1 -> 2 -> 0  
사이클 2: 3 -> 4 -> 5 -> 3

문제 풀이 팁

각 문제에서 코드 구현 전 그래프의 구조와 입력 데이터를 시각화하여 이해도를 높입니다.
디버깅을 통해 방문 상태, 부모 노드, 또는 부모 배열의 상태를 확인합니다.
코드의 재사용성을 높이기 위해 사이클 감지 함수를 모듈화합니다.

결론

이 연습 문제를 통해 그래프 데이터 구조의 핵심 개념과 사이클 감지 알고리즘을 숙달할 수 있습니다. 문제를 해결하며 습득한 내용을 활용하여 더 복잡한 그래프 문제에도 도전해 보세요.

요약

본 기사에서는 C언어를 활용하여 그래프에서 사이클을 감지하는 다양한 알고리즘과 구현 방법을 다뤘습니다. DFS와 유니온-파인드 같은 효율적인 알고리즘의 원리와 코드를 학습하고, 무향 및 유향 그래프에서 사이클을 탐지하는 차이점을 이해했습니다. 또한 디버깅 과정과 문제 해결 방법, 실전 연습 문제를 통해 알고리즘 구현 능력을 향상시킬 수 있도록 구성했습니다. 이를 통해 독자들은 그래프 이론의 기초와 실제 활용 능력을 모두 습득할 수 있을 것입니다.