글 읽기 - [C언어] 이분 그래프 문제 도와주시면 정말 감사하겠습니다

DryType 7년 전 0

런타임 에러가 자꾸 나는데 메모리 문제일까요??

calloc하는 부분이 있는데 free를 안해줘서 그런가 싶기도 하고...

근데 제가 작성한 부분에서 어떻게 free를 해줘야할지 모르겠네요 ㅠㅠ

어떤 문제인지 가르쳐주세요 고수님들!

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

int map[20001];//색깔 저장할 배열
int check[20001];//이미 bfs로 검색한 노드 1로 저장
int queue[200002];//
typedef struct Line
{
	struct Line *next;
	int to;
}_l;

struct MyStruct
{
	_l *l;
}m[20001];

int N, K;
int q = 0;
int _q = 0;

const char answer[2][5] = { "YES", "NO" };

void push(int i, int color)
{
	queue[q] = i;
	map[i] = color*-1;
	q++;
}

int pop()
{
	int v;

	v = queue[_q];
	_q++;

	return v;
}
int bfs(int i)
{
	if (check[i] == 1) return 0;
	if (m[i].l == NULL) return 0;
	
	if (map[m[i].l->to] == 0) push(i, -1);
	else push(i, map[m[i].l->to]);
	
	int from;
	int result = 0;
	_l *p;

	while (1)
	{
		from = pop();
		p = m[from].l;

		if (p != NULL)
		{
			if (map[p->to] == map[from])//양 꼭지점의 색이 같다면 NO
			{
				result = 1;
				break;
			}

			while (p)
			{
				if (map[p->to] == 0)//반대 꼭지점이 색이 칠해져있지 않을때 push함
				{
					push(p->to, map[from]);
				}
				else if (map[p->to] == map[from])//양 꼭지점의 색이 같다면 NO
				{
					q = _q;
					break;
				}
				p = p->next;
			}
		}
		check[from] = 1;//bfs끝냈다고 체크
		if (q == _q) break;
	}

	return result;	
}

int main()
{
	freopen("input.txt", "r", stdin);
	setbuf(stdout, NULL);

	int T;
	scanf("%d", &T);
	for (int test = 1; test <= T; test++)
	{
		scanf("%d%d", &N, &K);

		int result = 0;
		int front, back;
		_l *h;

		q = _q = 0;

		memset(check, 0, sizeof(int) * 20001);
		memset(map, 0, sizeof(int) * 20001);
		memset(m, 0, sizeof(_l)*K);
		memset(queue, 0, sizeof(int) * 200002);

		for (int i = 0; i < K; i++)
		{
			scanf("%d%d", &front, &back);
			h = (_l*)calloc(1, sizeof(_l));
			h->to = back;

			if (m[front].l == 0)//처음나온 출발 노드인경우
				m[front].l = h;
			else
			{
				h->next = m[front].l;
				m[front].l = h;
			}
		}

		for (int i = 1; i <= N; i++)
		{
			result = bfs(i);
			if (result) break;
		}

		printf("%s\n", answer[result]);

	}
		
	return 0;
}

zlzmsrhak 7년 전 0

m 초기화가 간선 개수만 되어있어서 정점 개수가 더 많은 경우 초기화에 문제가 생겨 런타임 에러가 나는 것 같습니다.

DryType 7년 전 0

댓글 감사합니다! 말씀대로 그게 문제인것 같아서 바로 수정했는데 여전히 런타임 에러가 나네요 ㅠㅠ

zlzmsrhak 7년 전 1

저는 이렇게 고쳤는데 WA가 납니다.

#include <stdio.h>
#include <memory.h>
#include <stdlib.h>
 
int map[20001];//색깔 저장할 배열
int check[20001];//이미 bfs로 검색한 노드 1로 저장
int queue[200002];//
typedef struct Line
{
    struct Line *next;
    int to;
}_l;
 
struct MyStruct
{
    _l *l;
}m[20001];
 
int N, K;
int q = 0;
int _q = 0;
 
const char answer[2][5] = { "YES", "NO" };
 
void push(int i, int color)
{
    queue[q] = i;
    map[i] = color*-1;
    q++;
}
 
int pop()
{
    int v;
 
    v = queue[_q];
    _q++;
 
    return v;
}
int bfs(int i)
{
    if (check[i] == 1) return 0;
    if (m[i].l == NULL) return 0;
     
    if (map[m[i].l->to] == 0) push(i, -1);
    else push(i, map[m[i].l->to]);
     
    int from;
    int result = 0;
    _l *p;
 
    while (1)
    {
        from = pop();
        p = m[from].l;
 
        if (p != NULL)
        {
            if (map[p->to] == map[from])//양 꼭지점의 색이 같다면 NO
            {
                result = 1;
                break;
            }
 
            while (p)
            {
                if (map[p->to] == 0)//반대 꼭지점이 색이 칠해져있지 않을때 push함
                {
                    push(p->to, map[from]);
                }
                else if (map[p->to] == map[from])//양 꼭지점의 색이 같다면 NO
                {
                    q = _q;
                    break;
                }
                p = p->next;
            }
        }
        check[from] = 1;//bfs끝냈다고 체크
        if (q == _q) break;
    }
 
    return result;  
}
 
int main()
{
//    freopen("input.txt", "r", stdin);
    setbuf(stdout, NULL);
 
    int T;
    scanf("%d", &T);
    for (int test = 1; test <= T; test++)
    {
        scanf("%d%d", &N, &K);
 
        int result = 0;
        int front, back;
        _l *h;
 
        q = _q = 0;
 
        memset(check, 0, sizeof(int) * 20001);
        memset(map, 0, sizeof(int) * 20001);
        memset(m, 0, sizeof(m));
        memset(queue, 0, sizeof(int) * 200002);
 
        for (int i = 0; i < K; i++)
        {
            scanf("%d%d", &front, &back);
            h = (_l*)calloc(1, sizeof(_l));
            h->to = back;
 
            if (m[front].l == 0)//처음나온 출발 노드인경우
                m[front].l = h;
            else
            {
                h->next = m[front].l;
                m[front].l = h;
            }
        }
 
        for (int i = 1; i <= N; i++)
        {
            result = bfs(i);
            if (result) break;
        }
 
        printf("%s\n", answer[result]);
 
    }
         
    return 0;
}

DryType 7년 전 0

감사합니다! 런타임에러 해결됐어요
어디서 오답난건지 더 고민해봐야겠어요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C언어] 이분 그래프 문제 도와주시면 정말 감사하겠습니다

DryType 7년 전 0

zlzmsrhak 7년 전 0

DryType 7년 전 0

zlzmsrhak 7년 전 1

DryType 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말