[SWEA] 4112 이상한 피라미드 탐험 파이썬

문제 링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWJHmLraeEwDFAUH& 

SW Expert Academy

 

4방향으로 BFS 돌려서 풀었다.

최대 숫자는 10000이므로 2차원 배열로 했을데 141x141이면 다 채울수 있다.

1

2 3

4 5 6

7 8 9 10

....

이런식으로 번호 넣은 배열 만들면서 각 칸의 번호가 몇행 몇열에 저장되어 있는지도 따로 배열로 저장했다.

이동은 6가지 방향으로 가능하지만 숫자가 작은곳에서 시작한다면 위쪽은 볼 필요가 없어서 4방향만 확인하면 된다.

그리고 보물보다 더 밑은 확인할 필요가 없어서 제외 시켰다.

 

from collections import deque

dx = [0,1,1, 0]
dy = [1,1,0,-1]

tc = int(input())

board = [[0]*141 for _ in range(141)]
num_loc = [()]
visited = [[0]*141 for _ in range(141)]
visited_num = 1

def solv(t):
    a,b = map(int, input().split())
    print('#%d %d'%(t,bfs(min(a,b),max(a,b))))
def bfs(a,b):
    global visited
    sx,sy = num_loc[a]
    ex,ey = num_loc[b]

    q = deque([(sx,sy,0)])
    visited[sx][sy] = visited_num

    while q:
        x,y,cnt = q.pop()
        if x == ex and y == ey:
            return cnt

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if point_validator(nx,ny,ex,ey):
                visited[nx][ny] = visited_num
                q.appendleft((nx,ny,cnt+1))
def point_validator(x,y,ex,ey):
    if x < 0 or y < 0 or x > ex or y > 141:
        return False
    elif board[x][y] == 0:
        return False
    elif visited[x][y] == visited_num:
        return False
    return True

def init_board():
    global board
    num = 1
    for x in range(141):
        for y in range(x+1):
            board[x][y] = num
            num_loc.append((x,y))
            if num == 10000:
                return
            num+=1
    print(num)


init_board()
for t in range(1,tc+1):
    visited_num += 1
    solv(t)