[삼성sw 2382번] 미생물격리(파이썬)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl&categoryId=AV597vbqAH0DFAVl&categoryType=CODE&problemTitle=SW&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2&&&&&&&&& 

SW Expert Academy

일반적으로 deque를 써서 이동하면 되는 문제가 아니라

알고리즘을 구성하는데 애를 많이 먹었습니다.

 

가장 어려웠던 부분은

'군집이 합쳐지는 케이스'

만약 이 케이스가 없었더라면

그냥 bfs하듯이 q를 계속 돌렸을텐데

이 부분이 있어서 좀 골치아팠습니다.

#삼성sw 2382 미생물격리
from copy import deepcopy
dx=[0,-1,1,0,0]
dy=[0,0,0,-1,1]
T=int(input())

def move():
    global room
    day=0
    while day<M:
        new_room=[[[] for _ in range(N) ]for _ in range(N)]
        hap=set()
        for x in range(N):
            for y in range(N):

                if room[x][y]:
                    cnt=room[x][y][0][0]
                    direct=room[x][y][0][1]
                    nx=x+dx[direct]
                    ny=y+dy[direct]
                    if nx==0 or nx==N-1 or ny==0 or ny==N-1:
                        cnt//=2
                        if direct==1:
                            direct=2
                        elif direct==2:
                            direct=1
                        elif direct==3:
                            direct=4
                        elif direct==4:
                            direct=3

                    if cnt==0:
                        continue
                    new_room[nx][ny].append([cnt,direct])
                    if len(new_room[nx][ny])>1:
                        hap.add((nx,ny))
        #겹친거 처리해주기
        for hx,hy in hap:

            now=new_room[hx][hy]

            n_size=len(now)
            n_cnt=now[0][0]
            n_max=now[0][0]
            n_dir=now[0][1]
            for k in range(1,n_size):
                if now[k][0]>n_cnt:
                    n_cnt=now[k][0]
                    n_dir=now[k][1]
                n_max+=now[k][0]
            new_room[hx][hy].clear()
            new_room[hx][hy].append([n_max,n_dir])


        room=deepcopy(new_room)
        day+=1

for case in range(T):
    N,M,K=map(int,input().split())
    virus=[]
    room =[[[] for _ in range(N) ]for _ in range(N)]
    for _ in range(K):
        vx,vy,vcnt,vdir=map(int,input().split())
        room[vx][vy].append([vcnt,vdir])

    move()
    answer=0
    for x in range(N):
        for y in range(N):
            if room[x][y]:
                answer+=room[x][y][0][0]

    print("#%d %d"%((case+1),answer))

 

처음에 제출했던 코드입니다.

문제에서 요구하는 데로 그대로 구현했습니다.

좌표를 돌면서 바이러스가 있는 걸 찾아서

계속 움직이는 방식이었죠.

하지만 for문을 너무 많이 돌다보니

시간초과를 피할 수 없었습니다.

 

어떻게 시간초과를 줄일까 생각하다가

'방 전체를 계속 돌기보다는

바이러스만 보고 움직이자'

라는 생각이 들어서 코드를 수정했습니다.

#삼성sw 2382 미생물격리

dx=[0,-1,1,0,0]
dy=[0,0,0,-1,1]
T=int(input())

def move():
    global virus
    day=0
    while day<M:
        new_room=[[[] for _ in range(N) ]for _ in range(N)]
        hap=set()
        popping=[]
        #1 바이러스를 움직여준다
        for k in range(len(virus)):
            now_virus=virus[k]
            x,y,cnt,dir=now_virus
            nx=x+dx[dir]
            ny=y+dy[dir]

            if nx==0 or nx==N-1 or ny==0 or ny==N-1:
                n_cnt=cnt//2
                #나눠서 0이 되는 건 나중에 삭제해준다
                if n_cnt==0:
                    popping.append([x,y,cnt,dir])
                    continue

                if dir==1:
                    n_dir=2
                elif dir==2:
                    n_dir=1
                elif dir==3:
                    n_dir=4
                elif dir==4:
                    n_dir=3
            else:
                n_cnt=cnt
                n_dir=dir
            new_room[nx][ny].append([n_cnt,n_dir])
            #이동한 구역에 바이러스가 2개이상이라면 hap이라는 집합에 넣어준다
            if len(new_room[nx][ny])>=2:
                hap.add((nx,ny))
            virus[k]=[nx,ny,n_cnt,n_dir]
        #2. 군집이 겹치는 거 처리해주기
        for hx,hy in hap:
            now=new_room[hx][hy]

            now_cnt=now[0][0]
            now_max=now[0][0]
            now_dir=now[0][1]
            popping.append([hx,hy,now_cnt,now_dir])
            #군집의 방향을 결정+군집의 모든 바이러스 합 구하기
            for i in range(1,len(now)):
                if now[i][0]>now_max:
                    now_max=now[i][0]
                    now_dir=now[i][1]
                now_cnt+=now[i][0]
                #이전 군집에 있는 바이러스는 없애준다
                popping.append([hx,hy,now[i][0],now[i][1]])
            #다 구한 군집의 바이러스,방향을 넣어준다
            virus.append([hx,hy,now_cnt,now_dir])
        #3. 없앨 바이러스는 없애준다
        for px,py,p_cnt,p_dir in popping:
            p_ind=virus.index([px,py,p_cnt,p_dir])
            virus.pop(p_ind)


        day+=1

for case in range(T):
    N,M,K=map(int,input().split())
    virus=[]
    room =[[[] for _ in range(N) ]for _ in range(N)]
    for _ in range(K):
        vx,vy,vcnt,vdir=map(int,input().split())

        virus.append([vx,vy,vcnt,vdir])
    move()
    answer=0
    for k in range(len(virus)):
        answer+=virus[k][2]
    print("#%d %d"%((case+1),answer))

시간초과를 어떻게 줄일 수 있을지 

공부할 수 있게 만들어준 좋은 문제입니다.