[BOJ] 20420 화살표 미로 (Normal)

문제 요약

문제 링크: 백준 20420 - 화살표 미로 (Normal)

문제 설명

---

접근 방법

(y, x) 좌표와 남은 R, L 아이템 개수를 하나의 상태로 정의하고, 이 상태를 정점으로 하는 너비 우선 탐색(BFS)을 수행하면 된다고 생각했다. 각 상태의 방문 여부는 (y, x, 남은 R개수, 남은 L개수)를 인덱스로 하는 4차원 배열로 관리하여 중복 탐색을 효율적으로 방지할 수 있다.

---

코드

#include <bits/stdc++.h>
using namespace std;

int r, c, k;
char mat[51][51];
pair<int, int>item;  // R회전, L회전
bool vis[51][51][151][151];
int d[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
map<char, int>m;

void solve() {
    item.first = k; item.second = k;
    queue<tuple<int, int, pair<int, int>>>q;
    q.push({ 0,0,item });
    vis[0][0][k][k];
    m.insert({ 'R',0 });    m.insert({ 'D',1 });
    m.insert({ 'L',2 });    m.insert({ 'U',3 });
    while (q.size()) {
        int y = get<0>(q.front());
        int x = get<1>(q.front());
        auto t = get<2>(q.front());
        q.pop();
        if (y == r - 1 && x == c - 1) {
            cout << "Yes";
            return;
        }
        // 1. 원래의 이동
        char cur = mat[y][x];
        int dir = m[cur];
        int yy = y + d[dir][0];
        int xx = x + d[dir][1];
        if (yy < r && yy >= 0 && xx < c && xx >= 0 && !vis[yy][xx][t.first][t.second]) {
            q.push({ yy,xx,t });
            vis[yy][xx][t.first][t.second] = 1;
        }
        // 2. L 주문 (최대 3번이죠)
        auto left = t;
        for (int i = 0; i < 3; i++) {
            dir--;
            if (dir == -1) dir = 3;
            int yy = y + d[dir][0];
            int xx = x + d[dir][1];
            left.second--;
            if (left.second < 0)
                break;
            if (yy >= r || yy < 0 || xx >= c || xx < 0)
                continue;
            if (vis[yy][xx][left.first][left.second])
                continue;
            q.push({ yy,xx,left });
            vis[yy][xx][left.first][left.second] = 1;
        }
        // 3. R 주문 (최대 3번이죠)
        auto right = t;
        dir = m[cur];
        for (int i = 0; i < 3; i++) {
            dir++;
            if (dir == 4) dir = 0;
            int yy = y + d[dir][0];
            int xx = x + d[dir][1];
            right.first--;
            if (right.first < 0)
                break;
            if (yy >= r || yy < 0 || xx >= c || xx < 0)
                continue;
            if (vis[yy][xx][right.first][right.second])
                continue;
            q.push({ yy,xx,right });
            vis[yy][xx][right.first][right.second] = 1;
        }
    }
    cout << "No";
}

void input() {
    cin >> r >> c >> k;
    for (int i = 0; i < r; i++)cin >> mat[i];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    solve();
}