BOJ/백준-2210-python

문제📖

풀이🙏

• 다섯 개의 줄에 다섯 개의 정수로 숫자판이 주어진다.
• 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다.
• 이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 0으로 시작하는 000123과 같은 수로 만들 수 있다.
• 만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 구하는 프로그램을 작성하라.
• 첫째 줄에 만들 수 있는 수들의 개수를 출력한다.

코드💻

# boj, 2210 : 숫자판 점프, python3
# 브루트포스 알고리즘, 그래프 탐색, 깊이 우선 탐색
import sys

def dfs(x, y, number, result):
    if len(number) == 6: 
        if number not in result: 
            result.append(number)
        return
        
    dx = [1, -1, 0, 0] 
    dy = [0, 0, 1, -1] 
    
    for k in range(4):
        ddx = x + dx[k]
        ddy = y + dy[k]
        
        if 0 <= ddx < 5 and 0 <= ddy < 5: 
            dfs(ddx, ddy, number + matrix[ddx][ddy], result)
            
def solve():
    result = []
    
    for i in range(5):
        for j in range(5):
            dfs(i,j,matrix[i][j], result)
    
    return len(result)

matrix = [list(map(str, sys.stdin.readline().split())) for _ in range(5)]
        
print(solve())

결과😎

출처 && 깃허브📝

boj
github