BOJ 14948

군대탈출하기

문제출처

문제 해석

  • N x M 배열에서 (0,0)-> (N,M)으로 가기 위해 필요한 최소 레벨제한을 구하는 문제입니다.
  • 각 블록에 레벨 제한이 있는데 최소한 해당 블록 레벨제한이 되어야 지날 수 있습니다.
  • 한번 무시하고 두칸을 연달아 이동할 수 있습니다. (도중 방향전환은 되지 않고, 범위가 넘어가면 안됩니다)

설계(10)

  • priority queue를 사용하여 레벨제한이 낮은 좌표부터 이동하도록 합니다.
  • flag를 설정하여, 무시를 이미 한 경우와 하지 않은 경우로 나누어 하지않은 경우에 한칸을 더 이동하게 하였습니다.
  • dist[x][y][flag] 배열에 해당 좌표까지 오기 위한 최대 레벨을 저장합니다. (지나온 길의 레벨제한 중 최대값이 최소한의 필요한 레벨제한이기 때문입니다)
  • x == N-1 && y == M-1 일 경우 바로 리턴하도록 하였습니다.

구현(20)

코드
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 100
int map[MAXN][MAXN];
int dist[MAXN][MAXN][2];
struct node {
	int x;
	int y;
	int flag;
	int level;
	bool operator < (const node& a) const {
		return a.level < level;
	}
};
priority_queue<node> pq;
int N, M;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
bool is_range(int x, int y) {
	if (x < 0 || y < 0 || x >= N || y >= M) return false;
	return true;
}
int bfs() {
	pq.push({ 0,0,0 ,map[0][0]});
	dist[0][0][0] = map[0][0];
	while (!pq.empty()) {
		int x = pq.top().x;
		int y = pq.top().y;
		int flag = pq.top().flag;
		int level = pq.top().level;
		if (x == N - 1 && y == M - 1) return dist[x][y][flag];
		pq.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (!is_range(nx, ny)) continue;
			if (dist[nx][ny][flag] == -1) {
				dist[nx][ny][flag] = max(dist[x][y][flag], map[nx][ny]);
				pq.push({ nx,ny,flag,map[nx][ny] });
			}
			if (!flag) {
				nx += dx[i];
				ny += dy[i];
				if (!is_range(nx, ny)) continue;
				if (dist[nx][ny][flag + 1] != -1) continue;
				dist[nx][ny][flag + 1] = max(dist[x][y][flag], map[nx][ny]);
				
				pq.push({ nx,ny,flag + 1,map[nx][ny] });
			}
		}
	}

}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	memset(dist, -1, sizeof(dist));
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}
	cout << bfs() <<"\n";
	return 0;
}
디버깅
제출결과
  • 8ms

    마무리

  • 우선순위 큐를 이용하여 최적의 레벨제한을 찾는 문제로, 블록을 한번 무시하고 뛰는 조건이 추가되어 약간 까다로운 문제였습니다.