글 읽기 - 정답코드 시간차이가 심합니다 (정답코드 주의)

jy1559 1년 전 0

정답은 맞췄으나 시간이 오래 걸립니다.

3가지 벽 세울 조합을 모두 구해서 각 경우의 수를 BFS 돌리는 아이디어를 생각하고 짜서 바로 맞추긴 했습니다.

근데 5876ms로 굉장히 오래 걸려서 다른 코드들을 살펴보던 중 1488ms로 4배가량 속도차이가 나는 코드를 봤는데

아이디어는 거의 동일하고 세세한 부분에서 조금 차이가 납니다.

차이를 살펴보면 빠른 코드에서는 그래프를 1차원 배열로 만든 것과, 제가 BFS 후 전체 그래프를 한 번 더 돌면서 안전구역을 센 것 정도 같습니다.

그래서 그래프 돌며 안전구역 찾는 것을 빼고 빠른 코드처럼 바이러스 감염될때마다 숫자 세는거로 바꿔도 5664ms로 크게 달라지지 않았습니다.

deepcopy가 문제인 걸까요? 아니면 다른 문제가 있는건가요?

고수님들 도와주세요...

#제 정답코드. 5876ms
from collections import deque
from copy import deepcopy   
from itertools import combinations
N,M = map(int,input().split())
graph = []
zeros = []
virus = []
for i in range(N): #입력받고 빈칸 + 바이러스 칸 리스트에 저장
    graph.append(list(map(int,input().split())))
    for j,x in enumerate(graph[-1]):
        if x == 0: zeros.append((i,j))
        if x == 2: virus.append((i,j))
combi = list(combinations(zeros,3)) #빈칸 중 3칸 조합 구함

dx = [1,-1,0,0] #BFS용
dy = [0,0,1,-1]
answer = 0
graphs = []
for now in combi: #빈칸 조합 for문
    graphs = deepcopy(graph) #그래프 (맵) 입력받음
    temp = 0 #현재 순환에서의 안전구역 개수
    for x in now:
        graphs[x[0]][x[1]] = 1 #3칸 벽 세움
    q = deque(virus) #바이러스 큐
    while q:
        x,y = q.popleft()
        for i in range(4): #상하좌우 4칸 돌면서
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<N and 0<=ny<M and graphs[nx][ny] == 0: #붙어있는칸
                graphs[nx][ny] = 2 #감염 후 새로 큐에 넣음
                q.append((nx,ny))
    for x in graphs: #순환 후 안전구역 숫자 셈
        for a in x:
            if a == 0: temp += 1 #이 부분이 오래걸리나 싶어서 아래처럼 바이러스 추가될
            #때마다 숫자 세는거로 바꿔봐도 5664ms로 크게 단축 안됨
    answer = temp if temp > answer else answer #안전구역 숫자 최대시 저장
print(answer)

#다른 정답코드. 1488ms

from sys import stdin
from itertools import combinations
input = stdin.readline
def solve():
    N, M = map(int, input().split())
    length = N * M
    arr = [0] * length
    for i in range(0, length, M):
        arr[i:i + M] = [*map(int, input().split())] #그래프 입력은 동일하나 1차원 배열

    blanks = []
    virus = []
    for i in range(length):
        if arr[i] == 0:
            blanks.append(i) #제 코드의 zeros 리스트와 동일
        elif arr[i] == 2:
            virus.append(i) # 제 코드의 virus 리스트와 동일

    not_wall = len(blanks) + len(virus) - 3 #안전구역 숫자 세는 것 같음
    ans = 0 #answer과 동일
    for blank in combinations(blanks, 3): #조합 순환 동일
        que = virus.copy()
        brr = arr.copy()
        infection = 0 
        for pos in blank:
            brr[pos] = 1
        while que: #거의 같으나 1차원 배열인 차이
            idx = que.pop()
            infection += 1
            r, c = idx // M, idx % M
            adj = [
                idx - M if 0 < r else -1,
                idx + M if r < N - 1 else -1,
                idx - 1 if 0 < c else -1,
                idx + 1 if c < M - 1 else -1
            ]
            for nxt in adj:
                if nxt != -1 and brr[nxt] == 0:
                    brr[nxt] = 2
                    que.append(nxt)

        cur = not_wall - infection #temp와 비슷함
        if ans < cur:
            ans = cur

    return ans


if __name__ == '__main__':
    print(solve())

rhzn5512 1년 전 0

얕은 복사를 사용하고자 1차원 배열로 만든 점이 유효하게 작용하신 것 같습니다.

1번 코드는 얕은 복사를 사용하지 못합니다. (n 차원의 배열에서 내부 배열의 주소 값이 원본 주소와 같고, 제일 바깥쪽 배열은 원본 주소와 다릅니다.)

얕은 복사의 경우 1차원 배열에서 메모리 주소 값이 다릅니다.

아래 코드는 얕은 복사를 사용하고자 1차원 배열로 만든 것이고, 얕은 복사를 사용할 수 있음으로서 루프가 확연히 줄어들게 됩니다.(기본적으로 1차원 배열과 2차원 배열의 성능 차이는 거의 없음)

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

문제

문제

출처

ICPC

정답코드 시간차이가 심합니다 (정답코드 주의)

jy1559 1년 전 0

rhzn5512 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말