[백준] 5213 - 과외맨

BFS + 그래프를 이용하여 해결 가능

다시 풀기 싫은 문제...

다른방법이 있을지는 모르겠지만 개인적으로는 stl을 사용하여 Queue를 사용하면 못풀 것 같다는 생각이 드는 문제

배열을 2칸을 묶어서 1칸으로 쓰는 것도 중요하다

1. 입력을 받고, 배열 2칸을 1칸으로 만들어 문제와 똑같은 형태로 각 칸에 번호를 매긴다

2. 각 정점에서 문제 조건에 맞는 갈 수 있는 방향을 그래프로 만들어 준다.

3. 이 그래프를 시작으로 BFS탐색 시작!

4. 문제의 조건 중 '도착할 수 없다면 가장 큰 위치로 이동한다'이 조건을 위해 번호가 크다면 계속 갱신을 시켜주고,

이 경로를 추적하기 위해 큐에 들어가는 정보 중 이전 큐의 위치, 즉 탐색을 하는 위치의 큐넘버를 함께 담아준다

5. 문제의 조건에 맞게 출력!

#include <iostream>
#define MX 510
using namespace std;
 
struct kkk{
    int r, br, n;
}q[MX * 2*MX];
 
int map[MX][2 * MX], mapnum[MX][2 * MX], check[MX * MX], graph[MX * MX][7], dab[MX*MX];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
int N, st, ed, ir, point, pointpos, cnt, sw;
 
void bfs()
{
    st = ed = -1;
    q[++st].r = 1; q[st].br = -1; q[st].n = 1; check[1] = 1;
    while (st != ed)
    {
        ir = q[++ed].r;
        for (int i = 0; i < 6; i++)
        {
            if (check[graph[ir][i]]) continue;
            if (!graph[ir][i]) break;
            q[++st].r = graph[ir][i]; q[st].br = ed; q[st].n = q[ed].n + 1; check[graph[ir][i]] = 1;
            if (point < graph[ir][i])
            {
                point = graph[ir][i]; pointpos = st;
            }
            if (q[st].r == cnt) { sw = 1; break; }
        }
        if (sw) break;
    }
}
 
void way()
{
    int next = -1, pos = 0;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= 2 * N; j++)
        {
            if (!map[i][j]) continue;
            if (pos != mapnum[i][j]) next = -1;
            for (int k = 0; k < 4; k++)
            {
                int nx = j + dx[k];
                int ny = i + dy[k];
                if (nx < 1 || ny < 1 || nx > 2 * N || ny > N) continue;
                if (mapnum[ny][nx] == mapnum[i][j]) continue;
                if (map[ny][nx] != map[i][j]) continue;
                graph[mapnum[i][j]][++next] = mapnum[ny][nx];
            }
            pos = mapnum[i][j];
        }
    }
}
 
void find(int n)
{
    int k = -1;
    while (n >= 0)
    {
        dab[++k] = q[n].r;
        n = q[n].br;
    }
}
 
int main(void)
{
    cin >> N;
 
    for (int i = 1; i <= N; i++)
    {
        if (i % 2)
        {
            for (int j = 1; j <= 2 * N; j += 2)
            {
                cin >> map[i][j] >> map[i][j + 1];
                mapnum[i][j] = ++cnt; mapnum[i][j + 1] = cnt;
            }
        }
        else
        {
            for (int j = 2; j <= 2 * (N - 1); j += 2)
            {
                cin >> map[i][j] >> map[i][j + 1];
                mapnum[i][j] = ++cnt; mapnum[i][j + 1] = cnt;
            }
        }
    }
    way();
    bfs();
    if (sw)
    {
        int k = q[st].n;
        cout << k << endl;
        find(st);
        for (int i = k - 1; i >= 0; i--)
            cout << dab[i] << " ";
        cout << endl;
    }
    else
    {
        int k = q[pointpos].n;
        cout << k << endl;
        find(pointpos);
        for (int i = k - 1; i >= 0; i--)
            cout << dab[i] << " ";
        cout << endl;
    }
    return 0;
}