[백준] 4485번: 녹색 옷 입은 애가 젤다지? (C++)

문제

---

문제링크: https://www.noj.am/4485

4485번: 녹색 옷 입은 애가 젤다지?

 

문제 분석

---

동굴 내부에 도둑 루피들만이 쫙 깔려있는 상황이다.

 

어차피 잃을 수밖에 없지만

기왕 이렇게 된 거, 최대한 덜 잃게 가보자는 것이다.

 

 

자세한 풀이

---

DP로 풀어야겠다고 생각해서

오케이, 최소로 만들면서 내려가보자고~

 

위쪽, 왼쪽 중 최소인 것만을 선택해 합해주는 로직을 만들었따

 

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

int N;
int cnt=1;
int board[126][126];
int dp[126][126];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    while(1){
    	cin >> N;
    	if(!N)break;
    	
    	for(int i=1;i<=N;i++)
    		for(int j=1;j<=N;j++)
    			cin >> board[i][j];
    			
    	for(int i=1;i<=N;i++)
    		for(int j=1;j<=N;j++){
    			if(i==1)dp[i][j]=dp[i][j-1]+board[i][j];
    			else if(j==1)dp[i][j]=dp[i-1][j]+board[i][j];
    			else dp[i][j]=min(dp[i-1][j],dp[i][j-1])+board[i][j];
    		}
    	
    	cout << "Problem " << cnt++ << ": " << dp[N][N] << '\n';
	}
}

 

그리고 가볍게 제출~

하기 전에 테스트 케이스를 돌려보았는데,

 

 

?

2번 문제 왜 20으로 나와

 

음, 근데 20 맞지 않나 ?

~~라고 생각했었다

 

그래서 직접 수동 DP를 해봤는데,

// 수동 DP

case 1, 충족
 5 10 14
 8 17 15
11 13 20

case 2, 반례
 3 10 12 12 13
 5 13 12 21 14
 6  8  9 17 15
15 16 18 19 15
18 22 23 20 20

위는 DP로 풀었을 경우, 답 20

 

1번은 문제 없었고,

2번은 직접 해봐도 20이 나오는 거시어따

 

잘못 더했나 싶어서 2번 더 해봤는데 똑같이 20이었다.

 

.

.

Hoxy..

 

내가 아예 잘못 생각하고 있나?

 

이쯤되면 킹리적 갓심으로 능지 이슈가 의심된다.

어케 19가 나오는지, 내가 젤다가 되어보자

 

 

DP로 풀 수 없는 이유

---

 3 11 11 12
 5  9 13
 6  8  9 14
         14
         19
하지만 위 경우처럼 위로 돌아갈 경우,
답은 19로 더 효율적인 코스가 존재하게 됨.

아

ㅏ

 

선택지가 오른쪽, 아래만 있는 게 아니라서

이걸로는 모든 경우를 고려할 수가 없었던 것이다.

 

DAG가 아니라는 건데,

쉽게 말하면 순환고리가 있어서

지나온 길을 다시 돌아갈 수 있다는 의미
(왔던 길 말고, 뒤로 돌아간다고)

 

DAG란? 재윤심의 블로그 참고

 

재귀의 요정은 잠시 들어가있어

 

이제 BFS 탐색으로 풀어볼까

 

이차원 배열을 모두 최대값으로 채워놓고,

일반적으로 써왔던 BFS 로직을 적용해주면?

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int N;
int cnt=1;
int board[126][126];
int zelda[126][126];

int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
queue<pair<int,int>> Q;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    while(1){
    	cin >> N;
    	if(!N)break;
    	
    	for(int i=0;i<N;i++)
    		for(int j=0;j<N;j++)
    			cin >> board[i][j];
    			
    	fill_n(zelda[0],126*126,200000);
    	
    	Q.push({0,0});
    	zelda[0][0]=board[0][0];
    	
    	while(!Q.empty()){
    		auto cur=Q.front(); Q.pop();
    		for(int i=0;i<4;i++){    			
				int nx=cur.X+dx[i];
				int ny=cur.Y+dy[i];
				
				if(nx<0||nx>=N||ny<0||ny>=N)continue;
				if(zelda[nx][ny]<zelda[cur.X][cur.Y]+board[nx][ny])continue;
				Q.push({nx,ny});
				zelda[nx][ny]=zelda[cur.X][cur.Y]+board[nx][ny];
			}
		}
    	
    	cout << "Problem " << cnt++ << ": " << zelda[N-1][N-1] << '\n';
	}
}

이런 코드가 나오게 된다.

 

그럼 이제 가볍게 제출~

 

또 다른 위협

---

?

 

왜

또 뭐가 문제야 대체

 

코드를 이곳 저곳 만져보다가

내가 BFS 로직 내부에서 예외처리하던 부분을 continue로 빼는 게 아니라

&&로 묶어서 만족할 때만 진행하도록 바꾸니 만족했다.

 

예외 하나하나 continue보다

맞는 조건일 때만 진행하는 게 더 효율적이라는 교훈을 얻었다

 

하긴, 그렇긴해~

앞으로는 이 방식으로 fix

 

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int N;
int cnt=1;
int board[126][126];
int zelda[126][126];

int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
queue<pair<int,int>> Q;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    while(1){
    	cin >> N;
    	if(!N)break;
    	
    	for(int i=0;i<N;i++)
    		for(int j=0;j<N;j++)
    			cin >> board[i][j];
    			
    	fill_n(zelda[0],126*126,200000);
    	
    	Q.push({0,0});
    	zelda[0][0]=board[0][0];
    	
    	while(!Q.empty()){
    		auto cur=Q.front(); Q.pop();
    		for(int i=0;i<4;i++){    			
				int nx=cur.X+dx[i];
				int ny=cur.Y+dy[i];
				
				if(nx>=0&&nx<N&&ny>=0&&ny<N)
					if(zelda[nx][ny]>zelda[cur.X][cur.Y]+board[nx][ny]){
						Q.push({nx,ny});
						zelda[nx][ny]=zelda[cur.X][cur.Y]+board[nx][ny];
					}
			}
		}
    	
    	cout << "Problem " << cnt++ << ": " << zelda[N-1][N-1] << '\n';
	}
}

 

궁금한 점은 댓글로~