퀴즈 정답

문제

• NxN 크기의 격자 모양 방들이 존재하고, 각 방안에는 1~9 사이의 숫자들이 있습니다.

• 임의의 방에서 시작하여 인접한 방들로 이동할 수 있으며 이동시에는 해당 방에 쓰여있는 숫자들을 더하면서 이동하게 됩니다.

• 단, 다음 방으로 이동할때에는왼쪽 또는 위쪽으로는 이동할 수 없고,
  오른쪽 또는 아래쪽으로 인접한 방으로만 이동 가능하며 방향 전환은 한번만 가능합니다.

• 특정한 숫자 S가 주어질때 임의의 방에서 시작하여 이동할 때 이동 경로의 숫자 총합이 S가 되는 모든 경우를 찾아서 한 행에 하나의 경로씩 출력해주세요.

• 각 경로들 사이에서의 순서는 상관없지만 하나의 경로 안에서 숫자들의 순서는 이동 경로 그대로 출력되어야 합니다

풀이

• 최소거리를 이동해야 함으로 BFS를 활용
• queue에 [x,y좌표 , 현재방향 , 합 ,좌표경로 , 방향전환횟수] 넣어주기
  [x, y, d, sum, field, cnt]

코드

# 방향전환은 한번
# 이동 오른쪽 아래
from collections import deque
N = 4
S = 11
dx = [0, 1]
dy = [1, 0]
arr = [
    [2,4,2,6],
    [6,6,4,2],
    [2,2,1,2],
    [4,4,5,3]
]
def BFS(queue):
    global N, visited, dx, dy
    while queue:
        x, y, d, sum, field, cnt = queue.popleft()
        # 도착한 경우
        if sum == S and cnt < 3:
            print("출력:", field)
        for i in range(2):
            ndr = x + dx[i]
            ndc = y + dy[i]
            # 범위안에 들어옴
            if 0 <= ndr < N and 0 <= ndc < N and visited[ndr][ndc] == False:
                visited[x][y] = True
                #print(ndr, ndc, "sum",sum, arr[ndr][ndc] ,"" ,field)
                if d == i:
                    queue.append([ndr, ndc, i, sum + arr[ndr][ndc], field + " " + str(arr[ndr][ndc]), cnt])
                else:
                    queue.append([ndr, ndc, i, sum + arr[ndr][ndc], field + " " + str(arr[ndr][ndc]), cnt + 1])
for i in range(N):
    for j in range(N):
        # 방문 확인용 배열
        visited = [[False for _ in range(N)] for _ in range(N)]
        queue = deque()
        visited[i][j] = True
        queue.append([i, j, -1, arr[i][j], str(arr[i][j]), 0])
        BFS(queue)