격자판의 숫자 이어 붙이기

최민수·2023년 5월 20일
0

알고리즘

목록 보기
61/94
from collections import deque

T = int(input())
answerCand = set()
grid = [[] for _ in range(4) for _ in range(4)]

def bfs(row, col):
    global grid
    temp = grid[row][col]
    start = [row, col, 1, temp]
    q = deque()
    q.append(start)

    while q:
        cur = q.popleft()
        curRow, curCol, curCnt, curStr = cur[0], cur[1], cur[2], cur[3]

        if curCnt == 7:
            answerCand.add(int(curStr))
            continue

        dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
        for xx, yy in zip(dx, dy):
            nxtRow, nxtCol = curRow+xx, curCol+yy
            if 0 <= nxtRow < 4 and 0 <= nxtCol < 4:
                q.append([nxtRow, nxtCol, curCnt+1, curStr+grid[nxtRow][nxtCol]])


for test_case in range(1, T + 1):
    answerCand.clear()
    grid = [[] for _ in range(4) for _ in range(4)]

    for i in range(4):
        nums = list(map(str, input().split()))
        for num in nums:
            grid[i].append(num)

    # BFS
    for row in range(4):
        for col in range(4):
            bfs(row, col)

    print("#" + str(test_case) + " " + str(len(answerCand)))

BFS 적용하면 바로 풀리는 문제였다. D4 문제치고는 너무 쉬운 문제였다.

grid 크기도 4*4 이고 문자열 길이도 7로 맞춰놔주어 모든 지점에서 bfs를 돌려도 시간초과를 걱정할 필요가 없었다.


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

profile
CS, 개발 공부기록 🌱

0개의 댓글