문제
https://www.acmicpc.net/problem/17484
풀이
BFS 시도 (오답)
최단 거리를 보장하는 BFS 알고리즘을 이용하면, 연료 비용도 최소가 되지 않을까..? 했는데, 그건 아닌 거 같다. 왜냐하면 조금 돌아서 가더라도 연료 비용이 최소가 되는 경우가 있을 수 있기 때문이다.
BFS로 다소 복잡한 코드를 짜봤는데,, 계속 오답이어서 다른 풀이를 참고했다,,
#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 7;
int N, M;
int arr[MAX][MAX];
bool visited[MAX][MAX];
int dx[] = {1, 1, 1};
int dy[] = {-1, 0, 1};
int ans = 1e9;
// 1행 ~ N행까지 이동
// 같은 방향으로 2번 연속 이동 불가
// 지구 -> 달 이동에 필요한 최소 연료 비용 구하기
class Node {
public:
pii pos; // 위치
int prevDir; // 이전 칸에서 이동한 방향
int cost; // 현재까지 비용
Node(pii pos, int prevDir, int cost){
this->pos = pos;
this->prevDir = prevDir;
this->cost = cost;
}
};
void input() {
cin >> N >> M;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cin >> arr[i][j];
}
}
}
void bfs(int x, int y, int prevDir){
queue<Node> q;
q.push(Node({x, y}, prevDir, 0));
visited[x][y] = true;
while(!q.empty()){
Node ele = q.front();
int r = ele.pos.first;
int c = ele.pos.second;
int prevDir = ele.prevDir;
int cost = ele.cost;
q.pop();
if(r == N - 1){
ans = min(ans, cost + arr[r][c]);
memset(visited, 0, sizeof(visited));
return;
}
if(prevDir == 0){
for(int d = 1; d <= 2; d++){
int nr = r + dx[d];
int nc = c + dy[d];
if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
if(visited[nr][nc]) continue;
q.push(Node({nr, nc}, d, cost + arr[nr][nc]));
visited[nr][nc] = true;
}
}else if(prevDir == 1){
for(int d = 0; d <= 2; d += 2){
int nr = r + dx[d];
int nc = c + dy[d];
if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
if(visited[nr][nc]) continue;
q.push(Node({nr, nc}, d, cost + arr[nr][nc]));
visited[nr][nc] = true;
}
}else if(prevDir == 2){
for(int d = 0; d <= 1; d++){
int nr = r + dx[d];
int nc = c + dy[d];
if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
if(visited[nr][nc]) continue;
q.push(Node({nr, nc}, d, cost + arr[nr][nc]));
visited[nr][nc] = true;
}
}
}
}
void solution() {
for(int i = 0; i < M; i++){
if(i == 0){
bfs(0, i, 1);
bfs(0, i, 2);
}else if(i == M - 1){
bfs(0, i, 0);
bfs(0, i, 1);
}else{
for(int j = 0; j < 3; j++){
bfs(0, i, j);
}
}
}
cout << ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
input();
solution();
return 0;
}완탐
그냥 DFS 이용해서 모든 경우의 수를 탐색하면 되는 거였다.
대신에 이전 칸에서의 이동 방향이 d일 때, 다음으로 (i, j)까지 이동하는 데 필요한 최소 연료 비용을 DFS 함수에서 반환하게 만든다.
재귀 호출의 종료 조건은 행의 위치가 N까지 커진 경우이다.
#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 7;
int N, M;
int arr[MAX][MAX];
int dc[] = {-1, 0, 1};
int ans = 1e9;
void input() {
cin >> N >> M;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cin >> arr[i][j];
}
}
}
int dfs(int r, int c, int prevDir){
// 달에 도착한 경우
if(r == N) return 0;
// 세가지 방향 중에 최소 연료 비용 저장
int result = 1e9;
for(int i = 0; i < 3; i++){
int nr = r + 1;
int nc = c + dc[i];
if(nc < 0 || nc >= M) continue;
// 이전 칸에서 이동한 방향과 같은 경우 패스
if(prevDir == i) continue;
int nextCost = dfs(nr, nc, i);
result = min(result, arr[r][c] + nextCost);
}
return result;
}
void solution() {
// M개의 열에 대해 최소 비용 구하기
for(int i = 0; i < M; i++){
ans = min(ans, dfs(0, i, -1));
}
cout << ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
input();
solution();
return 0;
}DP
입력값이 더 커진다면 완탐으로는 해결하지 못할 가능성이 있다.
따라서, 다음과 같은 dp 테이블을 만들어서 부분 문제의 해를 메모이제이션 해두면, 다른 부분 문제를 해결할 때 그대로 가져와 사용할 수 있다. (dp의 특징: 최적 부분 구조, 중복되는 부분 문제)
dp[i][j][d]: 이전 칸에서의 이동 방향이 d일 때, 현재 (i, j) 지점까지 오는 데 필요한 최소 연료 비용
#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 7;
int N, M;
int arr[MAX][MAX];
int dp[MAX][MAX][3];
int dc[] = {-1, 0, 1};
int ans = 1e9;
void input() {
cin >> N >> M;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cin >> arr[i][j];
}
}
}
int dfs(int r, int c, int prevDir){
// 달에 도착한 경우
if(r == N) return 0;
// dp 테이블의 원소에 대한 참조 변수 정의
int& result = dp[r][c][prevDir];
// 테이블에 저장된 값이 있으면 그대로 사용
if(result != 0) {
return result;
}
// 세가지 방향 중에 최소 연료 비용 저장
result = 1e9;
for(int i = 0; i < 3; i++){
int nr = r + 1;
int nc = c + dc[i];
if(nc < 0 || nc >= M) continue;
// 이전 칸의 이동 방향과 같은 경우 패스
if(prevDir == i) continue;
// 재귀호출 할 때마다 dp 테이블에 결과 저장
int nextCost = dfs(nr, nc, i);
result = min(result, arr[r][c] + nextCost);
}
return result;
}
void solution() {
// M개의 열에 대해 최소 비용 구하기
for(int i = 0; i < M; i++){
ans = min(ans, dfs(0, i, -1));
}
cout << ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
input();
solution();
return 0;
}C++에서 reference 타입 변수를 만들면, 원본을 복사하지 않고도 값을 직접 변경할 수 있다. 위의 코드에서 dfs 함수 안의 result 변수도 레퍼런스 타입이어서 result 값을 수정하면, dp[r][c][prevDir]의 값이 수정되는 것과 동일한 효과를 갖는다.
참고자료
습관이 될 때까지 📝