[BOJ/C++] 4485 녹색 옷 입은 애가 젤다지?

문제

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

풀이

맞게 풀어놓고 진짜 한참을 삽질했다;; 처음에는 cnt 배열을 INF로 초기화해야하는데 0으로 초기화해서 해맸고, memset은 0으로 밖에 초기화가 안돼서 fill을 사용하거나 직접 초기화해야하는데 memset으로 INF를 초기화해서 에러가 발생했다.

BFS 로직인데 다른 점은 방문여부로 큐에 push를 하는 것이 아니라, 현재의 값보다 작은 값 일 때만 갱신하도록 조건을 걸어야한다.

코드

#include <iostream>
#include <queue>

using namespace std;

int N;
int arr[130][130];
int cnt[130][130];

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};


void bfs(int x, int y) {
	cnt[x][y] = arr[x][y];

	queue <pair<int, int>> q;
	q.push({ x, y });
	
	while (!q.empty()) {
		int xx = q.front().first;
		int yy = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = xx + dx[i];
			int ny = yy + dy[i];

			if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
				if (cnt[nx][ny] > cnt[xx][yy] + arr[nx][ny]) {
					cnt[nx][ny] = cnt[xx][yy] + arr[nx][ny];
					q.push({ nx, ny });
				}
			}
		}
	}
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int num = 1;
	for (int i = 0; i < 130; i++) {
		for (int j = 0; j < 130; j++) {
			cnt[i][j] = 987654321;
		}
	}

	while (1) {
		cin >> N;
		if (N == 0)	break;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				int tmp;
				cin >> tmp;
				arr[i][j] = tmp;
			}
		}
		bfs(0,0);

		cout << "Problem " << num << ": " << cnt[N - 1][N - 1] << '\n';

		N = 0;
		for (int i = 0; i < 130; i++) {
			for (int j = 0; j < 130; j++) {
				arr[i][j] = 0;
				cnt[i][j] = 987654321;
			}
		}
		num++;
	}

	return 0;
}