7-c 질문드립니다

10-Week C++ Coding Test | Algorithm Coding Test

7-C

Resolved

Written on

안녕하세요 dp 없이 dfs로 풀었는데 왜 틀렸는지 모르겠습니다. 그리고 Int 형 재귀는 아무리 봐도.. 떠오르기 힘든데 (외판원 순회 문제도 아직 이해를 하지 못했습니다 ㅜㅜ) int 재귀를 잘 이해하는 방법이 있을까요?

#include <bits/stdc++.h>
using namespace std;
int t,a,d[54][54];
string s; 
char b[54][54];
bool check[54][54];
int ans[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);
}  
void down(int y,int x){
    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;

        if(!in(ny, nx) || b[ny][nx] == 'H') continue;
        if(check[ny][nx]){
            cout << -1 << "\n";
            exit(0);
        }

        d[ny][nx]=max(d[ny][nx],d[y][x]+1);
        down(ny,nx);
        
    }
    check[y][x] = 0;

}
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";
    d[1][1]=1;
    down(1,1);
    int ret=0;
    for (int i=1;i<=t;i++){
        for (int j=1;j<=a;j++){
            ret=max(ret,d[i][j]);
        }
        
    }
}

c++코딩-테스트

Answer 2

kundol

Instructor

안녕하세요 ㅎㅎ

dp 없이 dfs로 풀었는데 왜 틀렸는지 모르겠습니다

-> 일단 시간초과 때문에 dfs는 안됩니다. DP로 풀어주세요. (시간초과가 나면 중간에 호출스택이 터져서 멈추는 등으로 틀리는 경우의 수도 있습니다. )

int 재귀를 잘 이해하는 방법

처음에 DP가 어렵긴하죠 ㅠㅠ

팁을 드리면 다음과 같습니다.

먼저 작은 예제로 손으로 그려보기부터 시작하는게 좋습니다.

ex) 팩토리얼, 피보나치 수열처럼 단순한 문제부터 호출 트리(call tree)와 리턴값이 어떻게 전달되는지 다이어그램으로 그려 보세요.

그게 된다음 -> 외판원순회를 보면서 고민해봐야 되는데요.

먼저 재귀함수는 결국 “언제 더 내려가지 않고 바로 값을 리턴할지”가 핵심입니다.

if (S == 모두 방문) return cost; 처럼 종료 조건을 딱 정하고,

그 뒤의 return dfs(…) + 추가 비용; 구조를 이해하는게 중요합니다.

해당 dfs가 어떤 값을 주어야 -> 이 외판원순회가 될 수 있지? 하면서 말이죠. 정점을 3개로 최소화 시킨 다음에 생각을 하는게 좋습니다. (처음부터 10개 등 많은 정점을 기반으로 하면 헷갈립니다.)

사실 int타입의 DP는 재귀 호출로부터 값을 받아서 더하면서 상위 호출로 올려보내는 경우가 많습니다. 이 때 최소값을 찾는다면 코드 한 줄(ans = min(ans, cost);)이 추가되는 것이죠.

int타입은 + 가 되는경우가 많다 & 최소값을 찾는다면 ans = min(ans, cost); 이런식으로 return 값을 주는 경우가 많다 라는 포인트를 잡고 가시면

익숙해질것입니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

communityai8509

안녕하세요, 인프런 AI 인턴입니다.

ililil님, 질문해주신 내용에 대해 답변 드리겠습니다. 우선, 주어진 코드에서 잘못된 부분과 개선할 수 있는 부분에 대해 설명드릴게요.

코드 문제점 및 해결방법

dp 없이 dfs 사용:
- 현재 코드에서는 ‘visited’ 배열(= check 배열)이 무한 루프 방지를 위한 Priming이 정상적으로 작동하고 있지 않으며, 주어진 문제에서의 이동 가능 혹은 불가능 위치와 조건을 잘못 처리하고 있습니다. DFS 방식에서는 특정 조건에 대해 재탐색 시 불필요한 루프가 발생할 수 있습니다.
정확한 방문 처리:
- 새로 방문한 좌표 (ny, nx) 에 대해 check 배열을 올바르게 처리해야 합니다. 해당 위치를 재탐색과 비교를 위해 특정 조건을 만족할 시 올바르게 check 처리하여 무한 반복을 방지해야 합니다.
반환형 및 fucntion 매개변수:
- int 형이나 void 형 함수에서의 적절한 return 사용을 통하여 각 자식 처리 후 부모와 비교할 수 있도록 Dijkstra의 방식으로 이동이 이루어지게 해야 합니다.
재귀적 이해 강화:
- 재귀적인 문제 해결 방법은 처음에는 어렵게 느껴질 수 있습니다. 이를 감안해 재귀를 적절히 이해하고 각 호출마다의 로직을 벗어나지 않도록 충분한 디버깅 과정 및 출력을 통하여 이해를 도모해야 합니다.

유사 질문 및 추가 학습 자료

다음의 유사한 질문을 참고하시면 도움이 될 수 있습니다:

7-c 코드 질문입니다

이 링크에서는 비슷한 문제 상황과 솔루션 전략 등에 대한 토큰들을 확인하실 수 있습니다. 주어진 문제나 논리의 흐름에서 해결책을 찾는 방법에 대한 지식공유자의 해결법, 이해를 참고해 보면 좋을 것 같습니다.

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

Inflearn Community Q&A