파이썬)체스판 위의 공 - BOJ(실패)

https://www.acmicpc.net/problem/16957

16957번: 체스판 위의 공

 

import sys
input = sys.stdin.readline

r, c = map(int, input().split())

arr = []

board = []


for _ in range(r):
    a = [0] * c
    board.append(a)
    arr.append(list(map(int, input().split())))

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


def move(i, j):

    while True:
        min_value = 9909009990900900909
        nx, ny = i, j
        for k in range(len(dx)):

            nx = i + dx[k]
            ny = j + dy[k]

            if 0 <= nx < r and 0 <= ny < c:
                if min_value > arr[nx][ny]:
                    min_value = arr[nx][ny]
                    min_x, min_y = nx, ny
        if min_value > arr[i][j]:
            board[i][j] += 1
            return
        else:
            i, j = min_x, min_y


for i in range(r):
    for j in range(c):
        move(i, j)

# move(1, 0)

for i in range(r):
    for j in range(c):
        print(board[i][j], end=' ')
    print()

처음 작성한 코드이다. bfs로 보드의 모든 숫자에 대해 bfs를 진행했고 한 70퍼센트 쯤에서 타임아웃이 발생했다.

당연히 dp를 생각했지만 이를 어떻게 dp로 구현해야할지 생각이 날듯했지만 너무 복잡했다.

 

다른사람의 코드를 참조해봤따.

from collections import deque
import sys
input = sys.stdin.readline

r, c = map(int, input().split())

arr = []

board = []
marbles = [[1 for _ in range(c)] for _ in range(r)]
parent = [[[] for _ in range(c)] for _ in range(r)]


for _ in range(r):
    a = [0] * c
    arr.append(list(map(int, input().split())))

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


def move(i, j):
    q = deque()
    q.append((i, j))
    while True:
        x, y = q.popleft()
        min_value = 1e9
        min_dir = []

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

            if 0 <= nx < r and 0 <= ny < c:
                if arr[nx][ny] <= arr[x][y] and min_value >= arr[nx][ny]:
                    min_value = arr[nx][ny]
                    min_dir = [nx, ny]

        if min_value == 1e9 and not min_dir:
            return [x, y]

        if parent[min_dir[0]][min_dir[1]]:
            return parent[min_dir[0]][min_dir[1]]
        else:
            q.append((min_dir[0], min_dir[1]))


for i in range(r):
    for j in range(c):
        parent[i][j] = move(i, j)
new_marbles = [[0 for _ in range(c)] for _ in range(r)]

for i in range(r):
    for j in range(c):
        if marbles[i][j]:
            nxt_idx = parent[i][j]
            new_marbles[nxt_idx[0]][nxt_idx[1]] += marbles[i][j]

for i in range(r):
    print(*new_marbles[i])

이분의 코드도 마찬가지로 시간초과가 발생했다..ㅠㅠ

후에 다시 풀어봐야겠다.