[SW Expert Academy] 길찾기

길찾기

SW Expert Academy는 문제 복제가 금지되어 있기 때문에 링크로 대체하겠습니다.

어떻게 풀까?

대표적인 DFS / BFS 문제입니다.

저 같은 경우는 그냥 시작점에서 큐를 돌려서 BFS를 이용해서 풀었습니다!

0번 노드에서 시작해서 0번 노드에서 이어지는 노드들을 모두 큐에 넣은 후에 방문 했다는 것을 체크해 둡니다.

만약, 99번 노드가 나온다면 바로 연결되어있다는 것으로 끝내주면 됩니다.

하지만 큐가 빌 때까지 99번 노드를 찾을 수 없다면, 시작 노드에서 끝 노드로 갈 수 없다는 것이 될 것입니다!

문제를 하나 풀어보겠습니다.

큐에 시작점인 0을 넣고, 0번을 방문 했다고 체크 합니다.

큐의 가장 위에 있는 0번 노드가 시작 노드가 됩니다.

0번 노드가 가리키는 1번과 2번 노드를 큐에 넣습니다.

큐의 가장 앞에있는 1번 노드가 현재 노드가 됩니다. 1번 노드가 가리키는 4번 노드와 3번 노드를 큐에 넣습니다.

큐의 가장 앞에있는 2번 노드가 현재 노드가 됩니다.

2번 노드가 가리키는 5번 노드와 9번 노드를 큐에 넣습니다.

큐의 가장 앞에있는 3번 노드가 현재 노드가 됩니다.

3번 노드가 가리키는 7번 노드를 큐에 넣습니다.

큐의 가장 앞에있는 5번 노드가 현재 노드가 됩니다.

5번 노드가 가리키는 6번과 7번 노드를 큐에 넣으려고 했지만, 7번은 이미 방문한 적이 있기 때문에 넣을 필요가 없습니다.

큐의 가장 앞에있는 9번 노드가 현재 노드가 됩니다. 9가 가리키는 8번 노드도 이미 방문한 적이 있기 때문에 큐에 넣을 필요가 없습니다.

큐의 가장 앞에 있는 7번 노드가 현재 노드가 됩니다.

7번이 가리키는 99번 노드가 도착점이므로 결과 값은 1이 됩니다!

코드

#pragma once
#include<cstdio>
#include<cstring>
 
//adj[A][2] : A 노드와 인접한 노드의 번호입니다.
//인접한 노드가 최대 2개라 했기 때문에 2개의 공간만 만듭니다.
 
//alen[A] : A 노드와 인접한 노드의 개수 입니다.
//인접한 노드가 최대 2개이기 때문에 alen에는 0, 1, 2 세개의 값 중 하나의 값을 가집니다.
 
//visit : 방문했는지 체크합니다.
//테스트 케이스 번호를 넣어놓으면, visit 배열을 테스트 케이스마다 초기화할 필요가 없어집니다.
int queue[200], adj[100][2], visit[100] = { 0 }, alen[100] = { 0 };
int fr, re;
 
int main()
{
    for (int tc = 1; tc <= 10; tc++)
    {
        int tn, n;
 
        memset(alen, 0, sizeof(alen));
 
        scanf("%d %d\n", &tn, &n);
 
        while (n--)
        {
            int from, to;
            scanf("%d %d \n", &from, &to);
            adj[from][alen[from]++] = to;
        }
 
        re = fr = 0;
 
        //큐에 노드 0번(시작점)을 넣습니다.
        queue[re++] = 0;
        visit[0] = tc;
 
        bool isEnd = false;
        
        //큐가 빌때까지 실행합니다.
        //큐가 비면 0값이 됩니다.
        while (re != fr)
        {
            int now = queue[fr++];
 
            //도착할 수 있습니다!
            if (now == 99)
            {
                isEnd = true;
                break;
            }
 
            for (int i = 0; i < alen[now]; i++)
            {
                int next = adj[now][i];
 
                //이미 방문했으면 큐에 넣을 필요가 없습니다.
                if (visit[next] == tc) continue;
                visit[next] = tc;
 
                // 다음 노드를 넣습니다.
                queue[re++] = next;
            }
        }
 
        printf("#%d %d\n", tc, isEnd);
    }
    return 0;
}

여담

시간 복잡도는 얼마나 될까요?

최악의 경우 모든 노드와 간선을 검사해야하기 때문에 O(V + E)가 될 것입니다!

이 문제의 경우에는 간선의 경우도 최대 2 * V 를 넘지 않기 때문에, 결과적으로는 O(V)가 될 것입니다.