CCL(connected component labeling) 질문

조회수 888회

여기에 코드를 입력하세요이미지

이미지

이미지

스택을 이용한 비재귀함수로 위를 구현하려고 합니다. 8가지 방향으로 위를 0 우상을 1 우를 2 ~ 좌상7 까지 방향성을 8까지로 갖게하고. 000부터 시작해서 연결된 인자들은 같은 번호를 매기려고 합니다.

제가 구현하고 싶은 알고리즘 과정은

  1. (0,0)에서 시작, 방향 0~7 까지 검색중 1인 값이 나오면 push 반복
  2. push한 위치값이 반복된다면 (스택에 003이 존재하고 014, 025 등이 입력된경우)
  3. pop을 하고 pop한 값에서 다시 1을 찾는다. 입력된 방향 +1부터 재검색.
  4. 더이상 push할 값이 없다면(주위에 1이 없다면) pop 실행
  5. pop을 하면서 labeling 시작.
  6. pop할게 없다면 (stack head->next = tail)인 경우, 반복문 종료
  7. 다시 (0,1)부터 시작 ~ (14,14)까지 반복

인데 밑에 과정 즉 pop하는 과정을 구현하기가 힘듭니다. 그 과정을 다시 생각해보았는데 이 과정에서 맵은 [0,0,0,0,0] [0,1,0,1,0] [0,1,1,1,0] [0,0,0,0,0] 으로 생각했습니다. 1-1. pop을 시작한다. 1-1-1. pop한 (h,w,dir)에서 dir+1부터 검사를 다시한다. 1-1-2. 주위에 1이 있다면 다시 푸쉬한다.

  1. pop을 시작한다.(즉 주위에 1이 없다면) (h,w,dir) 스택 003 113 221 134 230

반복될때 134가 안나오고 pop시작 (2,3,0) 일때 (1,3)가 1이라면 2로 변경 1이 아니라면 다시 1찾기 수행한 후 푸쉬 else 아무것도 없다면 다음으로 패스. (1,3,4) 일때 (2,3)가 1이라면 2로 변경 (2,2,1) 일때 (1,3)이 1이라면 2로 변경 1이 아니라면 (2,2)를 2로 바꾸고 다시 1찾기 수행

스택 003 113 226 210

113이 안나오고 pop 시작 (2,1,0) 일때 (1,1)이 1이라면 2로 변경 (2,2,6) 일때 (2,1)이 1이라면 2로 변경 (1,1,3) 일때 (2,2)가 1이아니라면 다시 1찾기 수행. else 통과 (0,0,3) 일때 (1,1)이 1이라면 2로 변경 아니라면 통과.

스택이 비어있다면 다음 과정으로 넘어가라.

 - typedef struct _node { // 노드 생성, 세로 h   가로 w 방향성 dir   
int h;  
int w;  
int dir;    
struct _node *next; 
}node;
node *head, *tail; // 초기화를 위한 정의
int input_map[15][15] = { // 맵 설정
    { 0,0,0,0,0,0,0,0,0,0,0,0,1,1,0 },
    { 0,1,1,1,1,1,1,0,0,0,0,0,1,1,0 },
    { 0,1,0,0,0,0,1,0,0,0,1,1,0,1,0 },
    { 0,1,0,1,1,0,1,0,1,1,1,0,0,1,0 },
    { 0,1,0,0,1,0,1,0,1,0,0,0,0,1,0 },
    { 0,1,1,0,1,0,1,0,1,0,0,1,0,1,0 },
    { 0,0,0,1,1,0,1,0,1,0,1,1,0,1,0 },
    { 0,1,0,1,1,0,1,0,1,0,1,0,0,1,0 },
    { 0,1,0,0,0,0,0,0,1,0,1,0,0,1,0 },
    { 0,1,0,0,0,0,0,1,1,0,1,0,0,1,0 },
    { 0,1,1,1,1,1,0,1,0,0,1,1,0,1,0 },
    { 0,0,0,0,0,1,0,1,0,1,0,0,0,1,0 },
    { 0,1,1,1,0,1,0,1,0,0,0,0,0,1,0 },
    { 0,1,0,0,0,1,0,1,1,1,1,1,1,1,0 },
    { 0,1,1,1,1,1,0,0,0,0,0,0,0,0,0 }
};
void print_map() // 맵을 화면에 출력하는 함수
{
    int i, j;
    for (j = 0; j < 4; j++)
    {
        for (i = 0; i < 5; i++)
        {
            printf("%d", input_map[j][i]);
        }
        printf("\n");
    }
    printf("\n");
}
void init_stack() // 스택 초기화
{
    head = (node *)calloc(1, sizeof(node));
    tail = (node *)calloc(1, sizeof(node));
    head->next = tail;
    tail->next = tail;
}
int is_stack_empty() // 스택 빈경우 체크
{
    if (tail->next == tail)
        return 0;
    else
        return 1;
}

