[SWEA] 2819. 격자판의 숫자 이어붙이기/Python - D4

❓문제

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

SW Expert Academy

성능 요약

메모리: 76,160 KB, 시간: 333 ms

✍🏻풀이

우선 문제에서 상하좌우로 움직일 수 있다고 했으므로 BFS와 DFS가 바로 생각날 것이다.
이 문제는 DFS로 풀면 된다.

각각의 위치마다 만들 수 있는 숫자를 상하좌우로 탐색한다. 그리고 길이가 7이 되었을 때 이 숫자가 이미 만들어진 수인지 아닌지 판별하여 nums에 기록해 둔다.

그리고 마지막으로 nums의 길이를 출력하면 만들 수 있는 숫자의 개수를 알 수 있다.

💻코드

T = int(input())

def dfs(y, x, res):
    global nums
    if len(res) == 7:
        if res not in nums:
            nums.add(res)
        return

    if 0 <= y < 4 and 0 <= x < 4:
        dfs(y + 1, x, res + board[y][x])
        dfs(y - 1, x, res + board[y][x])
        dfs(y, x + 1, res + board[y][x])
        dfs(y, x - 1, res + board[y][x])


for tc in range(1, T + 1):
    board = [input().split() for _ in range(4)]
    nums = set()

    for y in range(4):
        for x in range(4):
            dfs(y, x, "")

    print(f"#{tc} {len(nums)}")

📍후기

처음에 dfs 파라미터에 cnt로 개수를 셌는데 생각해 보니 굳이 그럴 필요가 없었다. 그리고 마지막도 굳이 ans를 써서 개수를 일일이 셀 필요가 없었다. 그렇게 실패하고 몇 개를 수정하고 나니 바로 통과~~