글 읽기 - 시간초과가 납니다.

pepper_mis 1년 전 0

혹시 무한루프에 걸리는곳이 있는지 확인부탁드려도 될까요?

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

#화살쏘기
def shoot_left(h):
    for i in range(C):
        if mineral[h][i] == 'x':
            mineral[h][i]='.'
            return
def shoot_right(h):
    for i in range(C-1, -1, -1):
        if mineral[h][i] == 'x':
            mineral[h][i]='.'
            return
        
di = [-1, 1, 0, 0]
dj = [0, 0, -1, 1]

def check(i, j):
    global R, C, visited
    return 0<=i<R and 0<=j<C and not visited[i][j] and mineral[i][j] == 'x'

def find_cluster(i, j):
    global C, R
    cluster = [[i, j]]
    floor = 0
    queue = deque()
    queue.append((i, j))
    while queue:
        i, j = queue.popleft()
        if i == R-1: floor = 1
        for n in range(4):
            ni, nj = i+di[n], j+dj[n]
            if check(ni, nj):
                queue.append((ni, nj))
                cluster.append([ni, nj])
                visited[ni][nj] = 1
    return floor, cluster
            
def drop_cluster():
    global visited
    flag = 1
    visited = [[0]*C for _ in range(R)]
    clusters = []
    for i in range(R):
        for j in range(C):
            if flag and check(i, j):
                clusters.append(find_cluster(i, j))
    for i in range(len(clusters)):
        floor, cluster = clusters[i]
        if not floor:
            while True:
                for i, j in cluster:
                    mineral[i][j] = '.'
                for c in range(len(cluster)):
                    i, j = cluster[c]
                    mineral[i+1][j] = 'x'
                    cluster[c] = [i+1, j]
                for i, j in cluster: #바닥에 닿았는지 확인
                    if i==R-1: return
                    if [i, j] not in cluster and mineral[i+1][j] == 'x': return
                
def print_mineral():
    for m in mineral:
        print(''.join(m))
        
R, C = map(int, input().split())
mineral = []
for _ in range(R):
    mineral.append(list(input().strip()))
N = int(input())
height = list(map(int, input().split()))        

visited = []
for i in range(N):
    if i%2==0: shoot_left(R-height[i])
    else: shoot_right(R-height[i])
    drop_cluster()
print_mineral()

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

문제

문제

출처

ICPC

시간초과가 납니다.

pepper_mis 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말