[백준] 2210번 숫자판 점프

문제

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

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

입력

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

출력

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

예제 입력 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

제출답안

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def dfs(x, y, dx, dy, graph, number, answer):
    number += str(graph[x][y])

    if len(number) == 6:
        if number not in answer:
            answer.add(number)
        return

    for i in range(4):
        a = x + dx[i]
        b = y + dy[i]
        if 0 <= a < 5 and 0 <= b < 5:
            dfs(a, b, dx, dy, graph, number, answer)


def solution():
    n, m = 5, 5
    graph = [list(map(int, input().split())) for _ in range(5)]
    dy = [0, 0, 1, -1]
    dx = [1, -1, 0, 0]
    answer = set([])
    for i in range(n):
        for j in range(m):
            dfs(i, j, dx, dy, graph, '', answer)
    print(len(answer))
solution()

1. 먼저 재귀 깊이를 설정한다.
2. dfs 함수를 만든다.
   1. dfs를 돌면서 방문하는 곳의 숫자를 계속 누적시킨다.
   2. 누적시킨 변수의 길이가 6이면 answer에 있는지 없는지 확인하고 있으면 나가고 없으면 add 시킨다.
   3. 6이 안된다면 상,하,좌,우로 돌면서 a,b가 범위 안에 있으면 dfs를 다시 돌리면서 연결된 곳으로 방문하여 숫자를 누적한다.
3. solution함수를 만든다.
   1. n,m은 5,5가 고정이지만 따로 선언하였다.
   2. graph 에 입력받는 값들을 이중리스트로 생성한다.
   3. dy, dx로 이동방향 리스트를 만든다.
   4. answer는 set으로 생성하여 in을 비교하는데 일반 리스트보다 in을 비교할 때 set을 사용하면 시간을 훨씬 단축할 수 있다고 한다.
      1. 그래서 dfs를 사용할 때 append 대신 set이기 때문에 add를 사용하였다.
   5. for loop를 돌면서 dfs를 실행한다.
   6. 마지막으로 answer의 길이를 출력한다.