백준 5213번 _ 과외맨

www.acmicpc.net/problem/5213

5213번: 과외맨

---

코드

//visit배열을 500*500 + 1로 잡으니까 통과되었습니다..ㅎ
//사소한 실수로 거의 2시간을 날렸네요.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

class Tile
{
public:
    int sy;
    int sx;
    int ey;
    int ex;
    Tile(){}
    Tile(int sy_in, int sx_in, int ey_in, int ex_in) : sy(sy_in), sx(sx_in), ey(ey_in), ex(ex_in) {}
};

class BfsData {
public:
    int y;
    int x;
    vector<int>visit;
    BfsData(){}
    BfsData(int y_in, int x_in, vector<int>visit_in)
        : y(y_in), x(x_in), visit(visit_in){}
};

int N;
vector<Tile> tiles;
int Tileboard[500][1000];
int board[500][1000];
int dy[6] = { -1, 0, 1, 1, 0, -1 };
int dx[6] = { 1, 2, 1, -1, -2, -1 };

bool IsOdd(int i)
{
    if (i % 2 == 0)
        return false;
    return true;
}

void printboard()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N * 2; j++)
        {
            cout << board[i][j] << ' ';
        }
        cout << '\n';
    }
}

void printTileboard()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N * 2; j++)
        {
            cout << Tileboard[i][j] << ' ';
        }
        cout << '\n';
    }
}

void Input()
{
    cin >> N;

    int tileNumber = 1;
    for (int i = 0; i < N; i++)
    {
        //짝수시
        if (IsOdd(i) == false)
        {
            for (int j = 0; j < N; j++)
            {
                int a, b;
                cin >> a >> b;
                board[i][j * 2] = a;
                board[i][j * 2 + 1] = b;
                Tileboard[i][j * 2] = tileNumber;
                Tile tile(i, j * 2, i, j * 2 + 1);
                tiles.push_back(tile);
                tileNumber++;
            }
        }
        //홀수시
        else
        {
            for (int j = 0; j < N-1; j++)
            {
                int a, b;
                cin >> a >> b;
                board[i][j * 2 + 1] = a;
                board[i][j * 2 + 2] = b;
                Tileboard[i][j * 2 + 1] = tileNumber;
                Tile tile(i, j * 2 + 1, i, j * 2 + 2);
                tiles.push_back(tile);
                tileNumber++;
            }
        }
    }
}

bool IsVisit(const vector<int>& visit, int target)
{
    for (int i = visit.size() - 1; i >= 0; i--)
        if (visit[i] == target)
            return true;

    return false;
}

bool IsInRange(int y, int x)
{
    if (y >= 0 && y < N && x >= 0 && x < 2 * N)
        return true;
    return false;
}

bool IsGoPossible(int myTileNum, int targetTileNum, int dir)
{
    Tile mine = tiles[myTileNum - 1];
    Tile target = tiles[targetTileNum - 1];

    if (dir == 0 || dir == 1 || dir == 2)
    {
        if (board[mine.ey][mine.ex] == board[target.sy][target.sx])
            return true;
        return false;
    }
    else
    {
        if (board[mine.sy][mine.sx] == board[target.ey][target.ex])
            return true;
        return false;
    }
}

bool isVisit[250001];
void bfs()
{
    vector<int > answerVisit;
    int temp = 0;

    BfsData bfsDataInit(0, 0, vector<int>(0));
    queue<BfsData> que;
    que.push(bfsDataInit);

    while (!que.empty())
    {
        int y = que.front().y;
        int x = que.front().x;
        auto visit = que.front().visit;
        que.pop();

        //간곳이면
        if (isVisit[Tileboard[y][x]] == true)
            continue;
        isVisit[Tileboard[y][x]] = true;
        visit.push_back(Tileboard[y][x]);

        //만약에 끝타일에 도착했으면 
        if (Tileboard[y][x] == tiles.size())
        {
            answerVisit = visit;
            break;
        }
        //끝타일에 못갈 경우도 있으니 가장 높은 타일을 가진 아이를 계속 갱신해줘야함
        else if (temp < Tileboard[y][x])
        {
            temp = Tileboard[y][x];
            answerVisit = visit;
        }

        //다음가ㅓㄹ수있는지 찾기
        for (int dir = 0; dir < 6; dir++)
        {
            int ny = y + dy[dir];
            int nx = x + dx[dir];

            //범위가 넘었느ㅜㄴ가?
            if (IsInRange(ny, nx) == false || Tileboard[ny][nx] == 0)
                continue;

            //target 타일로 갈수 있는지 없는지 확인
            if (IsGoPossible(Tileboard[y][x], Tileboard[ny][nx], dir) == false)
                continue;

            BfsData bfsData(ny, nx, visit);
            que.push(bfsData);
        }
    }
    cout << answerVisit.size() << '\n';
    for (auto ele : answerVisit)
        cout << ele << ' ';

}

int main()
{
    Input();
    bfs();

    return 0;
}