4일차 - 길찾기

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AV14geLqABQCFAYD&categoryId=AV14geLqABQCFAYD&categoryType=CODE&problemTitle=&orderBy=SUBMIT_COUNT&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=2
이문제 특이했다.
1.
보통 BFS펼쳐갈 때 visit방문할 때 전체 배열만큼(arr) 방문하는데,
문제를 읽으면서 방문했던곳 다시 1->4->3가는거나
1->3 가는거나 같으므로 visit를 그냥 1차원 array로 가져갔다.

2.array를 문제에서 그림에서 줬는데 [2][i]형태로 가져가는게 중요하다

#include <iostream>
#include <string.h>
#include <vector>
#include <queue>

using namespace std;

#define start 0
#define end 99

int arr[2][100] = { 0, };
int visit[100] = { 0, };
int answer;

int  bfs(int istart)
{
    queue<int> qTemp;
    visit[istart] = 1;
    qTemp.push(istart);
    while (!qTemp.empty())
    {
        int iStart = qTemp.front();
        qTemp.pop();
        if (iStart == end)
        {
            return 1;
        }

        for (int i = 0; i < 2; i++)
        {
            int nx = arr[i][iStart];
            if (nx >0 && nx < 100 && visit[nx] == 0)
            {
                visit[nx] = 1;
                qTemp.push(nx);
            }
        }
    }
    return 0;
}

void clear()
{
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 100; j++)
        {
            arr[i][j] = 0;
        }
    }

    for (int j = 0; j < 100; j++)
    {
        visit[j] = 0;
    }
}

int main() {

    int test_case;


    for (test_case = 0; test_case <= 10; test_case++) 
    {
        clear();

        int iCnt(0), iExample(0);
        cin >> iCnt >> iExample;
        for (int i = 0; i < iExample; i++)
        {
            int iTemp1, iTemp2;
            cin >> iTemp1 >> iTemp2;

            if (arr[0][iTemp1] == 0)
            {
                arr[0][iTemp1] = iTemp2;
            }
            else
            {
                arr[1][iTemp1] = iTemp2;
            }
        }

        answer = bfs(start);
      


        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }

    //종료
    return 0;
}