심층 분석: 회문 및 연속 블록을 위한 재귀 솔루션

이 기사에서는 Perl Weekly Challenge #288의 두 가지 작업, 즉 가장 가까운 회문을 찾고 행렬에서 가장 큰 연속 블록의 크기를 결정하는 작업을 다룰 것입니다. 두 솔루션 모두 Perl과 Go에서 재귀적으로 구현됩니다.

목차

1. 가장 가까운 회문
2. 인접 블록
3. 결론

가장 가까운 회문

첫 번째 작업은 자신을 포함하지 않는 가장 가까운 회문을 찾는 것입니다.

가장 가까운 회문은 두 정수 사이의 절대 차이를 최소화하는 회문으로 정의됩니다.

후보가 여러 개인 경우 가장 작은 후보를 반환해야 합니다.

작업 설명

입력: 정수를 나타내는 문자열 $str.

출력: 문자열로 가장 가까운 회문.

예

• 입력: "123"
  출력: "121"

• 입력: "2"
  출력: "1"
  가장 가까운 회문 두 개가 있습니다: "1"과 "3". 따라서 가장 작은 "1"을 반환합니다.

• 입력: "1400"
  출력: "1441"

• 입력: "1001"
  출력: "999"

해결책

펄 구현

이 구현에서는 재귀적 접근 방식을 활용하여 원래 숫자와 동일하지 않은 가장 가까운 회문을 찾습니다. 재귀 함수는 원래 숫자 주변의 하한과 상한을 모두 탐색합니다.

• 현재 후보(하위 및 상위)가 유효한 회문인지(원본과 동일하지 않은지) 확인합니다.
• 두 후보 모두 유효하지 않으면 함수는 유효한 회문을 찾을 때까지 하위 후보를 반복적으로 감소시키고 상위 후보를 증가시킵니다.

이 재귀 전략은 검색 공간을 효과적으로 좁혀 문제의 제약 조건을 준수하면서 가장 가까운 회문을 식별할 수 있도록 합니다.

sub is_palindrome {
    my ($num) = @_;
    return $num eq reverse($num);
}

sub find_closest {
    my ($lower, $upper, $original) = @_;
    return $lower if is_palindrome($lower) && $lower != $original;
    return $upper if is_palindrome($upper) && $upper != $original;
    return find_closest($lower - 1, $upper + 1, $original) if $lower > 0;
    return $upper + 1;
}

sub closest_palindrome {
    my ($str) = @_;
    my $num = int($str);
    return find_closest($num - 1, $num + 1, $num);
}

구현으로 이동

Go 구현은 유사한 재귀 전략을 따릅니다. 또한 유효한 회문을 찾을 때까지 경계를 조정하기 위해 재귀를 사용하여 원래 숫자 주변의 후보를 확인합니다.

package main

import (
    "strconv"
)

func isPalindrome(num int) bool {
    reversed := 0
    original := num

    for num > 0 {
        digit := num % 10
        reversed = reversed*10 + digit
        num /= 10
    }

    return original == reversed
}

func findClosest(lower, upper, original int) string {
    switch {
        case isPalindrome(lower) && lower != original:
            return strconv.Itoa(lower)
        case isPalindrome(upper) && upper != original:
            return strconv.Itoa(upper)
        case lower > 0:
            return findClosest(lower-1, upper+1, original)
        default:
            return strconv.Itoa(upper + 1)
    }
}

func closestPalindrome(str string) string {
    num, _ := strconv.Atoi(str)
    return findClosest(num-1, num+1, num)
}

Hier ist die erweiterte Definition für den 인접 블록:

연속 블록

두 번째 작업은 모든 셀에 x 또는 o가 포함된 주어진 행렬에서 가장 큰 연속 블록의 크기를 결정하는 것입니다.

인접 블록은 블록의 다른 요소와 모서리(모서리뿐만 아니라)를 공유하는 동일한 기호를 포함하는 요소로 구성되어 연결된 영역을 만듭니다.

작업 설명

입력: x와 o를 포함하는 직사각형 행렬

출력: 가장 큰 연속 블록의 크기

예

• 입력:
  

  [
      ['x', 'x', 'x', 'x', 'o'],
      ['x', 'o', 'o', 'o', 'o'],
      ['x', 'o', 'o', 'o', 'o'],
      ['x', 'x', 'x', 'o', 'o'],
  ]
  

출력: 11
x를 포함하는 9개의 연속 셀 블록과 o를 포함하는 11개의 연속 셀 블록이 있습니다.

• 입력:
  

  [
      ['x', 'x', 'x', 'x', 'x'],
      ['x', 'o', 'o', 'o', 'o'],
      ['x', 'x', 'x', 'x', 'o'],
      ['x', 'o', 'o', 'o', 'o'],
  ]
  

