Python으로 푸는 백준 2210. 숫자판 점프

백준 2210. 숫자판 점프

주어진 격자판을 상하좌우로 이동하여 만들어 낼 수 있는 6자리의 수들 중

중복되지 않은 수들의 갯수를 반환하는 프로그램을 짜시오.

백준에서 푼 문제 리스트 보기

백준에서 문제 보기

Github에서 코드 보기

문제 조건

숫자판의 모든 지점에서 수를 만들어 낼 수 있다.

만들어진 6자리의 수는 서로 중복되지 않아야 한다.

문제 풀이

이 문제는 이해하기 쉽도록 재귀로 풀 수 있다. 주어진 입력값의 크기는 2차원 배열 5*5이므로 재귀로 풀어도 stackoverflow 에러가 나지 않기 때문에 해당 방법으로 문제를 풀었다. 문자의 길이가 6이 아니면 count를 더해 재귀한다. 현재의 문자의 길이가 6이 될때에 만들어진 수를 집합(set()) 컨테이너에 넣어서 중복을 제거해준다. board의 모든 지점에서 문자열을 만들어 집합에 넣어주었을 때, 해당 집합의 길이를 출력해주면 된다.

파이썬 코드

import sys
input = sys.stdin.readline
 
def checkNumber(board, pos, unique_numbers, current_number, count):
    rd = [-1, 0, 1, 0]
    cd = [0, 1, 0, -1]
    r, c = pos
 
    for i in range(4):
        temp_r = r + rd[i]
        temp_c = c + cd[i]
        if 0 <= temp_r < 5 and 0 <= temp_c < 5:
            next_number = current_number + str(board[temp_r][temp_c])
            if count == 5:
                unique_numbers.add(next_number)
            else:
                checkNumber(board, (temp_r, temp_c), unique_numbers, next_number, count + 1)
 
 
 
def solve(board):
    unique_numbers = set()
    for i in range(5*5):
        r = i // 5
        c = i % 5
        checkNumber(board, (r,c), unique_numbers, str(board[r][c]), 1)
    total_unique_count = len(unique_numbers)
    print(total_unique_count)
 
 
if __name__ == "__main__":
    lines = []
    for i in range(5):
        lines.append(input().strip().split())
    solve(lines)