글 읽기 - Python 시관초과 문제 어떻게 해결할까요

khsh5592 4년 전 0

알고리즘은 아래와 같습니다.

1. 상근이 위치를 확인해 sgQ 에 넣는다. (sgCheck)

2. 불의 위치를 확인해 fireQ 에 넣는다. (fireCheck)

3. 매 시간마다 불을 확산시킨다. (fireSpread)

4. 상근이를 탈출시킨다. (sgExit)

4.1 상근이의 탈출경로가 모서리일 경우 return true

4.2 현재 시간을 return

5. 만약 상근이의 Q 가 비어있는경우 탈출을 못하므로 IMPOSSIBLE

어디서 시간을 더 줄일 수 있을지 모르겠내요.

import sys
from queue import Queue

def sgCheck(building, N, M):
    for i in range(N):
        for j in range(M):
            if building[i][j] == '@':
                return i, j

def sgExit(building, N, M, time, Q):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    for _ in range(Q.qsize()):
        i, j = Q.get()

        for k in range(4):
            nx = i + dx[k]
            ny = j + dy[k]
            if (0 <= nx and 0 <= ny and nx < N and ny < M):
                if building[nx][ny] == '.':
                    if nx == 0 or nx == N - 1 or ny == 0 or ny == M - 1:
                        return 1
                    else:
                        Q.put((nx, ny))
    return 0

def fireCheck(building, N, M, Q):
    for i in range(N):
        for j in range(M):
            if building[i][j] == '*':
                Q.put((i, j))

def fireSpread(building, N, M, Q):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    for _ in range(Q.qsize()):
        i, j = Q.get()
        for k in range(4):
            nx = i + dx[k]
            ny = j + dy[k]
            if (0 <= nx and 0 <= ny and nx < N and ny < M):
                if building[nx][ny] == '.' or building[nx][ny] == '@':
                    building[nx][ny] = '*'
                    Q.put((nx, ny))

def Simulation(building, N, M):
    sgQ = Queue()
    fireQ = Queue()
    time = 1

    sgQ.put((sgCheck(building, N, M)))
    fireCheck(building, N, M, fireQ)

    while not sgQ.empty():
        fireSpread(building, N, M, fireQ)
        if sgExit(building, N, M, time, sgQ):
            return time + 1
        else:
            time += 1
    return False

def solution():
    T = int(input())
    for _ in range(T):
        M, N = map(int, sys.stdin.readline().split())

        data = []

        for _ in range(N):
            data.append(list(map(str, input())))

        ret = Simulation(data, N, M)
        if ret == False:
            print("IMPOSSIBLE")
        else:
            print(ret)

solution()

djm03178 4년 전 0

sgExit에서 이동할 때 큐에 넣기만 하고 방문 표시를 하지 않고 있습니다.

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

문제

문제

출처

ICPC

Python 시관초과 문제 어떻게 해결할까요

khsh5592 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말