출력: 11
x를 포함하는 11개의 연속 셀 블록과 o를 포함하는 9개의 연속 셀 블록이 있습니다.

• 입력:
  

  [
      ['x', 'x', 'x', 'o', 'o'],
      ['o', 'o', 'o', 'x', 'x'],
      ['o', 'x', 'x', 'o', 'o'],
      ['o', 'o', 'o', 'x', 'x'],
  ]
  

출력: 7
o를 포함하는 7개의 연속 셀 블록, o의 다른 2셀 블록 2개, x의 2셀 블록 3개, x의 3셀 블록 1개가 있습니다.

해결책

펄 구현

이 구현에서는 재귀적 깊이 우선 검색(DFS) 접근 방식을 활용하여 행렬에서 가장 큰 연속 블록의 크기를 결정합니다. 주요 함수는 방문 행렬을 초기화하여 탐색된 셀을 추적합니다. 각 셀을 반복하면서 방문하지 않은 셀을 발견할 때마다 재귀 DFS 기능을 호출합니다.

DFS 기능은 현재 셀에서 가능한 네 가지 방향(위, 아래, 왼쪽, 오른쪽)을 모두 탐색합니다. 동일한 기호를 공유하고 방문되지 않은 인접 셀에서 자신을 재귀적으로 호출하여 연속 블록의 크기를 계산합니다. 이 재귀적 방법은 각 셀이 한 번만 계산되도록 하면서 블록 크기를 효과적으로 집계합니다.

sub largest_contiguous_block {
    my ($matrix) = @_;
    my $rows = @$matrix;
    my $cols = @{$matrix->[0]};
    my @visited = map { [(0) x $cols] } 1..$rows;

    my $max_size = 0;

    for my $r (0 .. $rows - 1) {
        for my $c (0 .. $cols - 1) {
            my $symbol = $matrix->[$r][$c];
            my $size = dfs($matrix, \@visited, $r, $c, $symbol);
            $max_size = $size if $size > $max_size;
        }
    }

    return $max_size;
}

sub dfs {
    my ($matrix, $visited, $row, $col, $symbol) = @_;

    return 0 if $row < 0 || $row >= @$matrix || $col < 0 || $col >= @{$matrix->[0]}
                || $visited->[$row][$col] || $matrix->[$row][$col] ne $symbol;

    $visited->[$row][$col] = 1;
    my $count = 1;

    $count += dfs($matrix, $visited, $row + 1, $col, $symbol);
    $count += dfs($matrix, $visited, $row - 1, $col, $symbol);
    $count += dfs($matrix, $visited, $row, $col + 1, $symbol);
    $count += dfs($matrix, $visited, $row, $col - 1, $symbol);

    return $count;
}

구현으로 이동

Go 구현은 이러한 재귀적 DFS 전략을 반영합니다. 마찬가지로 행렬을 순회하고 재귀를 사용하여 동일한 기호가 있는 연속 셀을 탐색합니다.

package main

func largestContiguousBlock(matrix [][]rune) int {
    rows := len(matrix)
    if rows == 0 {
        return 0
    }
    cols := len(matrix[0])
    visited := make([][]bool, rows)
    for i := range visited {
        visited[i] = make([]bool, cols)
    }

    maxSize := 0

    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            symbol := matrix[r][c]
            size := dfs(matrix, visited, r, c, symbol)
            if size > maxSize {
                maxSize = size
            }
        }
    }

    return maxSize
}

func dfs(matrix [][]rune, visited [][]bool, row, col int, symbol rune) int {
    if row < 0 || row >= len(matrix) || col < 0 || col >= len(matrix[0]) ||
        visited[row][col] || matrix[row][col] != symbol {
        return 0
    }

    visited[row][col] = true
    count := 1

    count += dfs(matrix, visited, row+1, col, symbol)
    count += dfs(matrix, visited, row-1, col, symbol)
    count += dfs(matrix, visited, row, col+1, symbol)
    count += dfs(matrix, visited, row, col-1, symbol)

    return count
}

Conclusion

In this article, we explored two intriguing challenges from the Perl Weekly Challenge #288: finding the closest palindrome and determining the size of the largest contiguous block in a matrix.

For the first task, both the Perl and Go implementations effectively utilized recursion to navigate around the original number, ensuring the closest palindrome was found efficiently.

In the second task, the recursive depth-first search approach in both languages allowed for a thorough exploration of the matrix, resulting in an accurate count of the largest contiguous block of identical symbols.

These challenges highlight the versatility of recursion as a powerful tool in solving algorithmic problems, showcasing its effectiveness in both Perl and Go. If you're interested in further exploration or have any questions, feel free to reach out!

You can find the complete code, including tests, on GitHub.

위 내용은 심층 분석: 회문 및 연속 블록을 위한 재귀 솔루션의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!