백준 27453 - 귀엽기만 한 게 아닌 한별 양 (C++)

문제

• 문제 링크

  
   BOJ 27453 - 귀엽기만 한 게 아닌 한별 양 
  

• 문제 요약

가장 최근 지나온 $3$ 개 이하 칸에 있는 불상사의 개수 합이 $K$ 이하가 되게 이동하려 한다.
학교에서 집으로 가는 최단 거리를 구해보자.

• 제한

TL : $2$ sec, ML : $512$ MB




$2 ≤ N, M ≤ 1,000$

$0 ≤ K ≤ 27$

알고리즘 분류

• 그래프 이론(graphs)
• 그래프 탐색(graph_traversal)
• 너비 우선 탐색(bfs)

풀이

우선 불상사 합이 $K$ 를 넘는지에 대한 여부는 이전 위치의 정보를 들고 있으면 간단히 처리할 수 있다.
방문 처리에 있어서 다소 까다로워 보일 수 있는데, "방향에 대한 방문 처리를 하자" 라는 생각이 들었다면 이미 문제를 다 푼 것이나 다름 없다.

구체적으로 이전 지점, 현재 지점, 다음 지점을 각각 $P1, P2, P3$ 이라 할 때,

• 큐에서 $5$개의 정보를 관리하자. ( $P2_y, P2_x, P1_y, P1_x, distance$ )


• $M[P2_y][P2_x] == $'$H$' 면 $distance$ 출력 후 종료.


• $P2$로부터 $4$개의 방향 $d_i$에 대해,
  1. $P3$이 맵 내부에 있으며
  2. 해당 방향으로 이동한 적이 없고
  3. $P3 ≠ P1$ && $M[P3] ≠$ '$X$' 이며
  4. $D[P1] + D[P2] + D[P3] ≤ K$ 를 만족하면
  5. 그 지점으로의 탐색을 진행한다.

지점 간 불상사 합을 간편히 계산하기 위하여 $map$ 자료 구조( $D[]$ ) 를 이용하였다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int dy[]{ -1, 1, 0, 0 }, dx[]{ 0, 0, -1, 1 };
queue <tuple<int, int, int, int, int>> Q;
map <char, int> D{ {'S', 0}, {'H', 0} };
char M[1001][1001], V[1001][1001][4];
int n, m, k, i, j;
 
void in()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> k;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            if (cin >> M[i][j]; M[i][j] == 'S') Q.push({ i, j, 0, 0, 0 });
    for (i = 0; i < 10; i++) D[i + 48] = i;
}
void sv()
{
    while (Q.size())
    {
        auto [a, b, c, d, e](Q.front()); Q.pop();
        if (M[a][b] == 'H') cout << e, exit(0);
        for (i = 0; i < 4; i++)
        {
            int y(a + dy[i]), x(b + dx[i]);
            if (y && x && y <= n && x <= m && !V[a][b][i] && (y ^ c || x ^ d) && M[y][x] ^ 'X' && D[M[a][b]] + D[M[c][d]] + D[M[y][x]] <= k)
                V[a][b][i] = 1, Q.push({ y, x, a, b, e + 1 });
        }
    }
}
int main()
{
    in();
    sv();
    cout << -1;
}

comment

끝