7-C 질문있습니다.

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

7-C

해결된 질문

작성

안녕하세요 큰돌님.

7-C에서 고전하다 강의 덕분에 결국 문제를 이해하고 풀 수 있게 되었습니다.

하지만 풀다가 의문점이 하나 생겨서 질문을 남기게 되었습니다.

http://boj.kr/3822cd1a54ca419ca30423cff2285ad4

이 코드의 로직과 정답코드의 로직의 차이점은 단 한가지 입니다.

정답코드는 기저 조건을 달성할 시 0을 return한 다음, 재귀 함수의 끝에 다다른 후, 다시 거슬러 올라가며 1씩 더해서 이동 거리를 구하는데, 이 코드는, 재귀함수를 호출하는 시점에 이동거리에 1을 더하고, 기저조건에 달성했을 시, 지금까지 쌓아온 이동거리를 return하여 이동거리를 구합니다.

그런데 제가 보기에 두 로직의 차이는 사실상 없는데, 위의 코드로 제출을 하면 6%에서 틀려버립니다.

이 두 로직 사이에 어떠한 유의미한 차이가 생겨 결과를 바꿔버리는지 제 나름 생각해봤지만 저는 차이를 생각하지 못했습니다.

정답 코드와 이 코드 사이, 어떤 차이가 생겨 결과가 바뀌어버렸을까요?

감사합니다. 그리고 새해 복 많이 받으세요.

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 비스킷님 ㅎㅎ

대략적으로는 잘 짜셨습니다만

	if (result == -1)
	{
		for (int i = 0; i < 4; ++i) {
			int ny = pos.first + dy[i] * board[pos.first][pos.second];
			int nx = pos.second + dx[i] * board[pos.first][pos.second];

			result = max(result, DFS(count + 1, { ny, nx }, board, dp, visited));
		}
	}

이부분이 가장 틀린 부분입니다. 이렇게 함수 매개변수로 count를 넘겨버리면 로컬옵티멈이 제대로 생성이 안되고 순차적인 DP가 제대로 쌓이지 않습니다. {1, 1} -> {2, 2} -> {3, 3}이라고 했을 때 3, 2, 1 이렇게 값이 생겨야 하는데 끝까지 가서 count를 끌어와 max를 하게 되니 3, 3, 3 이렇게 쌓이는 것이죠.

제가 좀 다듬어봤습니다. 참고부탁드립니다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

typedef vector<vector<int>> Board;
typedef pair<int, int> Pair;

int r, c;
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, 1, -1};

int DFS(int y, int x, const Board &board, Board &dp, Board &visited) {
    if (y < 0 || y >= r || x < 0 || x >= c || board[y][x] == -1) {
        return 0;
    }

    if (visited[y][x] == 1) {
        cout << -1 << "\n";
        exit(0);
    }

    if (dp[y][x] != -1) {
        return dp[y][x];
    }

    visited[y][x] = 1;
    int maxMoves = 0;

    for (int i = 0; i < 4; ++i) {
        int ny = y + dy[i] * board[y][x];
        int nx = x + dx[i] * board[y][x];
        maxMoves = max(maxMoves, DFS(ny, nx, board, dp, visited));
    }

    visited[y][x] = 0;
    dp[y][x] = maxMoves + 1;
    return dp[y][x];
}

int main() {
    cin >> r >> c;

    Board board(r, vector<int>(c, -1));
    Board visited(r, vector<int>(c, 0));
    Board dp(r, vector<int>(c, -1));

    for (int y = 0; y < r; ++y) {
        string cur;
        cin >> cur;
        for (int x = 0; x < c; ++x) {
            if (cur[x] == 'H') {
                board[y][x] = -1;
            } else {
                board[y][x] = cur[x] - '0';
            }
        }
    }

    cout << DFS(0, 0, board, dp, visited) << "\n";
    return 0;
}

그리고 비스킷님도 새해복 많이 받으세요 ㅎㅎ

감사합니다.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다. 비스킷님.

재귀 함수의 설계에서 기저 조건의 처리 방식과 재귀호출 내의 논리 구조는 문제 해결의 정확성에 큰 영향을 미칠 수 있습니다. 설명해주신 두 코드의 차이점은 재귀 호출 시 이동거리를 추가하는 시점과 방식에 있습니다. 이러한 차이가 일어날 수 있는 주요 이유는 다음과 같습니다:

재귀 호출의 깊이: 재귀 호출 시점에 이동거리를 더하는 경우, 모든 호출 스택마다 값이 누적됩니다. 반면, 기저조건을 달성한 후 값들을 역으로 처리할 경우, 실제 처리된 경로를 기준으로 누적되게 됩니다.
기저 조건 처리의 불일치: 기저 조건 처리 방식이 다르다면, 두 코드 간의 단일 호출 또는 경로가 전혀 다르게 평가될 수 있습니다. 특히 특정 조건 하에서 의도하지 않은 경로로 이동할 가능성이 있습니다.
오류의 전파: 재귀 깊이에서 조금의 오류나 잘못된 이동 거리가 계속해서 누적된다면, 최종 결과에 큰 영향을 미칠 수 있습니다.

이러한 논리적 차이점이 코드의 실행 결과에 미묘한 영향을 미치며, 특정 테케의 실패로 이어질 수 있습니다. 따라서 코드를 더 깊이 분석하면서 각 단계별로 왜 특정 이동거리가 발생하는지 추적해보는 것도 중요합니다.

기존 질문 중 유사한 토픽을 다루고 있는 질문이 있으니 참고해 보실 수 있습니다:
- 1-K 질문드립니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변

7-C 질문있습니다.