험난한 등굣길 (feat. 백준, 26009번)

험난한 등굣길
https://www.acmicpc.net/problem/26009

26009번: 험난한 등굣길

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
int N, M, dx[4], dy[4], arr[3001][3001];
bool visit[3001][3001];
void bfs(){
    queue<pair<int, int>> q;
    q.push(make_pair(1, 1));
    arr[1][1] = 0;
    visit[1][1] = true;
    while(!q.empty()){
        register int i = q.front().first, j = q.front().second;
        q.pop();
        for(register int d = 0, nx, ny; d < 4; ++d){
            nx = i + dx[d], ny = j + dy[d];
            if(1 <= nx && nx <= N && 1 <= ny && ny <= M && !visit[nx][ny])
                visit[nx][ny] = true, arr[nx][ny] = arr[i][j] + 1, q.push(make_pair(nx, ny));
        }
    }
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
    dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
    memset(arr, 0, sizeof(arr));
    memset(visit, false, sizeof(visit));
    register int K;
    cin >> N >> M >> K;
    for(register int k = 0, r, c, d, i, j; k < K; ++k){
        cin >> r >> c >> d;
        for(i = 0; i < d; ++i){
            if(r - d + i >= 1){
                if(c - i >= 1)
                    visit[r - d + i][c - i] = true;
                if(c + i <= M)
                    visit[r - d + i][c + i] = true;
            }
            if(r + d - i <= N){
                if(c - i >= 1)
                    visit[r + d - i][c - i] = true;
                if(c + i <= M)
                    visit[r + d - i][c + i] = true;
            }
        }
        if(c - d >= 1)
            visit[r][c - d] = true;
        if(c + d <= M)
            visit[r][c + d] = true;
    }
    bfs();
    if(visit[N][M]){
        cout << "YES\n";
        cout << arr[N][M];
    }
    else
        cout << "NO\n";
    return 0;
}
// *&)*@*

 

반응형

1. 정체구역 K개에 대해서 (R,C) 기준 D 이하의 모든 구역을 제한구역으로 둔다면 시간 초과 판정을 받게 됩니다.
2. bfs로 진행할 수 있고 따라서 제한 구역의 테두리만 제한구역으로 둔다면 그 내부의 구역 또한 검사의 대상이 아니므로 해결할 수 있습니다.
3. 따라서 기본적인 bfs 방식이지만 정체구역을 확인하는 부분만 신경쓰면 되겠습니다.