Baekjoon 5213번 과외맨

문제

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

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int n, maxi = 1;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
vector<int> ans, before;
vector<vector<int>> visited;
vector<vector<pair<int, int>>> tile; // tile number, digit

void bfs(){
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0)); 
    q.push(make_pair(0, 1)); 
    visited[0][0] = 1;
    visited[0][1] = 1;
    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int ny = y+dy[i];
            int nx = x+dx[i];
            if(0 <= ny && ny < n && 0 <= nx && nx < 2*n && !visited[ny][nx] && tile[ny][nx].second){
                if(tile[y][x].second == tile[ny][nx].second){
                    q.push(make_pair(ny, nx));
                    visited[ny][nx] = 1;
                    for(int j = 2; j < 4; j++){
                        int ly = ny+dy[j];
                        int lx = nx+dx[j];
                        if(0 <= ly && ly < n && 0 <= lx && lx < 2*n && !visited[ly][lx] && tile[ly][lx].second){
                            if(tile[ny][nx].first == tile[ly][lx].first){
                                q.push(make_pair(ly, lx));
                                visited[ly][lx] = 1;
                            }
                        }
                    }
                    before[tile[ny][nx].first] = tile[y][x].first;
                    maxi = max(maxi, tile[ny][nx].first);
                }
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    before.resize(n*n+1, 0);
    visited.resize(n, vector<int>(2*n, 0));
    tile.resize(n, vector<pair<int, int>>(2*n, make_pair(0, 0)));
    int a, b;
    int y = 0, x = 0;
    for(int i = 1; i <= n*n-n/2; i++){
        cin >> a >> b;
        if(y%2 == 0){ // 홀수번째 줄
            if(x == 2*n){
                x = 1;
                y++;
            }
            tile[y][x].first = i;
            tile[y][x].second = a;
            x++;
            tile[y][x].first = i;
            tile[y][x].second = b;
            x++;
        }
        else{ // 짝수번째 줄
            if(x == 2*n-1){
                x = 0;
                y++;
            }
            tile[y][x].first = i;
            tile[y][x].second = a;
            x++;
            tile[y][x].first = i;
            tile[y][x].second = b;
            x++;
        }
    }
    bfs();
    ans.push_back(maxi);
    while(before[maxi]){
        ans.push_back(before[maxi]);
        maxi = before[maxi];
    }
    reverse(all(ans));
    cout << ans.size() << "\n";
    for(auto& i : ans) cout << i << " ";
    return 0;
}

많이 까다로웠던 만큼 배울점도 많았던 문제였다.

1. 최단 경로를 큐에 저장하며 bfs 를 진행하면 메모리초과가 난다.

타일의 번호와 인덱스가 일치하는 1차원 배열 before 에, 새로운 타일에 도착할 때 마다 어느 타일로부터 왔는지를 기록한다. 동시에 도달한 타일 번호의 최대값 maxi 를 저장해두고 maxi 로 부터 지나온 경로를 역추적해야 한다.

2. 한 타일의 두 조각을 동시에 큐에 집어 넣어야 재대로 된 결과를 얻을 수 있다.

같은 타일의 두 조각이 다른 순서로 큐에 들어가게 되면 다음과 같은 반례가 생긴다.

3. n이 1일 경우 bfs 가 한번도 진행되지 않는다는 점을 고려해, maxi 와 before 배열의 크기를 신경써서 초기화해 주어야 한다.

int maxi = 1;
vector<int> before(n*n+1, 0);