[BOJ/C++] 17484 진우의 달 여행 (Small)

문제

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

풀이

DP 아니면 재귀로 완전탐색하는 문제
BFS로 풀다가 너무 코드가 복잡해져서 그냥 솔루션 찾아봤다.

행렬을 배열로 표현할 때, x좌표 y좌표 순서 바뀌는 거 잊지말기 !!!

행렬
x좌표: 열(column)
y좌표: 행(row)

배열
2차원 배열에서 map[y][x]
y: row의 인덱스
x: column의 인덱스

코드

#include <iostream>

using namespace std;

int N, M;
int map[7][7];
int ans = 999999999;
int dx[3] = { -1, 0, 1 };

int Solve(int y, int x, int last) {
	if (y == N)	return 0;

	int tmp = 999999999;
	for (int i = 0; i < 3; i++) {
		if (x + dx[i] >= 0 && x + dx[i] < M && i != last)
			tmp = min(tmp, Solve(y + 1, x + dx[i], i) + map[y][x]);
	}

	return tmp;
}

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

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

	for (int i = 0; i < M; i++)
		ans = min(ans, Solve(0, i, -1));

	cout << ans;
	
	return 0;
}