[C/C++] 백준 - 11048번 : 이동하기

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

11048번: 이동하기

초기화를 통해 해결할 수 있는 간단한 문제이다.

#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <bitset>
#define INF 987654321
#define CUNLINK ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
#define ll long long
#define endl '\n'

using namespace std;

int N, M;
int adj[1001][1001];
int cache[1001][1001];

const int dy[] = { 1,0 };
const int dx[] = { 0,1 };
queue<pair<int, int>> q;

void start(int y, int x) {
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 2; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (0 <= ny && ny < N && 0 <= nx && nx < M) {
				if (cache[y][x] + adj[ny][nx] > cache[ny][nx]) {
					cache[ny][nx] = cache[y][x] + adj[ny][nx];
					q.push({ ny, nx });
				}
			}
		}
	}
}

int main() {
	CUNLINK;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> adj[i][j];
		}
	}
	memset(cache, -1, sizeof(cache));
	q.push({ 0,0 });
	cache[0][0] = adj[0][0];

	start(0, 0);
	cout << cache[N - 1][M - 1] << endl;

	return 0;
}