void print_stack() // 스택 출력함수, 중간에 과정이 맞는지 확인을 위해 정의
{
    node *t;
    t = head->next;
    while (t != tail)
    {
        printf("(%d, %d, %d)", t->h, t->w, t->dir);
        t = t->next;
    }
    printf("\n");
}

int repeat(int h, int w, int dir) // 스택에 같은 값이 들어가는지 확인하는 함수
{
    node *t;
    t = head->next;
        while (t != tail && t->h != h && t->w != w && t->dir != dir)
        {
            t = t->next;
        }
    if (t == tail) return 0; // 반복되는게 없다면 0
    else return 1; // 반복되는게 존재한다면 1
}

int push(int y, int x, int dir) // 스택에 push
{
    node *t;
    if ((t = (node*)malloc(sizeof(node))) == NULL)
    {
        printf("Out of memory! \n");
        return -1;
    }
    t->h = y;
    t->w = x;
    t->dir = dir;
    t->next = head->next;
    head->next = t;

    print_stack();
    return 1;
}

node pop() // !!!!!!!!!!!!!!!!!!!!!질문!!!!!!!!!!!!!!!!!!!!!!!!!!!!

{
    node *t;
    int a, b, c;

    t = head->next;
    a = t->h;
    b = t->w;
    c = t->dir;

    head->next = t->next;

    print_map();
    return *t;
}

void neighbor(int h, int w, int dir) // 인접성 검사
{
    int i, j;
    node *t;
    for (h = 0; h < 4; h++) // h와 i를 따로 설정하여 0,0부터 순차적으로 검사
    {
        i = 0;
        i++;
        for (w = 0; w < 5; w++) // 위와 동일
        {
            j = 0;
            j++;
            for (dir = 0; dir < 8; dir++) // 방향성 설정
            {
                if ((dir = UP) && (input_map[h - 1][w] == 1)) // 위방향의 값이 1인경우
                {
                    if (repeat(h, w, dir) == 0) // 반복되지 않는다면
                    {
                        push(h, w, dir); // 푸쉬하고 위치 이동
                        h = h - 1;
                        w = w;
                    }
                    else // 반복된다면
                        pop(); // 팝을 하고
                        if(input_map[t->h][t->w] == 1) // 팝한 값이 1이라면
                            input_map[t->h][t->w] = 2; // 2로 변경 labeling 시작
                            // !!!!!!!!!!!!!!!!!!!!!질문!!!!!!!!!!!!!!!!!!!!!!!!!!!!
                }
                else if ((dir = RIGHTUP) && (input_map[h - 1][w + 1] == 1))
                {
                    push(h, w, dir);
                    h = h - 1;
                    w = w + 1;
                    dir = 0;
                }
                else if ((dir = RIGHT) && (input_map[h][w + 1] == 1))
                {
                    push(h, w, dir);
                    h = h;
                    w = w + 1;
                    dir = 0;
                }
                else if ((dir = RIGHTDOWN) && (input_map[h + 1][w + 1] == 1))
                {
                    push(h, w, dir);
                    h = h + 1;
                    w = w + 1;
                    dir = 0;
                }
                else if ((dir = DOWN) && (input_map[h + 1][w] == 1))
                {
                    push(h, w, dir);
                    h = h + 1;
                    w = w;
                    dir = 0;
                }
                else if ((dir = LEFTDOWN) && (input_map[h + 1][w - 1] == 1))
                {
                    push(h, w, dir);
                    h = h + 1;
                    w = w - 1;
                    dir = 0;
                }
                else if ((dir = LEFT) && (input_map[h][w - 1] == 1))
                {
                    push(h, w, dir);
                    h = h;
                    w = w - 1;
                    dir = 0;
                }
                else if ((dir = LEFTUP) && (input_map[h - 1][w - 1] == 1))
                {
                    push(h, w, dir);
                    h = h - 1;
                    w = w - 1;
                    dir = 0;
                }
                else
                {
                    while (!is_stack_empty())
                        pop();
                }


            }
        }
    }
}

void map_make() // 레이블 만드는 함수
{
    int i, j;
    for (j = 0; j < 4; j++)
    {
        for (i = 0; i < 5; i++)
        {
            if (input_map[j][i] == 1) printf("1");
            else printf("0");
        }
        printf("\n");
    }
    printf("\n");
}

void main()
{
    init_stack();
    map_make();
    neighbor(0, 0, 0);
    print_map();
}
  • (•́ ✖ •̀)
    알 수 없는 사용자
  • 그래서 질문이 무엇인가요? 정영훈 2017.4.30 18:40
  • 운영정책에 맞지 않는 글(과제 등에 대한 질문)로 숨김처리 되었습니다. 알 수 없는 사용자 2017.5.1 14:26

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)