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

2819. 격자판의 숫자 이어 붙이기

원래 문제 풀이

기존에는 답이 자꾸 9로 나와서 실패했었다.

from collections import deque
t = int(input())

for p in range(1, t + 1):

    def bfs(x, y):
        q = deque([(x, y)])
        now = arr[x][y]

        while q:
            a, b = q.popleft()

            dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
            for i in range(4):
                nx = a + dx[i]
                ny = b + dy[i]

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

                if 0 <= nx < 4 and 0 <= ny < 4:
                    now += arr[nx][ny]
                    q.append([nx, ny])


    arr = [list(input().split()) for _ in range(4)]
    num = set()

    for k in range(4):
        for j in range(4):
            bfs(k, j)

    print(f"#{p} {len(num)}")

BFS로 문제 풀이

• BFS로 풀이
• now를 deque안에 넣어 같이 관리했더니 정답이 나왔다.
  그리고, now의 길이가 7일때 return을 하면 더이상 이동하지 않기 때문에 continue를 이용해 계속 이동할 수 있게 하였다.

from collections import deque
t = int(input())

for p in range(1, t + 1):


    def bfs(x, y):
        q = deque([(x, y, arr[x][y])])

        while q:
            a, b, now = q.popleft()

            dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
            for i in range(4):
                nx = a + dx[i]
                ny = b + dy[i]

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

                if 0 <= nx < 4 and 0 <= ny < 4:
                    q.append([nx, ny, now + arr[nx][ny]])


    arr = [list(input().split()) for _ in range(4)]
    num = set()

    for k in range(4):
        for j in range(4):
            bfs(k, j)

    print(f"#{p} {len(num)}")

DFS로 문제 풀이

t = int(input())

for p in range(1, t + 1):

    def dfs(x, y, now):

        if len(now) == 7:
            num.add(now)
            return

        dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < 4 and 0 <= ny < 4:
                dfs(nx, ny, now + arr[nx][ny])


    arr = [list(input().split()) for _ in range(4)]
    num = set()

    for k in range(4):
        for j in range(4):
            dfs(k, j, arr[k][j])

    print(f"#{p} {len(num)}")