[백준] 17391 무한부스터

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

17391번: 무한부스터

직사각형 map이 주어지고

map element들마다 위치한 정수 값만큼 최대로 이동이 가능할 떄 (방향은 only 오른쪽, 아래쪽)

0, 0 좌표의 element부터 시작해서 m-1, n-1 element를 도착하는 최단거리를 구하는 문제

 

첫번째 생각

dfs 알고리즘을 이용해서 문제를 해결하는 것을 생각

구현 완료했으나 시간초과가 발생함

 

두번째 생각

dfs 돌리면서 이미 구해놓은 최소 depth 이상의 dfs는 호출하지 않는 방식으로 가지치기 수행

구현 완료했으나 시간초과;;

 

세번째 생각

인터넷으로 찾아보니 bfs를 이용하는 방식으로 구현한 것들을 확인함

나도 동일하게 bfs를 이용해서 구현

이 때 depth값을 구하는 방법을 조금 고민했었는데

queue에 push하는 최초의 객체를 시작으로 해당 객체를 pop해서 탐색을 수행해서
queue push 수행하면 pop 한 값에 depth + 1 을 해주는 식으로 구현했음

구현 완료했으나 메모리초과;;;;;

 

네번째 생각

bfs돌릴 때 queue 크기가 너무 큰가보다

어떻게 하면 push를 줄일 수 있을 지 고민해보았는데

bfs로 지도를 탐색했을 때 map에 visit 처리해주나 안해주나 동일한 결과값을 내는 것을 시뮬레이션으로 확인

그렇다면 queue push 조건으로 visit처리 수행해주면 push 수를 줄일 수 있겠따고 생각함

구현 완료 및 성공!

 

 

#include<stddef.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

typedef struct {
	uint16_t i;
	uint16_t j;
	uint16_t size;
	uint16_t visit;
}map_t;

typedef pair<int, map_t> queue_map;

int N, M;
int di[] = { 0, 1 };
int dj[] = { 1, 0 };
map_t map[301][301];

int bfs(int _i, int _j)
{
	queue<queue_map> q;
	q.push({ 1, map[_i][_j] });
	map[_i][_j].visit = 1;
	
	while (!q.empty()) {

		queue_map x;
		x = q.front(); q.pop();

		for (int i = 0; i < 2; i++) {
			for (int k = 1; k <= map[x.second.i][x.second.j].size; k++) {
				int ni = x.second.i + di[i] * k;
				int nj = x.second.j + dj[i] * k;

				if (ni < 0 || nj < 0 || ni >= N || nj >= M || map[ni][nj].visit == 1) {
					continue;
				}

				if (ni == N - 1 && nj == M - 1) {
					return x.first;
				}
				map[ni][nj].visit = 1;
				q.push({ x.first + 1, map[ni][nj] });
			}
		}
	}

	return 0;
}

int main(void) {
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			map[i][j].i = i;
			map[i][j].j = j;
			cin >> map[i][j].size;
		}
	}

	cout << bfs(0, 0);

	return 0;
}