[PS][완전탐색] BOJ 17484 - 진우의 달 여행(Small)

[2021년 08월 13일 23시 02분 작성]

[PS][완전탐색] BOJ 17484 : 진우의 달 여행(Small)

---

[문제 링크 : 클릭]

---

1. 풀이

 

Solve 함수를 다음과 같이 정의합니다.

Solve(y, x, last) : 현재 좌표가 (y, x)이고, 마지막으로 움직인 방향이 last일 때,                       우주선이 달까지 가는데에 필요한 연료의 최소값

위 함수에 맞게 재귀로 완전탐색을 돌려주면 해결할 수 있습니다.

 

---

2. 소스코드

 

[Github 링크 : 클릭]

#include <bits/stdc++.h>
using namespace std;

const int INF = 2147000000;
const int dx[3] = {-1, 0, 1};
int n, m, ans=INF, board[7][7];

int Solve(int y, int x, int last)
{
	if(y==n) return 0; //기저사례 : 달에 도착

	int ret = INF; 
	for(int i=0; i<3; i++)
	{
		if(last==i) continue; //이전에 움직인 방향으로 움직일 수 없음
		if(x+dx[i]<0 || x+dx[i]>=m) continue; //범위 밖으로 벗어날 수 없음

		ret = min(ret, Solve(y+1, x+dx[i], i)+board[y][x]); 
	}
	return ret;
}

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>>board[i][j];

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

	cout<<ans<<'\n';

	return 0;	
}

---

3. 복기

.