[SWEA] 2819_격자판의 숫자 이어 붙이기

📕 문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB 

SW Expert Academy

 

💡 풀이법

1. 거쳤던 칸을 다시 거쳐도 되기 때문에 방문처리가 필요없는 dfs 문제이다.

2. 만들 수 있는 서로 다른 수들을 담을 answers 리스트를 만든다.

3. dfs의 인자로 지금까지의 숫자 개수를 가지고 다니면서 개수가 7이 될때, answers 리스트 안에 없는 숫자라면 answers안에 담는다.

4. answer의 길이를 출력한다.

 

dxy = [(1,0), (0,1), (-1,0), (0,-1)]
def dfs(x, y, num, c):
    if c == 7:
        if num not in answers:
            answers.add(num)
        return

    for dx, dy in dxy:
        nx, ny = x + dx, y + dy

        if -1 < nx < 4 and -1 < ny < 4:
            dfs(nx, ny, num + matrix[nx][ny], c+1)

T = int(input())
for tc in range(1, T+1):
    matrix = [input().split() for _ in range(4)]
    answers = set()
    for i in range(4):
        for j in range(4):
            dfs(i, j, matrix[i][j], 1)

    print('#{} {}'.format(tc, len(answers)))