BOJ26153 로하의 농사(C++)

https://www.acmicpc.net/problem/26153
태그 : 그래프, 깊이 우선 탐색

사고 흐름

그래프 문제인데, 브루트포스, bfs, dfs 등의 방법 등이 생각났다.

같이 고민하던 동기분이 dp 아이디어를 내주셨고,

처음엔 괜찮다는 생각이 들다가 조금 고민해보니 안될 것 같다는 생각이 들었다.

내가 선택한 방법은 dfs로 구현하되 방향만 잘 컨트롤 해주는 것이였다.

#include <iostream>
#include <algorithm>
using namespace std;

#define INF 1000000007

int n, m;
int arr[50][50];
int visited[50][50];
int x, y, p;
int ans;

//       0
//     3 x 1
//       2

void dfs(int r, int c, int from, int p, int v);

void init() {
	visited[x][y] = 1;
	dfs(x - 1, y, 0, p - 1, arr[x][y]);
	dfs(x, y + 1, 1, p - 1, arr[x][y]);
	dfs(x + 1, y, 2, p - 1, arr[x][y]);
	dfs(x, y - 1, 3, p - 1, arr[x][y]);
}

void dfs(int r, int c, int from, int p, int v) {
	if (visited[r][c] || r >= n || r < 0 || c >= m || c < 0 || p < 0) {
		return;
	}
	visited[r][c] = 1;

	v += arr[r][c];
	ans = max(ans, v);
	if (from == 0) {
		dfs(r - 1, c, 0, p - 1, v);
		dfs(r, c + 1, 1, p - 2, v);
		dfs(r, c - 1, 3, p - 2, v);
	}
	else if (from == 1) {
		dfs(r - 1, c, 0, p - 2, v);
		dfs(r, c + 1, 1, p - 1, v);
		dfs(r + 1, c, 2, p - 2, v);
	}
	else if (from == 2) {
		dfs(r, c + 1, 1, p - 2, v);
		dfs(r + 1, c, 2, p - 1, v);
		dfs(r, c - 1, 3, p - 2, v);
	}
	else {
		dfs(r - 1, c, 0, p - 2, v);
		dfs(r + 1, c, 2, p - 2, v);
		dfs(r, c - 1, 3, p - 1, v);
	}
	visited[r][c] = 0;
}

void solve() {
	ans = arr[x][y];
	init();
}

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

	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> arr[i][j];
		}
	}
	cin >> x >> y >> p;
	solve();
	cout << ans;
}

후기

시작 정점 처리 때문에 WA를 많이 받았다. 무지성 제출을 좀 줄이고 엣지 케이스나 로직을 더 고민해야...

풀고 보니 bfs와 dp를 잘 섞으면 어떻게 될 수도 있겠다는 생각이 들었다.