백준: 2210 숫자판 점프

문제

2210번: 숫자판 점프

 

문제 풀이

 5x5 크기의 숫자판이 있을 때, 임의의 위치에서 부터 시작하여 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이때 서로 다른 여섯 자리의 수들의 개수를 구하는 문제이다. 답을 찾기 위해서는 각 그래프의 좌표마다 DFS를 통해, 방문가능한 경로를 탐색하고 6자리가 되면 숫자를 기록하면 쉽게 문제를 풀 수 있다.

 

코드

from sys import stdin


def dfs(x, y, num):

    if len(num) == 6:
        answer.add(num)
        return

    for dx, dy in dirs:
        next_x, next_y = x + dx, y + dy

        if 0 <= next_x < 5 and 0 <= next_y < 5:
            dfs(next_x, next_y, num + graph[next_x][next_y])


if __name__ == '__main__':
    answer = set()
    dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))
    graph = [list(stdin.readline().split()) for _ in range(5)]

    for i in range(5):
        for j in range(5):
            dfs(i, j, '')
    print(len(answer))