과외맨

https://www.acmicpc.net/problem/5213

5213번: 과외맨

#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
int n;
struct tile {
    int a, b;
    tile(int a, int b) {
        this->a = a;
        this->b = b;
    }
};
struct Pair {
    int x1, x2, y1, y2, tile;
    Pair(int x1, int y1, int x2, int y2, int tile) {
        this->x1 = x1;
        this->y1 = y1;
        this->x2 = x2;
        this->y2 = y2;
        this->tile = tile;
    }
};
vector<tile> map;
int rmap[501][1000];
int tnum[501][1000];
bool til[249751];
int tist[249751];
int tr[249751];
int maxt = 0;
int ans;
vector<int> road;
bool fin = false;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
void bfs() {
    queue<Pair> q;
    q.push(Pair(0, 0,0,1, tnum[0][0]));
    til[tnum[0][0]] = true;
    tist[tnum[0][0]] = 1;
    tr[1] = -1;
    vector<int> temp;
    while (!q.empty()) {
        int x1 = q.front().x1; int y1 = q.front().y1;
        int x2 = q.front().x2; int y2 = q.front().y2;
        int t = q.front().tile;
        //cout << x1 << ' ' << y1<<' '<<x2<<'  '<<y2<<' '<<t<< '\n';
        q.pop();
        if (maxt < t) maxt = t;
        if (t == n * n - n / 2 ) {
            fin = true;
            continue;//(return 해도됨)
        }
        for (int i = 0; i < 4; i++) {
            int nx = x1 + dx[i]; int ny = y1 + dy[i];
            if (nx < 0 || nx > n || ny < 0 || ny > 2 * n) continue;
            if (rmap[nx][ny] == 0||tnum[nx][ny]==0)continue;
            if (tnum[nx][ny] == t) continue;
            if (til[tnum[nx][ny]] ==false && rmap[x1][y1] == rmap[nx][ny]) {
                til[tnum[nx][ny]] = true;
                tist[tnum[nx][ny]] = tist[t] + 1;
                tr[tnum[nx][ny]] = t;
                if (tnum[nx][ny - 1] == tnum[nx][ny]) {
                    q.push(Pair(nx, ny - 1, nx, ny, tnum[nx][ny]));
                }
                else if (tnum[nx][ny + 1] == tnum[nx][ny]) {
                    q.push(Pair(nx, ny, nx, ny + 1,tnum[nx][ny]));
                }
            }
        }
        for (int i = 0; i < 4; i++) {
            int nx = x2 + dx[i]; int ny = y2 + dy[i];
            if (tnum[nx][ny] == t) continue;
            if (nx < 0 || nx > n || ny < 0 || ny > 2 * n) continue;
            if (rmap[nx][ny] == 0 || tnum[nx][ny] == 0)continue;
            if (til[tnum[nx][ny]] == false && rmap[x2][y2]==rmap[nx][ny]) {
                til[tnum[nx][ny]] = true;
                tr[tnum[nx][ny]] = t;
                if (tnum[nx][ny - 1] == tnum[nx][ny]) {
                    q.push(Pair(nx, ny - 1, nx, ny, tnum[nx][ny]));
                }
                else if (tnum[nx][ny + 1] == tnum[nx][ny]) {
                    q.push(Pair(nx, ny, nx, ny + 1, tnum[nx][ny]));
                }
            }
        }
    }
    return;
}
 
vector<int> goback() {
    vector<int> q;
    q.push_back(maxt);
    int s = maxt;
    while (s != -1) {
        if(tr[s] != -1)
            q.push_back(tr[s]);
        s = tr[s];
    }
    return q;
}
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n * n - n / 2; i++) {
        int a, b;
        cin >> a >> b;
        map.push_back(tile(a, b));
    }
    int idx = 0;
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            int k = 0;
            for (int j = 0; j < n; j++) {
                tnum[i][k] = (idx + j + 1);
                rmap[i][k++] = map[idx + j].a;
                tnum[i][k] = (idx + j + 1);
                rmap[i][k++] = map[idx + j].b;
 
            }
            idx += n;
        }
        else {
            int k = 1;
            for (int j = 0; j < n - 1; j++) {
                tnum[i][k] = (idx + j + 1);
                rmap[i][k++] = map[idx + j].a;
                tnum[i][k] = (idx + j + 1);
                rmap[i][k++] = map[idx + j].b;
            }
            idx += n - 1;
        }
    }
    /*
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2 * n; j++)
            cout << rmap[i][j] << ' ';
        cout << '\n';
    }*/
    bfs();
    road = goback();
    cout << road.size() << '\n';
    for (int i = road.size()-1; i >= 0; i--) {
        cout << road[i] << ' ';
 
    }cout << '\n';
    return 0;
}

과외맨 문제 엄두도 못내다가 이번에 풀었다..

화장실가고 쓸데없는 짓거리만 안했으면 한시간반컷 충분히가능했더문제지만..

너무나 멍청하게도 계속 맵담아두는 크기를 500x500으로해놔서... 틀릴수밖에없었다..

처음에는 경로 잘못가져온줄알았는데...후..

그래도 나름 어려운 BFS가아닐까싶다.