[알고리즘|파이썬] 백준 2210 숫자판 점프

알고리즘

[알고리즘|파이썬] 백준 2210 숫자판 점프

따오잉 2025. 2. 4. 23:08

문제 링크: https://www.acmicpc.net/problem/2210

📌 문제 탐색하기

시간 제한: 2초
메모리 제한: 128 MB

구해야 하는 정답

0~9 숫자가 채워져 있는 5*5 숫자판에 임의의 위치에서 시작하여 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙여 만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 구해야 한다.

조건:

- 이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 됨.

- 0으로 시작하는 수 만들 수 있음. 예) 000123

예시:

111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 => 15

📌 풀이하기

1) 완전탐색이 가능할까?

시작점 경우의 수 = 25
이동: 상, 하, 좌, 우 4가지 방법으로 5번의 이동을 함 = 4^5 = 1024

즉, 최대 25 * 1,024 = 25,600 가지가 나오므로, 완전 탐색을 하여 모든 경우의 수를 구하여도 제한 시간 2초 안에 충분히 해결 가능함.

2) 6자리 숫자 만드는 방법 시뮬레이션

모든 경우의 수를 어떻게 만들어 낼 것인가?

1. 시작점을 (0, 0) ... (4, 4) 25가지를 돌아가며 선택한다

2. depth가 5가 될때까지 [상, 하, 좌, 우] 에 대해 탐색을 한다.

예를들어 아래와 같은 숫자판이 주어졌다고 가정을 했을때,

시작 점은 (0, 0)인 0부터, (4, 4)인 4까지 총 25개의 점을 돌아가면서 선택한다.

시작점을 (0, 0)으로 한 경우, depth = 0 일때 만들어진 숫자는 0이다.

다음 움직임으로는 상, 하, 좌, 우로 움직여 다음 숫자를 선택하고, depth 를 하나 더 증가시킬 것이다.

depth = 1
상: (-1, 0) -> 표를 벗어남
하: (1, 0) -> 5
좌: (0, -1) -> 표를 벗어남
우: (0, 1) -> 1

depth = 1 일때 만들어진 숫자는 05, 01 이다.

이때 각각의 경우 다시 상하좌우로 움직인다.

depth = 2
상: (0, 0) -> 1
하: (2, 0) -> 0
좌: (0, -1) -> 표를 벗어남
우: (1, 1) -> 6

05로 depth = 2 일때 만들어진 숫자는 051, 050, 056 이다.

depth =2
상: (-1, 0) -> 표를 벗어남
하: (2, 0) -> 6
좌: (0, 0) -> 0
우: (0, 2) -> 2

01로 depth = 2일때 만들어진 숫자는 016, 010, 012 이다.

이 과정을 depth = 5가 될때까지 만들어 6자리 숫자를 만들고, 서로 다른 숫자가 몇개인지를 출력하면 정답이다.

📌 코드 설계하기

1. input으로 board를 받음

2. 5*5 행렬을 돌면서 시작점 고르기

a. depth가 5 보다 작은지 확인

i. 상, 하, 좌, 우로 움직인다

ii. 움직였을 때 판을 벗어나는지 확인한다

iii. 판을 벗어나지 않는 경우 다음 위치에서 depth 를 하나 증가시켜 반복

b. depth가 5보다 큰 경우 만들어진 6자리 숫자 set에 저장

3. set의 크기 출력

* set은 중복된 값을 저장하지 않으므로, 서로 다른 숫자를 세어야하므로 적합한 자료구조

* 000123 과 같은 숫자도 6자리 숫자로 인정된다고 하였으므로 숫자 타입이 아니라 string 타입으로 숫자를 만드는 것이 편리함

📌 정답 코드

board = [[0] * 5] * 5
for a in range(5):
    board[a] = list(map(int, input().split()))

num_list = set()


def run(i, j, depth, num):
    if depth < 5:
        # 상 (i-1, j)
        if 0 <= i - 1 <= 4:
            run(i - 1, j, depth + 1, str(num)+str(board[i-1][j]))
        # 하 (i+1, j)
        if 0 <= i + 1 <= 4:
            run(i + 1, j, depth + 1, str(num)+str(board[i+1][j]))
        # 좌 (i, j-1)
        if 0 <= j - 1 <= 4:
            run(i, j - 1, depth + 1, str(num)+str(board[i][j-1]))
        # 우 (i, j+1)
        if 0 <= j + 1 <= 4:
            run(i, j + 1, depth + 1, str(num)+str(board[i][j+1]))
    else:
        num_list.add(num)
        return


for i in range(5):
    for j in range(5):
        start = board[i][j]
        run(i, j, 0, start)

print(len(num_list))