1238. [S/W 문제해결 기본] 10일차 - Contact

계속 답이 틀리길래 테케 하나씩 넣고 돌리면 답이 또 맞아서 이건 분명히 초기화 문제야!!!!!!!!!!

라고 생각하고 초기화를 다 검토하고 이상이 없어서 버그 찾느라 엄청난 삽질을 했다.

결론은 역시 초기화 문제...memset에 배열의 크기 부분에 sizeof(0)을 주고 있었다ㅜ,ㅠ

하...2시간이나 걸리다니 미쳤다.

풀이는 간단하다.

 

BFS로 돌린다음 BFS 단계를 체크하는 배열을 별도로 만들어서 제일 마지막 단계에 있는 숫자들 중에서 가장 큰 숫자를 출력하면 된다.

문제 설명에서 보여지는 예제는

2 / 7 15 / 1 4 / 10 8 17

로 단계가 진행되면 별도의 배열로 단계를 체크해주면 된다.

2 / 7 15 / 1 4 / 10 8 17

0 / 1 1  /  2 2 / 3  3  3

요런식!!마지막 3단계의 숫자들만 비교하면 된다.

#include <stdio.h>
#include <string.h>
int map[111][111];
int Q[2][111 * 111], visit[111];
int Q_front, Q_back, max;
 
 
int main()
{
    for (int i = 1; i <= 10; i++)
    {
        int len = -1, start = -1, a = -1, b = 1;
        Q_front = -1;
        Q_back = -1;
        max = -1;
        memset(map, 0, sizeof(map));
        memset(Q, 0, sizeof(Q));
        memset(visit, 0, sizeof(visit));
 
        scanf("%d %d", &len, &start);
 
        visit[start] = 1;
        for (int j = 0; j < len/2; j++)
        {
            scanf("%d %d",&a, &b);
            //printf("%d %d\n", a, b);
            map[a][b] = 1;
            if (start == a)
            {
                Q[0][++Q_back] = b;
                Q[1][Q_back] = 1;
                visit[b] = 1;
            }
        }
        while (Q_front != Q_back)
        {
            int X = Q[0][++Q_front];
 
            for (int j = 1; j <= 100; j++)
            {
                if (map[X][j] == 1 && visit[j] == 0)
                {
                    visit[j] = 1;
                    Q[0][++Q_back] = j;
                    Q[1][Q_back] = Q[1][Q_front] + 1;
                }
            }
        }
 
        int num = Q[1][Q_back];
        int count = 0;
        for (int j = 0; j < 100;j++)
        {
            if (Q[1][Q_back - j] == num)
            {
                count += 1;
            }
            else
                break;
        }
 
        for (int j = 0; j < count; j++)
        {
            if (Q[0][Q_back - j] > max)
            {
                max = Q[0][Q_back - j];
            }
        }
 
        printf("#%d %d\n", i, max);
    }
 
    return 0;
}