[SWEA/D4] 2819 : 격자판의 숫자 이어 붙이기 python

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AV7I5fgqEogDFAXB&categoryId=AV7I5fgqEogDFAXB&categoryType=CODE&problemTitle=&orderBy=SUBMIT_COUNT&selectCodeLang=PYTHON&select-1=4&pageSize=10&pageIndex=1&&&&&&&&&&

SW Expert Academy

 

35분만에 풀었다.

뿌듯 

 

from collections import deque
T = int(input())
# 방향벡터
dx = [-1,1,0,0]
dy = [0,0,-1,1]

# 행, 열, 현재까지 만들어진 문자열을 인자로 받는 bfs함수
def bfs(a,b,now):
	# 문자열 집합을 전역변수로 선언
    global numbers
    
    # bfs 수행에 필요한 큐 생성
    q = deque()
    q.append((a,b,now))
    
    while q:
        x,y,now=q.popleft()
        # 현재 문자열의 길이가 7이라면 집합에 추가
        # 더 이상 탐색할 필요 없으니 continue
        if len(now)==7:
            numbers.add(now)
            continue
        # 동서남북으로 이동하면서 격자판의 범위를 넘지 않는다면
        # 무조건 큐에 추가함(방문한 곳도 재방문이 가능하니까)
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<n and 0<=ny<n:
                q.append((nx,ny, now+board[nx][ny]))
                
for test_case in range(1, T + 1):
	# 격자판 한 면의 길이
    n = 4
    
    # 격자판을 입력받음
    board = []
    for i in range(n):
        board.append(list(input().split()))
    
    # 서로 다른 7자리 문자열을 저장하기 위한 집함
    numbers = set()
    # 격자판의 모든 자리에서 bfs를 수행함
    for i in range(n):
        for j in range(n):
            res = bfs(i,j,board[i][j])
            
    # 집합에 저장된 문자열의 개수를 출력함
    print('#%d'%test_case,len(numbers))