백준 17391 무한부스터

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

숭고한 공식 풀이는 여기서 보실 수 있습니다.

bfs 탐색을 하면 쉽지만 dfs 탐색을 하면 시간초과가 나거나 구현하기 까다롭게 하는 게 출제자의 의도였습니다. dfs 탐색을 나이브하게 짜는 경우 $300\times300\times300\times600$ 의 시간복잡도가 나오게 됩니다.

모든 칸 탐색 $300\times300$, 부스터 갯수 $300$, 최소 이동 횟수 $600$

(물론 최적화를 빡세게 하면 훨씬 나아집니다.)

반면에 bfs 탐색은 한 번 방문했던 점이 가장 작기 때문에 다시 방문할 필요가 없으므로 $300\times300\times300$ 의 시간복잡도가 나오게 됩니다.

오른쪽 또는 아래로만 이동하기 때문에 Dynamic Programming 으로도 쉽게 풀 수 있습니다.

#include<bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> pt;
const int SZ=305;
int graph[SZ][SZ];
int vst[SZ][SZ];
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	int n,m; cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>graph[i][j];
		}
	}
	queue<pt> q; q.push({0,{0,0}});
	while(!q.empty()){
		pt f=q.front(); q.pop();
		int x=f.ss.ff, y=f.ss.ss, w=f.ff;
		if(x==n-1 && y==m-1){
			cout<<w;
			return 0;
		}
		int dx[2]={0,1};
		int dy[2]={1,0};
		for(int i=0;i<2;i++){
			for(int j=1;j<=graph[x][y];j++){
				int nx=x+dx[i] * j;
				int ny=y+dy[i] * j;
				if(nx<0 || nx>=n) continue;
				if(ny<0 || ny>=m) continue;
				if(vst[nx][ny]) continue;
				q.push({w+1,{nx,ny}}); vst[nx][ny]=1;
			}
		}
	}
	return 0;
}