[백준] 2210번 숫자판 점프 - Python / 알고리즘 중급 2/3 - 브루트 포스 - 문제

---

---

---

💡 문제

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

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

입력

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

출력

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

---

💭 접근

매우 간단한 DFS 문제이다. 이때 문제에서 주어진 바와 같이 한번 거쳤던 칸을 다시 거쳐도 되므로 방문처리를 하지 않는다.

그리고, 5 x 5의 모든 칸에서 시작하며 여섯 자리의 수가 완성되면 파이썬의 set()을 사용하여 이미 저장되어있는 여섯 자리의 수가 중복되어 저장되지 않도록 하면 된다.

---

📒 코드

def dfs(x, y, depth, digits):
    if depth == 6:
        ans.add(digits)
        return
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < 5 and 0 <= ny < 5:
            dfs(nx, ny, depth + 1, digits + graph[nx][ny])

graph = [list(input().split()) for _ in range(5)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

ans = set()
for i in range(5):
    for j in range(5):
        dfs(i, j, 1, graph[i][j])
print(len(ans))

---

💭 후기

매우 간단한 DFS 문제였다.

---

🔗 문제 출처

https://www.acmicpc.net/problem/2210

---