[백준] 5213번 과외맨

5213 과외맨

문제) https://www.acmicpc.net/problem/5213

풀이)

어려운 문제는 아니였는데 몇가지 사항을 간과해 계속 틀렸던 문제이다.

한 번 꼬이기 시작하니깐 문제 조건들을 자세히 읽지 못했다.

과정은 이러하다.

1. 타일들을 N * (N*2) 배열에 둔다고 생각하자. //map[N][N*2]

   입력 예시로 보면 (N=5)

   

2. 배열의 각 칸마다 현재 칸의 값과 이 칸이 어떤 타일에 속하는지, 그리고 이 칸을 방문했었는지 정보를 저장하는 

   구조체를 저장해둔다.

   struct Tile_info{

int val, int number, bool visited; 

   };

  //구조체를 이용해 배열 map선언 => Tile_info map[N][N*2] 

  위의 입력 예시그림을 참고로 보면

  // map[1][1].val = 1, map[1][1].number = 1, map[1][1].visited= false;

  // map[5][10].val = 4, map[5][10].number = 23, map[5][10].visited = false;  

3. 1번 타일부터 마지막 타일까지 탐색을 시작한다.

   (탐색은 BFS로 수행하며, 타일마다 2칸씩 존재하니깐

    새로운 타일을 탐색할때 그 타일의 2칸 모두 queue에 넣어 탐색한다.)

   (경로 저장은 하나의 배열을 따로 선언해준다 // int parent[];

    parent[현재 타일 번호 j] = 이전 타일번호 i; // 이전 타일 i번에서 j번으로 탐색해서 온 것이라는 뜻) 

주의사항

① 경로 저장하는 배열의 크기는 int parent[501]이 아니다. 무슨 말이냐면 타일의 번호가 500번까지 나오는 게 아니다.

    타일의 번호는 N*N - N/2 까지 나올 수 있으므로 더 크게 만들어야한다.

    int parent[501*501]

   처음에 이를 착각하고 크기를 501 사이즈로 둬서 틀렸다.

② 문제 조건 중 "마지막 줄의 마지막 타일로 이동할 수 없는 경우가 존재할 수 있다. 이 경우에는 번호가 가장 큰 타일로 이동하면 된다" 를 지켜야 한다.

    문제가 쓸데없이 너무 길다보니 이 조건을 넘어가버려서 틀렸었다.

    입력 예시에서 마지막 타일의 번호가 23번인데, 23번 타일에 도달못할 경우 22, 21, 20, 19, ... 번호 큰 순으로 차례로 살펴봐서 갈 수 있을 경우 그 경로를 출력해야 한다. 

    새로운 타일을 탐색할 때마다 그 타일의 번호가 지금까지 찾았던 타일의 번호 최대값보다 큰 지 확인 & 바꿈 을 통해 출력할 타일 번호를 알아냈다.

코드)

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
#define INF 999999999
 
int N;
int parent[501*501];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
struct Tile_info {
    int val, number;
    bool visited;//타일 값, 타일번호, 방문여부
};
Tile_info map[501][1002];
 
int bfs() {
    queue <pair<int, int>> qu;
    parent[1] = 1;
    qu.push({1,1});
    qu.push({ 1,2 });
    map[1][1].visited = true;
    map[1][2].visited = true;
    
    int tile = 1;
    while (!qu.empty())
    {
        int y = qu.front().first;
        int x = qu.front().second;
 
        qu.pop();
 
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
 
            if (ny <1 || ny > N || nx < 1 || nx > N * 2) continue;
            if (map[ny][nx].val == 0 || map[ny][nx].visited) continue; // 존재하지 않는 타일 공간 이거나 이미 방문한 타일 pass
 
            if (map[y][x].val == map[ny][nx].val) {//다른 타일이고 같은 숫자를 가질 경우
 
                if (map[ny][nx].number > tile) tile = map[ny][nx].number; //타일 번호 최대값 update
                
                map[ny][nx].visited = true; //방문표시
                parent[map[ny][nx].number] = map[y][x].number; //경로 저장
                
                //탐색한 칸 큐에넣음
                qu.push({ ny,nx });
 
                //나머지 한칸도 큐에 넣음
                if (map[ny][nx - 1].number == map[ny][nx].number) {
                    map[ny][nx - 1].visited = true; //방문표시
                    qu.push({ ny,nx - 1 });
                }
                else if (map[ny][nx + 1].number == map[ny][nx].number) {
                    map[ny][nx + 1].visited = true; //방문표시
                    qu.push({ ny,nx + 1 });
                }
            }
        }
 
    }
    
    return tile;
}
int main() {
    scanf("%d", &N);
    int a, b;
    int num = 1;
    for (int i = 1; i <= N; i++) {
        if (i % 2 == 0) {//짝수 줄
            for (int j = 1; j <= N-1; j++) {
                scanf("%d %d", &a, &b);
                map[i][j * 2].val = a;
                map[i][j * 2 + 1].val = b;
                map[i][j * 2].number = num;
                map[i][j * 2 + 1].number= num;
                num++;
            }
        }
        else { //홀수 줄
            for (int j = 1; j <= N; j++) {
                
                scanf("%d %d", &a, &b);
                map[i][j * 2 - 1].val = a;
                map[i][j * 2].val = b;
                map[i][j * 2-1].number = num;
                map[i][j * 2].number = num;
                num++;
            }
        }
        
    }
 
    vector<int> temp;
    int x = bfs();
    
    for (x; x != parent[x]; x = parent[x]) { // 제일 큰 타일 번호부터 거꾸로 경로 찾음
        temp.push_back(x);
    }
    temp.push_back(1);
    printf("%d\n", temp.size());
 
    for (int i = temp.size() - 1; i >= 0; i--) {
        printf("%d ", temp[i]);
    }
    
    return 0;
}