문제

입력

다섯 개의 줄에 다섯 개의 정수로 숫자판이 주어진다.

출력

첫째 줄에 만들 수 있는 수들의 개수를 출력한다.

입력 예시 1

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 2 1
1 1 1 1 1

출력 예시 1

15

문제 이해

처음에는 DFS로 풀어야하는 게 맞나 싶었다. 순열/조합으로 푸는 문제라고 생각했다. 그런데 문제를 보니 그냥 시뮬레이션+DFS로 풀라고 풀어서 설명해준다.

"임의의 위치에서 시작해서 인접해 있는 네 방향으로 이동, 각 칸에 적혀있는 숫자를 붙여서 6자리 수를 만든다" -> 시뮬레이션과 DFS로 숫자를 만들고, 탈출조건은 숫자가 6자리일때.

"만들 수 있는 서로 다른 여섯 자리의 개수를 구하시오" -> 모든 위치에서 수를 구하고, 중복된 것은 set()으로 제외시킨다.

코드

# 백준 2210번 숫자판 점프

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 방향벡터 동-서-남-북순
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# DFS 사용자함수
def DFS(y, x, string):
    global result

    if len(string) == 6:
        result.append(string)
        return
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < 5 and 0 <= ny < 5:
            DFS(ny, nx, string + str(number_map[ny][nx]))



# 0. 입력 및 초기화
number_map = []
result = []

# 1. 맵 정보 입력
for i in range(5):
    number_map.append(list(map(int, input().split())))

# 2. DFS호출
for i in range(5):
    for j in range(5):
        value = str(number_map[i][j])
        DFS(i, j, value)

# 3. 출력
result = set(result) # 중복걸러주기
print(len(result))