깊이 우선 탐색(DFS) (2) - 여행경로

여행 경로

주어진 항공권을 모두 사용하여 ICN에서 출발하는 여행 경로를 찾는 문제

알파벳 순서가 앞서는 경로를 우선적으로 선택하고, 모든 항공권이 사용되어야 하며 모든 도시를 방문할 수 없는 경우는 없다.

풀이 전략

1. 그래프 생성

   항공권 정보를 바탕으로 인접 리스트 형태의 그래프를 생성한다. 각 공항에서 갈 수 있는 공항들을 알파벳 순으로 정렬한다.

2. DFS(깊이 우선 탐색)
   • 재귀적으로 경로를 탐색하며 모든 항공권을 사용했는지 확인한다.
   • 탐색 과정에서 경로를 기록하고, 가능한 경로를 사전순으로 반환한다.

3. 경로 완성

   모든 티켓이 사용된 경로를 반환하며, 여러 경로가 가능할 경우 알파벳 순서를 따른다.

알고리즘 풀이

unction solution(game_board, table) {
    const n = game_board.length;

    // 방향 벡터: 상, 하, 좌, 우
    const directions = [
        [-1, 0], [1, 0], [0, -1], [0, 1]
    ];

    // 블록 추출 함수 (DFS 기반)
    const extractBlock = (board, x, y, value) => {
        const block = [];
        const queue = [[x, y]];
        board[x][y] = -1; // 방문 표시
        block.push([x, y]);

        while (queue.length) {
            const [cx, cy] = queue.shift();

            for (const [dx, dy] of directions) {
                const nx = cx + dx;
                const ny = cy + dy;

                if (
                    nx >= 0 && ny >= 0 && nx < n && ny < n &&
                    board[nx][ny] === value
                ) {
                    board[nx][ny] = -1; // 방문 표시
                    queue.push([nx, ny]);
                    block.push([nx, ny]);
                }
            }
        }

        // 블록 정렬 및 기준점(0, 0)으로 이동
        block.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
        const [baseX, baseY] = block[0];
        return block.map(([bx, by]) => [bx - baseX, by - baseY]);
    };

    // 블록 회전 함수
    const rotateBlock = (block) => {
        return block.map(([x, y]) => [y, -x])
            .sort((a, b) => a[0] - b[0] || a[1] - b[1]);
    };

    // 블록 비교 함수
    const isSameBlock = (block1, block2) => {
        if (block1.length !== block2.length) return false;
        for (let i = 0; i < block1.length; i++) {
            if (block1[i][0] !== block2[i][0] || block1[i][1] !== block2[i][1]) {
                return false;
            }
        }
        return true;
    };

    // 보드에서 모든 블록 추출
    const findBlocks = (board, value) => {
        const blocks = [];
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (board[i][j] === value) {
                    blocks.push(extractBlock(board, i, j, value));
                }
            }
        }
        return blocks;
    };

    // 게임 보드의 빈칸 (0)을 블록으로 추출
    const emptySpaces = findBlocks(game_board, 0);

    // 테이블의 퍼즐 조각 (1)을 블록으로 추출
    const puzzleBlocks = findBlocks(table, 1);

    let filledSpaces = 0;

    // 빈칸과 퍼즐 조각 매칭
    for (const empty of emptySpaces) {
        for (let i = 0; i < puzzleBlocks.length; i++) {
            const puzzle = puzzleBlocks[i];

            let matched = false;

            for (let rotation = 0; rotation < 4; rotation++) {
                if (isSameBlock(empty, puzzle)) {
                    filledSpaces += puzzle.length;
                    puzzleBlocks.splice(i, 1); // 사용한 퍼즐 조각 제거
                    matched = true;
                    break;
                }
                puzzle = rotateBlock(puzzle); // 회전
            }

            if (matched) break;
        }
    }

    return filledSpaces;
}

시간 복잡도

1. 그래프 생성

   주어진 항공권을 정렬하는 데 O(Elog⁡E)의 시간이 소요된다. 여기서 E는 항공권의 수이다.

2. DFS 탐색

   각 항공권을 정확히 한 번씩 탐색하므로 O(E)의 시간이 소요된다.

결과적으로 시간 복잡도는 O(Elog⁡E)이다.