[백준 5213] 과외맨 (C++)

문제 링크: www.acmicpc.net/problem/5213

5213번: 과외맨

1. 주의할 점

- 타일에 대한 정보를 어떻게 저장하고 불러올 것인가

- 주변 타일을 어떻게 구할 것인가

- 끝까지 도달 못할 경우, 가장 번호가 큰 타일을 목적지로 한다

- 경로를 어떻게 저장할 것인가

 

2. 구현

- Arr[][]배열을 통해 각 타일에 대한 정보를 저장한다

- y와 x 벡터를 통해 각 타일이 2줄을 간격으로 Arr[][] 배열의 어떤 위치에 값을 대입하면 되는지에 대한 정보를 담는다

- 공식을 통해 Arr[][] 배열에 타일에 대한 정보를 담는다

- Dist[] 배열은 해당 타일번호까지의 최단거리를 저장하므로, 초기에 초기화 작업을 거친다

- BFS를 수행하여 1번 타일부터 N*N-N/2 타일까지의 최단거리를 구한다

- 최단거리를 갱신할 경우, Pre[] 배열을 통해 경로를 저장한다

- find_tile_num() 함수를 통해 해당 위치의 타일번호를 반환한다

- rtnXy() 함수를 통해 현 위치에 해당하는 타일번호의 다른 좌표에 대한 정보를 넘긴다

- N*N-N/2부터 1번 타일까지 역순으로 탐색하여 도달할 수 있는 가장 큰 번호의 타일을 찾는다

- 도달할 수 있는 가장 큰 타일 번호에서 부터 역순으로 경로를 구하여 Stack에 넣는다

- Stack의 모든 원소를 출력한다 

#define MAX 987654321
#include <iostream>
#include <queue>
#include <vector>
#include <stack>
using namespace std;
struct info{
    int x,y,val;
};
info tmp;

int arr[500][1000];
int dist[500*500+1];        //해당 타일번호까지의 최단거리
int pre[500*500+1];         //해당 타일번호에 도착하기 직전 타일번호
int num,a,b,term,tx[2],ty[2];
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};

int find_tile_num(int y, int x){
    int cnt = (y/2)*(2*num-1);
    if(y%2==0) cnt+=(x/2+1);
    else cnt+=(num+(x+1)/2);
    return cnt;
}

int rtnXy(int y, int x, int n){
    int lx = x-1;
    int rx = x+1;
    int lnum,rnum;
    if(lx>=0) lnum = find_tile_num(y,lx);
    if(rx<2*num) rnum = find_tile_num(y,rx);
    if(lnum==n) return y*2*num+lx;
    else return y*2*num+rx;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>num;
    int row=0;
    vector<int> y,x;
    for(int i=0;i<num;i++){
        y.push_back(0);
        x.push_back(2*i);
    }
    for(int i=0;i<num-1;i++){
        y.push_back(1);
        x.push_back(2*i+1);
    }
    term = (2*num-1);
    
    for(int i=0;i<num*num-num/2;i++){
        cin>>a>>b;
        int cy = 2*(i/term) + y[i%term];
        int cx = x[i%term];
        arr[cy][cx] = a;
        arr[cy][cx+1] = b;
    }
    for(int i=1;i<=num*num;i++)
        dist[i] = MAX;
    queue<info> q;
    pre[1]=1;
    dist[1]=1;
    tmp.x=0;
    tmp.y=0;
    tmp.val=1;
    q.push(tmp);
    while(!q.empty()){
        tx[0] = q.front().x;
        ty[0] = q.front().y;
        int cv = q.front().val;
        q.pop();
        int ct = find_tile_num(ty[0],tx[0]);
        if(dist[ct]<cv) continue;
        
        int temp = rtnXy(ty[0],tx[0],ct);
        ty[1] = temp/(2*num);
        tx[1] = temp%(2*num);
        
        for(int i=0;i<2;i++){
            int cx = tx[i];
            int cy = ty[i];
            for(int j=0;j<4;j++){
                int nx = cx+dx[j];
                int ny = cy+dy[j];
                if(nx>=0 && ny>=0 && nx<2*num && ny<num && arr[ny][nx]==arr[cy][cx]){
                    int tn = find_tile_num(ny,nx);
                    if(dist[tn] > cv+1){
                        dist[tn] = cv+1;
                        pre[tn] = ct;
                        tmp.x=nx;
                        tmp.y=ny;
                        tmp.val = cv+1;
                        q.push(tmp);
                    }
                }
            }
        }
    }
    int idx=0;
    for(int i=num*num-num/2;i>0;i--){
        if(dist[i]!=MAX){
            idx = i;
            break;
        }
    }
    
    stack<int> s;
    s.push(idx);
    while(1){
        idx = s.top();
        if(idx==pre[idx]) break;
        s.push(pre[idx]);
    }
    cout << s.size()<<'\n';
    while(!s.empty()){
        cout<<s.top()<<" ";
        s.pop();
    }
    return 0;
}