7699

static int y, x;
static char board[20][20] = { 0, };
static int visit[255] = { 0, };
 
static bool check(int ny, int nx)
{
    if (ny < 0 || ny >= y)
        return false;
    else if (nx < 0 || nx >= x)
        return false;
    else if (visit[board[ny][nx]])
        return false;
    else
        return true;
}
 
static int __solution(int sy, int sx)
{
    if (!check(sy, sx))
        return 0;
    visit[board[sy][sx]] = 1;
     
    int up = 1 + __solution(sy - 1, sx);
    int down = 1 + __solution(sy + 1, sx);
    int left = 1 + __solution(sy, sx - 1);
    int right = 1+ __solution(sy, sx + 1);
    int max1 = up > down ? up : down;
    int max2 = left > right ? left : right;
    visit[board[sy][sx]] = 0;
    return max1 > max2 ? max1 : max2;
}
 
static int solution(void)
{
    scanf("%d %d", &y, &x);
    for (int i = 0; i < y; i++)
        scanf("%s\n", board[i]);
 
    memset(visit, 0, sizeof(visit));
    return __solution(0, 0);
}

 

입력으로 받은 2차원 배열을 어떻게 돌아다녀야 최소비용으로 최대의 가치를 얻을 수 있는지 해결하는 문제다.

일단은 재귀 형태로 구현을 하였다. (재귀가 아닌 일반 함수로 구현해보는 것도 좋을 것 같다.)

 

일단 입력으로 받은 경로로 갈 수 있는지 확인한다.

배열의 범위를 벗어난다던지 이미 본 특산품이라면 가지 않고 반환한다. 0을 반환하는 이유는 더 이상 볼 특산품이 없기 때문이다.

반대로 갈 수 있는 경로라면 먼저 이 특산품을 봤다라고 기록을 한다.

그리고 위, 아래, 왼쪽, 오른쪽에 대해서 재귀적으로 재실행하고 이것이 모두 끝나면 현재 위치에 대해서 본 특산품에 대한 정보를 지운다. 아래를 예시로 이에 대해 설명하자면,

 

A B C B

D E D C

 

먼저 A에서 B로 가는 것을 먼저 실행했다하면 B에서 C로 가고 C에서 B로 가야하는데 갈 수 없으므로 다시 C로 되돌아 가게 된다. 그런데 방금 B를 갈 수 없었기에 B에 대한 정보를 지워버리면 현재 C에서 왼쪽 B로 다시 갈 수 있게 된다.

그래서 이러한 문제를 해결하기 위해 현재 C에 대해서 모든 경로를 다 탐색하고난 뒤 에 이를 해제하도록 한 것이다.

 

이번에는 return 하는 값에 대해서 보겠다.

아까는 A에서 오른쪽으로 간 것이다. 그 위치에 B에대해서 모든 경로를 탐색 한 뒤에 B에 대한 정보는 제거되고,

A에서 D로 간다. 그리고 다시 재귀를 하게 되는데,

모든 경로에 대해서 볼 수 있는 특산품의 최대 값을 구하여 반환하는 것이다.