c언어로 알고리즘퍼즐68 (프리렉) 풀기 Q48 급할수록 돌아가라

[문제] 가로 6, 세로 5인 맵이 있다. (0, 0)에서 출발하여 (6, 5)에 가려고 한다.

단, 동일 가로행 및 세로열을 3회 이상 지나지 않는다고 할 때, 최장으로 갈 수 있는 이동거리는?

(동일 길을 2번 지나는 것은 가능하나, 각각 1번씩 카운트한다.)

예를 들어 아래 그림에서 첫번째 경로는 가능하고 (거리는 13) 두번째, 세번째 경로는 불가능하다.

 

[알고리즘]

각각의 가로행 및 세로열을 지난 횟수를 배열에 저장한다.

가로행은 총 6개 있으므로 cntX[6] 배열에 저장하고, 세로열은 총 7개 있으므로 cntY[7] 배열에 저장한다.

점이 (x, y)에서 (x + 1, y) 또는 (x -1, y)로 이동하면 cntX[y]가 1회 증가하고,

점이 (x, y)에서 (x, y+1) 또는 (x, y -1)로 이동하면 cntY[x]가 1회 증가한다.

cntX, cntY 내 원소들이 2가 넘지 않도록 하면서 이동한다.

아래는 코드

#include <stdio.h>
#define X 6
#define Y 5
int cntX[Y + 1] = { 0 };
int cntY[X + 1] = { 0 };
typedef struct point {
    int x, y;
} point;
enum dir { E, W, S, N };
void solve(point* p, int* maxL, int depth);
void movePoint(point* p, int dir);
void returnPoint(point* p, int dir);
int main() {
    point p = { 0, 0 };
    int maxLength = 0;
    int depth = 0;

    solve(&p, &maxLength, depth);
    printf("최장거리 = %d\n", maxLength);
}
void solve(point* p, int* maxL, int depth) {
    if (p->x < 0 || p->x > X)	// 경계 밖으로 벗어나면 리턴
        return;
    if (p->y < 0 || p->y > Y)	// 경계 밖으로 벗어나면 리턴
        return;
    if (cntX[p->y] > 2 || cntY[p->x] > 2)	// 2회 초과하여 지나가면 리턴
        return;
    if (p->x == X && p->y == Y) {	// 목표 지점에 도달한 경우
        *maxL = depth > *maxL ? depth : *maxL;
        return;
    }
    // 동서남북 4개 방향 중 1가지 방향으로 이동한다.
    for (int dir = E; dir <= N; dir++) {
        movePoint(p, dir);
        solve(p, maxL, depth + 1);
        returnPoint(p, dir);
    }
}
void movePoint(point* p, int dir) {
    if (dir == E) {
        p->x++;
        cntX[p->y]++;
    }
    else if (dir == W) {
        p->x--;
        cntX[p->y]++;
    }
    else if (dir == S) {
        p->y--;
        cntY[p->x]++;
    }
    else {
        p->y++;
        cntY[p->x]++;
    }
}
void returnPoint(point* p, int dir) {
    if (dir == E) {
        p->x--;
        cntX[p->y]--;
    }
    else if (dir == W) {
        p->x++;
        cntX[p->y]--;
    }
    else if (dir == S) {
        p->y++;
        cntY[p->x]--;
    }
    else {
        p->y--;
        cntY[p->x]--;
    }
}

정답은 25.

 

어떤 경로로 지나가는지 살펴보면 상당히 많은 경우의 수가 존재한다.

정답 중 1가지

정답 중 1가지