BOJ 20158 : 사장님 달려가고 있습니다

• 문제 링크 : boj.kr/20158
• 난이도 : P5
• 태그 : 구현, BFS

20158번: 사장님 달려가고 있습니다

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

struct _data {
    int t;
    int dir; //lrud
    int speed;
    pii pos;
};

int board[101][101];
int _visit[101][101][4][15];
int n;

bool available(_data curr) {
    if(curr.pos.first < 0 || curr.pos.first >= n) return false;
    if(curr.pos.second < 0 || curr.pos.second >= n) return false;
    pii temp = curr.pos;
    int num = board[curr.pos.first][curr.pos.second];
    if(num && num <= curr.t) return false;
    for(int i = 1; i < curr.speed; i++) {
        num = board[temp.first - i*dx[curr.dir]][temp.second - i*dy[curr.dir]];
        if(num && num < curr.t) return false;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> board[i][j];
        }
    }

    queue<_data> _q;
    _data start;
    start.t = 0;
    start.dir = 0;
    start.speed = 0;
    start.pos = {0,0};
    _visit[0][0][0][0] = true;
    _q.push(start);
    while(!_q.empty()) {
        _data curr = _q.front(); _q.pop();
        if(curr.pos.first == n-1 && curr.pos.second == n-1) {
            cout << curr.t;
            return 0;
        }
        _data _next[4] = {};
        for(int i = 0; i < 4; i++) {
            _next[i].t = curr.t+1;
            _next[i].dir = i;
            _next[i].speed = (_next[i].dir == curr.dir ? curr.speed+1 : 1);
            _next[i].pos = {curr.pos.first + dx[i]*_next[i].speed, curr.pos.second + dy[i]*_next[i].speed};
        }
        for(auto u : _next) {;
            if(available(u)) {
                if(_visit[u.pos.first][u.pos.second][u.dir][u.speed]) continue;
                _q.push(u);
                _visit[u.pos.first][u.pos.second][u.dir][u.speed] = true;
            }
        }
    }
    cout << "Fired";
    return 0;
}

---

풀이

구현이 많고, 문제에서 말하는 조건이 명확하지 않은 문제이다.

 

문제의 명확하지 않은 조건부터 파악해보자.

• 가속도가 붙어서 이동할 때, 중간의 경로에 통제구역이 있다면 이동할 수 없다.

이 조건이 문제에선 명확하게 나타나있지 않고, 예제 해설을 통해 추측하도록 문제가 구성되어있다. 개인적으로는 좋은 방식이라고는 생각하지 않는다. 심지어 본대회때는 3번 예제조차 없었다...

 

아무튼 이러한 조건에 맞게 너비 우선 탐색을 진행하면 된다.

단 같은 위치에 도달하더라도, 직전의 방향과 속력에 따라 다음 이동 가능 위치가 달라지므로, visit 배열을 이를 고려해서 만들어줘야 한다.

탐색 가능 조건 역시 복잡하므로 잘 확인해줘야 한다.