글 읽기 - 시간초과 해결 방법 부탁드립니다 ..

thdruddyd21 3년 전 0

로직은 맞는듯한데 맞왜초인지 모르겠습니다 ..

1. 각 사람들에 해당하는 성( 번호 순으로 순차적 for문) 들 각각의 경우에 대해 DFS로 확장 가능한 좌표들을 temp에 저장합니다

2. temp를 순회하며 board를 갱신합니다 ( 확장시키기 )

3. 더 이상 방문할 곳이 없으면 탈출

로 설계했습니다

어느부분에서 연산이 낭비되고 있는지 짚어주신다면 감사하겠습니다

import sys

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

def move(player, d, x, y):
    global temp, changed, tvisited
    if d == Len[player]:
        return

    if d > max(N, M) * 2:
        return

    for k in range(4):
        tx, ty = x + dx[k], y + dy[k]
        if 0 <= tx < N and 0 <= ty < M and board[tx][ty] == '.' and not tvisited[tx][ty]:
            tvisited[tx][ty] = True
            if [tx, ty] not in temp:
                temp.append([tx, ty])
            changed = True
            move(player, d + 1, tx, ty)


def start():
    global temp, changed, tvisited
    for p in range(P):
        temp = list()
        while nodes[p]:
            cx, cy = nodes[p].pop()
            tvisited = [[False for _ in range(M)] for _ in range(N)]
            tvisited[cx][cy] = True
            move(p, 0, cx, cy)
        nodes[p] = temp # new
        for nx, ny in nodes[p]:
            board[nx][ny] = p + 1

N, M, P = map(int, sys.stdin.readline().split())
Len = list(map(int, sys.stdin.readline().split()))
board = []
temp = []
tvisited = []
nodes = [list() for _ in range(P)]
for _ in range(N):
    board.append(list(sys.stdin.readline().rstrip()))

for i in range(N):
    for j in range(M):
        if board[i][j] != '.' and board[i][j] != '#':
            board[i][j] = int(board[i][j])
            nodes[int(board[i][j]) - 1].append([i, j])

while True:
    changed = False
    start()
    if not changed:
        break

dic = {i : 0 for i in range(1, P + 1)}
for i in range(N):
    for j in range(M):
        if board[i][j] != '.' and board[i][j] != '#':
            dic[board[i][j]] += 1

for i in range(1, P + 1):
    print(dic[i], end = " ")

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 해결 방법 부탁드립니다 ..

thdruddyd21 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말