1219. [S/W 문제해결 기본] 4일차 - 길찾기

이건 두 개의 방법으로 풀었다.

1. 인접 행렬을 이용한 BFS.

2. 문제에서 주어진 가이드라인을 통해서.

1번 같은 경우 인접행렬로 풀 때 2와 3이 연결되어 있으면

arr[2][3]=arr[3][2]=1;

이런 식으로 연결이 됨을 표시해줬는데..여기는 일방 통행이라는 전제 때문인지

arr[2][3]=1;

요렇게만 해줘야된다..ㅎㅎ

1.

#include <stdio.h>
#include <string.h>
int Q[99 * 99];
int Map[111][111], visit[111];
int Q_back, Q_front, T, Len, Flag;
 
int main()
{
    for (int i = 0; i < 10; i++)
    {
        memset(Map, 0, sizeof(Map));
        memset(visit, 0, sizeof(visit));
        memset(Q, 0, sizeof(Q));
        Q_back = -1; Q_front = -1; Flag = 0;
        
        scanf("%d %d", &T, &Len);
 
        for (int j = 0; j < Len; j++)
        {
            int a, b;
            scanf("%d %d", &a, &b);
 
            Map[a][b] = 1;
 
            if (a == 0)
            {
                Q[++Q_back] = b;
            }
        }
        
        while (Q_back != Q_front)
        {
            int X = Q[++Q_front];
 
            if (X == 99)
            {
                Flag = 1;
                break;
            }
 
            for (int j = 0; j <= 99; j++)
            {
                if (Map[X][j] == 1 && visit[j] == 0)
                {
                    Q[++Q_back] = j;
                    visit[j] = 1;
                }
            }
        }
        printf("#%d %d\n", T, Flag);
    }
 
    return 0;
}

2. visit체크 안 함 - 테케가 빈약하여 통과..최악의 경우는 안 댐

#include <stdio.h>
#include <string.h>
int Q[99 * 99 * 99];
int Map1[111], Map2[111], visit[111];
int Q_back, Q_front, T, Len, Flag;
 
int main()
{
    for (int i = 0; i < 10; i++)
    {
        memset(Map1, 0, sizeof(Map1));
        memset(Map2, 0, sizeof(Map2));
        memset(visit, 0, sizeof(visit));
        memset(Q, 0, sizeof(Q));
        Q_back = -1; Q_front = -1; Flag = 0;
        
        scanf("%d %d", &T, &Len);
 
        for (int j = 0; j < Len; j++)
        {
            int a, b;
            scanf("%d %d", &a, &b);
 
            if (a == 0)
            {
                Q[++Q_back] = b;
            }
            
            if (Map1[a] == 0)
            {
                Map1[a] = b;
            }
            else if (Map1[a] != 0)
            {
                Map2[a] = b;
            }
        }
        
        while (Q_back != Q_front)
        {
            int X = Q[++Q_front];
 
            if (X == 99)
            {
                Flag = 1;
                break;
            }
            if (Map1[X] != 0)
            {
                Q[++Q_back] = Map1[X];
            }
            if (Map2[X] != 0)
            {
                Q[++Q_back] = Map2[X];
            }
 
        }
        printf("#%d %d\n", T, Flag);
    }
 
    return 0;
}

2. 비짓체크 함

#include <stdio.h>
#include <string.h>
int Q[99];
int Map1[111], Map2[111], visit[111];
int Q_back, Q_front, T, Len, Flag;
 
int main()
{
    for (int i = 0; i < 10; i++)
    {
        memset(Map1, 0, sizeof(Map1));
        memset(Map2, 0, sizeof(Map2));
        memset(visit, 0, sizeof(visit));
        memset(Q, 0, sizeof(Q));
        Q_back = -1; Q_front = -1; Flag = 0;
         
        scanf("%d %d", &T, &Len);
 
        for (int j = 0; j < Len; j++)
        {
            int a, b;
            scanf("%d %d", &a, &b);
 
            if (a == 0)
            {
                visit[0] = 1;
                Q[++Q_back] = b;
            }
             
            if (Map1[a] == 0)
            {
                Map1[a] = b;
            }
            else if (Map1[a] != 0)
            {
                Map2[a] = b;
            }
        }
         
        while (Q_back != Q_front)
        {
            int X = Q[++Q_front];
 
            if (X == 99)
            {
                Flag = 1;
                break;
            }
 
            if (visit[X])
                continue;
 
            if (Map1[X] != 0)
            {
                visit[X] = 1;
                Q[++Q_back] = Map1[X];
            }
 
            if (Map2[X] != 0)
            {
                visit[X] = 1;
                Q[++Q_back] = Map2[X];
            }
 
        }
        printf("#%d %d\n", T, Flag);
    }
 
    return 0;
}