[17267] 상남자

https://www.acmicpc.net/problem/17267

17267번: 상남자

<문제>

정점의 재방문을 허용할 필요성이 있을 수 있겠다는 생각이 들 수 있지만...

그렇다고 visit[N][M][L][R]처럼 만들수도 없다. 이렇게 만들면 배열 갯수만 1000^4개다.

 

어떤 정점을 이미 방문했더라도 그때에 비해서 적은 L, R로 이동한다면 더 멀리 갈 수 있다는 부분을 염두해야 한다.

좌나 우로 이동하는것이 가중치가 1, 상이나 하로 이동하는것이 가중치가 0이라는 것에 착안하여

0-1 BFS로 모든 정점을 최적의 L, R 이동횟수로 접근이 가능하다.

덱을 사용할 수도 있고, 가중치가 0인 경우는 현재 정점과 같은 열뿐이므로 단순히 while()로 구현할수도 있다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, m, l, r, sy, sx, a[1001][1001], dy[4] = {1, -1, 0, 0},
                                       dx[4] = {0, 0, 1, -1};
bool visited[1001][1001];
typedef struct {
    int y, x, left, right;
} state;
queue<state> q;
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> l >> r;
    int i, j;
    for (i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (j = 0; j < m; j++) {
            if (s[j] == '2') {
                sy = i;
                sx = j;
                q.push({sy, sx, 0, 0});
                visited[sy][sx] = true;
                a[sy][sx] = 0;
            } else
                a[i][j] = s[j] - '0';
        }
    }
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        for (i = 0; i < 2; i++) {
            int y = cur.y;
            int x = cur.x;
            while (1) {
                y += dy[i];
                if (y < 0 || y >= n) break;
                if (a[y][x] == 1) break;
                if (visited[y][x] == false) {
                    visited[y][x] = true;
                    q.push({y, x, cur.left, cur.right});
                }
            }
        }
        for (i = 2; i < 4; i++) {
            int y = cur.y + dy[i];
            int x = cur.x + dx[i];
            if (y < 0 || x < 0 || y >= n || x >= m) continue;
            if (a[y][x] == 1) continue;
            if (i == 2 && cur.right == r) continue;
            if (i == 3 && cur.left == l) continue;
            if (visited[y][x] == false) {
                visited[y][x] = true;
                if (i == 2)
                    q.push({y, x, cur.left, cur.right + 1});
                else
                    q.push({y, x, cur.left + 1, cur.right});
            }
        }
    }
    int cnt = 0;
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++)
            if (visited[i][j]) cnt++;
    cout << cnt;
    return 0;
}