델타 탐색 이론 정리

델타 탐색이란

현재 위치를 기준으로 우-하-좌-상 으로 방향 전환이 고정되어 있다는 점을 활용하여 방향 전환 횟수 및 각 방향에서 움직이는 횟수에 대한 규칙을 사용하는 풀이이다.

예시 문제

swexpertacademy : 1954_달팽이 숫자 문제

문제풀이 아이디어

N자리 달팽이 숫자에서 방향 전환은 (2N-1)번 일어난다. 각 방향에서 움직임 횟수는 N ~ N-1 ~ N-1 ~ N-2 ~ N-2 ~ … ~ 2 ~ 2 ~ 1 ~ 1 순으로 발생한다는 것을 알 수 있습니다.

dr = (0, 1, 0, -1)
dc = (1, 0, -1, 0)

for tc in range(1, int(input()) + 1):
    N = int(input())

    snail = [[0] * N for _ in range(N)]
    r, c, d = 0, 0, 0

		# 1부터 N**2까지 차례로 순회하며 할당합니다.
    for num in range(1, N ** 2 + 1):
				# 해당 좌표에 해당 숫자를 할당합니다.
        snail[r][c] = num

				# 기본적으로 기존 방향을 유지하며 다음 좌표를 설정합니다.
        nr, nc = r + dr[d], c + dc[d]

				# 다음 좌표가 범위를 벗어나는 경우 또는 다음 좌표에 이미 숫자가 할당된 경우 방향을 전환합니다.
        if nr < 0 or nr >= N or nc < 0 or nc >= N or snail[nr][nc] != 0:
						# 아래와 같이 방향 전환 좌표를 설정하면 3 => 0으로의 방향 전환이 가능합니다.
            d = (d + 1) % 4
            nr, nc = r + dr[d], c + dc[d]

				# 위에서 계산한 다음 좌표를 현재 좌표로 최신화한 후 다음 반복으로 넘어갑니다.
        r, c = nr, nc

    print(f'#{tc}')
    for ans in snail:
        print(*ans)

달팽이 문제 다른 풀이

dr = [0, 1, 0, -1]  #우하좌상
dc = [1, 0, -1, 0]

for tc in range(1, int(input())+1):
    N = int(input())
    snail = [[0 for _ in range(N)] for _ in range(N)]

    d = 0  # 방향
    num = 0  # 달팽이 안에 넣을 숫자
    r = 0  # 행 좌표
    c = -1  # 시작 cell은 0이여야하는데, 아래코드로 시작하면 (0, 1)에서 시작. 따라서 (0,0) 옆 왼쪽의 가상의 칸에서 시작한다

    for i in range(N * 2, 1, -1):  # 방향바꾸기 횟수 2N-1
        for _ in range(i // 2):  # 각 방향에서 움직임 횟수
            num += 1
            r += dr[d % 4]
            c += dc[d % 4]
            snail[r][c] = num
        d += 1  # 방향 바꾸기

    print(f'#{tc}')
    for ans in snail:
        print(*ans)

예전에 풀었던 백준 7569. 토마토 코드

import sys
from collections import deque

m,n,h = map(int,input().split())
graph = []
for i in range(h):
    graph.append([list(map(int,input().split())) for j in range(n)])
dx = [1,-1,0,0,0,0]
dy = [0,0,1,-1,0,0]
dz = [0,0,0,0,1,-1]

Q = deque()
for i in range(len(graph)):
    for j in range(len(graph[0])):
        for k in range(len(graph[0][0])):
            if graph[i][j][k] == 1:
                Q.append([i,j,k])
# i j k = h, m, n
def bfs():
    while Q:
        z,x,y = Q.popleft()
        for i in range(6):
            nz,nx,ny = z+dz[i], x + dx[i], y + dy[i]
            if nz <0 or ny <0 or nx<0 or nz>=h or nx>=n or ny >= m:
                continue
            if graph[nz][nx][ny] == 0:
                graph[nz][nx][ny] = graph[z][x][y] + 1
                Q.append([nz,nx,ny])

bfs()
days = 0
for lst in graph:
    for i in lst:
        for j in i:
            if j == 0:
                print(-1)
                exit()
            else:
                if j > days:
                    days = j
print(days-1)