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

문제 링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB 

SW Expert Academy

 

모든 점에서 BFS를 돌리는데 이때 방문체크는 하지 않는다.

BFS를 돌리면서 각점의 숫자들을 이어붙여서 새로운 숫자를 만들고 7자리가 됐을 때 저장한다.

이때 같은 숫자는 체크하면 안되므로 set을 이용하여 중복제거를 했고 마지막에 set의 길이를 출력한다.

 

from collections import deque

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

tc = int(input())
def solv(t):
    global board, answer_set
    board = [list(input().strip().split()) for _ in range(4)]

    answer_set = set()
    for sx in range(4):
        for sy in range(4):
            bfs(sx,sy)
    print('#%d %d'%(t,len(answer_set)))

def bfs(sx,sy):
    global answer_set
    q = deque([(sx,sy,board[sx][sy])])
    while q:
        x,y,now = q.pop()

        if len(now) == 7:
            answer_set.add(now)
            continue

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if point_validator(nx,ny):
                q.appendleft((nx,ny,now+board[nx][ny]))
def point_validator(x,y):
    if x < 0 or y < 0 or x >= 4 or y >= 4:
        return False
    return True
for t in range(1,tc+1):
    solv(t)