[백준] 2210번 - 숫자판 점프

📩 출처

문제

5×5 크기의 숫자판이 있다. 각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 0으로 시작하는 000123과 같은 수로 만들 수 있다.

숫자판이 주어졌을 때, 만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

👉 생각

• 깊이 우선 탐색을 하는 함수 dfs를 만들어준다. 스택에 좌표값과 이동한 횟수, 숫자를 차례대로 붙여준 값을 담고 뒤에서부터 하나씩 꺼내서 깊이우선 탐색을 한다.
• 숫자가 6자리가 되면 중복체크를 한 이후에 lst라는 배열에 담아주고 lst를 반환해준다.
• 모든 좌표에서 나온 lst를 answer에 중복체크를 한 이후에 넣어주고 길이를 출력해준다!

def dfs(x, y):
    stack = [(x,y,0, arr[x][y])]
    lst = []
    while stack:
        x, y, cnt, six = stack.pop()
        if cnt == 5 and six not in lst:
            lst.append(six)

        for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < 5 and 0 <= ny < 5 and cnt < 5:
                stack.append((nx, ny, cnt + 1, six+arr[nx][ny]))
    return lst

arr = [list(input().split()) for _ in range(5)]
answer = []
for i in range(5):
    for j in range(5):
        result = dfs(i,j)
        for res in result:
            if res not in answer:
                answer.append(res)

print(len(answer))