7-C 질문입니다.

안녕하세요 yeon님 ㅎㅎ

아 솔직히 오래걸렸어요 ㅎㅎ 정말 잘 짜셨거든요. 저또한 이게 왜 틀리지? 하면서 하나하나 불필요한 코드를 지워가면서 디버깅을 했습니다.

먼저 yeon님의 코드를 좀 수정해서 맞아봤습니다.

http://boj.kr/9c5c7339d0c046bb8dc1926b4f5b7e8c

불필요한 부분은 벡터넘기기, 전역변수로 배열선언시 0으로 초기화 되니 초기화 불필요. cnt없애기, value미리 선언 이였습니다.

자 여기서 핵심이 되었던 사안은 cnt였습니다.

이 문제 dp의 정의는 뭘까요? 바로 {i,j} 좌표에서 "최대로 갈 수 있는 경우의 수"가 되어야 하죠(-1 경우의 수 제외)

자 그러면 yeon님의 코드는 이러한 dp를 잘 채울 수 있었을까요?

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

int n, m;
int di[] = {-1, 1, 0, 0};
int dj[] = {0, 0, -1, 1};
char b[54][54];
int rec[54][54];
vector<vector<int>> v(54, vector<int>(54, 0));
// good
int dp(int i, int j, int cnt) {
	// good
	if (i < 0 || j < 0 || i >= n || j >= m || b[i][j] == 'H') return cnt;
	// good
	if (v[i][j]) {
		cout << -1 << "\n";
		exit(0);
	}
	// good  
	int & ret = rec[i][j];
	if (ret) return ret;
	
	v[i][j] = 1;
	int value = (int)(b[i][j] - '0');
	for (int d=0; d<4; d++) {
		int ni = i + di[d]*value;
		int nj = j + dj[d]*value;
		ret = max(ret, dp(ni, nj, cnt+1));
	}
	v[i][j] = 0;
	return ret; 
}

int main() {
	cin >> n >> m;
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {
			cin >> b[i][j];
		}
	} 
	cout << dp(0, 0, 0) << "\n";
	
	
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {
			cout << rec[i][j] << ' ';
		}
		cout << '\n';
	} 
	return 0;
}
/*
예제입력
3 7
3942178
1234567
9123532
 
5
5 3 0 5 0 3 5
0 0 0 0 0 0 0
4 0 0 5 5 0 5
*/

이게 yeon님의 코드 - 디버깅인데요. 3942.. 여기서 9인데도 3이 찍히고 있습니다. 올바르게 dp값이 저장되지 않고 있다는 의미입니다.

저의 코드는 다음과 같습니다.

#include <bits/stdc++.h>

using namespace std;
int t,a,d[54][54];
string s; 
char b[54][54];
bool check[54][54];
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};
bool in(int aa,int bb){
    return(1<=aa && aa<=t && 1<=bb && bb<=a);
}  
int down(int y,int x){
    if(!in(y, x) || b[y][x] == 'H') return 0;
    if(check[y][x]){
        cout << -1 << "\n";
        exit(0);
    } 
    int &ret = d[y][x];
    if(ret) return ret;

    check[y][x] = 1;
    int value = (int)b[y][x] - '0';
    for(int i = 0; i < 4; i++){
        int ny = y + dy[i] * value;
        int nx = x + dx[i] * value;
        ret= max(ret,down(ny,nx) + 1);
    }
    check[y][x] = 0;
    return ret;
}
int main(){
    cin >> t >> a;
    for(int i = 1; i <= t; i++){
        cin >> s;  
        for(int j = 1; j <= a; j++){
            b[i][j] = s[j - 1];
        }
    }
     
    cout << down(1, 1) << "\n";
    for(int i = 1; i <= t; i++){ 
        for(int j = 1; j <= a; j++){
        	cout << d[i][j] << " ";
        }
        cout << '\n';
    }
}
/*
예제입력
3 7
3942178
1234567
9123532
 
5
5 1 0 4 0 1 1
0 0 0 0 0 0 0
1 0 0 3 1 0 2
*/

잘 찍히죠?

사실 이러한 부분이 가장 어렵죠. 분명 cnt를 증가시키면서 한거 같은데 왜 저럴까... 근데 생각해보면 단순해요. i, j 빠져나갈 때 cnt를 반환하죠? 빠져나가는 그 i, j 에서의 dp[i][j]는 cnt를 반환하는게 맞을까요? 당연히 그 자리에는 올 수 없기 때문에 0을 반환하는게 맞겠죠?

DP의 의미를 생각하고 코드를 다시 보면 조금 이해하기가 쉬워집니다.

다만, 나머지 코드는 정말 잘 짜셨습니다. ㅎㅎ / 제가 yeon님 코드 불필요한 부분 없애는 것도 참고해주시구 해당 설명 참고해서 공부해주세요.

감사합니다.

이해했습니다! 범위를 벗어날 때 cnt를 반환할 경우 이상한 값이 들어간다는 것은 생각하지 못했네요. 파라미터로 cnt를 사용할 때는 이 차이를 인지하고 사용해야겠습니다. 답변 감사드립니다!