[BOJ 5213] 과외맨

#문제

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

#풀이

읽는데 힘들었고(아이언맨에... 닥터후까지 나오는..대서사기...) 굉장히 시간이 많이 걸렸던 문제였습니다.

어디가 틀렸는지 제대로 찾지 못하였다가 결국 반례를 찾게 되었습니다...

구글링을 해보니 저처럼 푸신 분은 거의 없었습니다... 

이걸 좋아해야하는지... 

머리가 나쁜건지... 모르겠습니다... :(

일단, 타일 자체를 받는데 고민을 많이했습니다.

기본 맵과는 다르게 홀수 줄에서는 N열, 짝수 줄에서는 N-1열이기 때문입니다.

저는 홀수줄은 1~2N번째 열을 입력 받았고, 짝수줄은 2~(2N-1)열을 입력 받아 칸마다 값들을 넣었습니다.

또한 두 칸마다 하나의 타일이므로 2개씩 묶어 타일 번호를 지정해 주었습니다.(아래 자세한 그림 참조!)

추가적으로 거리 값도 넣어주었는데, 해당 타일에 접근했었는지 확인을 하는 값입니다.

입력을 받은 후에는 BFS로 갈 수 있는 길을 모두 방문해 주어야 합니다.

이전에도 말했듯이 최소 거리라는 말이 나오게 되면 바로 BFS로 접근 하는 경향이 있어 이번에도 BFS로 풀게 되었습니다.

큐에 넣을때 타일 전부 즉, [1,1], [1,2]를 한 셋트로 넣어주어야 합니다. (코드 -> 생성: 12줄 ,저장: 63줄)

이를 못찾고 계속 헤매서... 몇시간동안 본듯하네요...

이렇게 해서 갈 수 있는 길을 모두 넣어 주시고, 돌려주시면 됩니다.

이때! 가는 경로도 조사를 해야합니다.

과연 어떻게 알 수 있을까요?(생각을 해보시고 밑 부분을 드래그하여 답을 확인 해봅시다!)

가는 경로를 알기 위해서 새로운 배열을 만들고 그곳에 왔던 길을 등록하면 편하겠죠? :)

예를 들어 가는 길이 1 -> 3 -> 5 라고 한다면, 5에는 3, 3에는 1을 등록하는 방법입니다.

배열은 [0, 0, 1, 0, 3] 이런 식으로 저장이 되어있을 겁니다.

따라서, 새로운 배열을 만들어 그 곳에 왔던 길을 계속해서 저장합니다.(코드 -> 23,24줄)

그리고 또 하나 놓쳐서는 안되는 조건이 있습니다.

"마지막 줄의 마지막 타일로 이동할 수 없는 경우가 존재할 수 있다. 이 경우에는 번호가 가장 큰 타일로 이동하면 된다." 라는 조건입니다.

즉, 위 그림에서 23번 타일에 도달하지 못하였을 경우 22, 21, 20 조사하여 최대로 멀리 간 경우를 찾아야합니다.

이는 어떻게 찾을 수 있을까요?

바로 큐에 값을 넣었을 때 해당 타일 값이 더 큰지 확인하고 크다면 타일 값을 넣어주면 됩니다. (코드 -> 66줄)

최대 타일부터 이전에 저장하며 왔던 길을 거꾸로 조사하며 출력하면 끝! (코드 -> findPath 함수)

 

#코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
struct Tile{
    int value;
    int num;
    int dist;
};
Tile map[501][501 * 2];
int path[501 * 501];
int N;
 
int dr[4] = {0,0,-1,1};
int dc[4] = {-1,1,0,0};
 
vector<int> way;
int last = 1;
 
void findLoad(){
    queue<pair<int, int>> q;
    q.push({1,1});
    q.push({1,2});
    map[1][1].dist = 1;
    map[1][2].dist = 1;
    while (!q.empty()) {
        int r = q.front().first;
        int c = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];
            int col = nr % 2 == 1 ? N : N-1;
            int start = nr % 2 == 1 ? 1 : 2;
            //범위를 벗어났을때 무시
            if(nr < 1 || nr > N || nc < start || nc > (col*2)+(start-1)) continue;
            
            //이미 방문한 곳 무시
            if(map[nr][nc].dist != 0) continue;
 
            //값이 다르면 움직일 수 없다.
            if(map[nr][nc].value != map[r][c].value) continue;
 
            //타일은 무조건 (왼쪽,오른쪽) 거리가 같아야한다.
            //따라서 왼쪽이 같은 타일일때 오른쪽 거리를 왼쪽에 넣어주고,
            //왼쪽을 큐에 넣어준다.
            bool left = false;
            if(map[nr][nc - 1].num == map[nr][nc].num) left = true;
            map[nr][nc].dist = map[r][c].dist + 1;
            q.push({nr,nc});
            //왼쪽이 같은 타일
            if(left){
                map[nr][nc-1].dist = map[nr][nc].dist;
                q.push({nr,nc-1});
            }
            //오른쪽이 같은 타일
            else{
                map[nr][nc+1].dist = map[nr][nc].dist;
                q.push({nr,nc+1});
            }
            //여태까지 지나온 타일들을 알기 위해 이전 타일을 저장해준다.
            path[map[nr][nc].num] = map[r][c].num;
            
            //번호가 큰 타일 찾기
            if(last < map[nr][nc].num) last = map[nr][nc].num;
        }
    }
}
void findPath(){
    //번호가 제일 큰 타일 찾아서 왔던 길 되돌아 가기
    int temp = last;
    way.push_back(temp);
    while(path[temp] != 0){
        way.push_back(path[temp]);
        temp = path[temp];
    }
    cout << way.size() << endl;
    for(int i = (int)way.size()-1; i >= 0; i--){
        cout << way[i] << " ";
    }
    cout << endl;
}
 
int main(){
    cin >> N;
    int cnt = 1;
    for(int i = 1; i <= N; i++){
        int col = i % 2 == 1 ? N : N-1;
        int start = i % 2 == 1 ? 1 : 2;
        for(int j = start; j <= (col*2)+(start-1); j++){
            cin >> map[i][j].value;
            map[i][j].num = (cnt + 1) / 2;
            cnt++;
        }
    }
    findLoad();
    findPath();
    return 0;
}