★Implementation&Simluation Advanced I - 5 Solved★

★ 21610 마법사 상어와 비바라기 ★

 

import sys
input=sys.stdin.readline
from collections import deque
N,M=map(int,input().split())

baskets=[]
for _ in range(N):
    baskets.append(list(map(int,input().split())))

moves=[]
for _ in range(M):
    moves.append(tuple(map(int,input().split())))

clouds=deque([[N-2,0],[N-2,1],[N-1,0],[N-1,1]])
#(1) clouds moving
dx,dy=[0,-1,-1,-1,0,1,1,1],[-1,-1,0,1,1,1,0,-1]
for move in moves:
    d,s=move[0],move[1]
    for cloud in clouds:
        for _ in range(s):
            cloud[0] += dx[d-1]
            cloud[1] += dy[d-1]
            if cloud[0] < 0: cloud[0] = (N-1)
            if N <= cloud[0]: cloud[0] = 0
            if cloud[1] < 0: cloud[1] = (N-1)
            if N <= cloud[1]: cloud[1] = 0
        #(2) raining in 4clouds (increment in 1)
        baskets[cloud[0]][cloud[1]] += 1

    ddx,ddy=[-1,-1,1,1],[1,-1,1,-1]
    #(3) check diagonal dir if having water
    for cloud in clouds:
        x,y=cloud[0],cloud[1]
        cnt=0
        for i in range(4):
            nx,ny=x+ddx[i],y+ddy[i]
            if 0<=nx<N and 0<=ny<N:
                if baskets[nx][ny] >= 1:
                    cnt += 1
        baskets[x][y] += cnt
    for cloud in clouds:
        baskets[cloud[0]][cloud[1]] *= (-1)
    #(4) remaining slots - forming cloud(when >= 2) and decreased in 2
    cloud_length=len(clouds)
    for x in range(N):
        for y in range(N):
            if baskets[x][y] < 0: #where cloud is located:
                baskets[x][y]*=(-1)
            else:
                if baskets[x][y] >= 2:
                    baskets[x][y] -= 2
                    clouds.append([x,y])
    for _ in range(cloud_length):
        clouds.popleft()

#(5) get the sum
total = 0
for x in range(N):
    for y in range(N):
        total += baskets[x][y]

print(total)

 

🥶 지문 대로 그래도 구현. 시간 초과를 막기 위해 2가지 방법 사용

① 새로운 cloud를 위한 별도의 list를 준비하지 말고, cloud deque의 오른쪽에 차례대로 넣기. 앞에서의 cloud는 popleft()로 기존 구름의 개수만큼 빠르게 없애기

② 구름인지 아닌지 알기 위해 미리 -1을 곱함. 어차피 음수인 경우는 존재하지 않고, 구름 자리에 1씩 올리므로 0은 없으므로 무방. 이후 (4) 단계에서 구름인 경우와 구름이 아닌 경우 한 번에 반복문 돌리기 가능

 

🥶 그 외 구현 TIP

① 상하좌우대각선 이동 방향 벡터 dx, dy 사용

② 0보다 작거나 N-1보다 큰 경우, 즉 그래프를 벗어날 때만 보정 

---

★ 17144 미세먼지 안녕! ★

 

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

R,C,T=map(int,input().split())
A=[]
dusts=deque([])
air_purifier = []
for i in range(R):
    row = list(map(int,input().split()))
    A.append(row)
    for j in range(C):
        if A[i][j] == -1: #air purifier
            air_purifier.append((i,j))

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

for _ in range(T):
    for i in range(R):
        for j in range(C):
            if A[i][j] > 0: #dust
                dusts.append((i,j))

    #1 calculating the deltas in each of the possible dusts
    len_dusts = len(dusts)
    for _ in range(len_dusts):
        dust_x,dust_y=dusts.popleft()
        if A[dust_x][dust_y] > 0: #if it is a dust
            cum_dust=0
            for i in range(4): #calculate the deltas 
                nx,ny=dust_x+dx[i],dust_y+dy[i]
                if 0<=nx<R and 0<=ny<C and (nx,ny) not in air_purifier: #if can spread
                    amount = int(A[dust_x][dust_y]/5)
                    if amount > 0:
                        cum_dust+=amount
                        dusts.append((nx,ny,amount))
            if cum_dust > 0:
                dusts.append((dust_x,dust_y,-cum_dust)) 
    
    #2 applying deltas
    len_dusts_delta = len(dusts)
    for _ in range(len_dusts_delta):
        dust_x,dust_y,delta=dusts.popleft()
        A[dust_x][dust_y] += delta
    
    #3 air purifier operating
            
    #3-1 upper one
    air_x,air_y=air_purifier[0]

    #<1> right dir ->
    last_one=A[air_x][-1]
    A[air_x]=[-1,0]+A[air_x][1:-1]

    #<2>upper dir
    last_one_2=A[0][-1]
    for i in range(air_x):
        if i == air_x -1:
            A[i][-1] = last_one
        else:
            A[i][-1]=A[i+1][-1]

    #<3> left dir <-
    last_one_3=A[0][0]
    A[0]=A[0][1:-1]+[last_one_2]+[A[0][-1]]

    #<4> down dir
    for i in range(air_x-1,0,-1):
        if i != 1:
            A[i][0] = A[i-1][0]
        else: #i==1
            A[1][0] = last_one_3

    #3-2 lower one
    air_x,air_y=air_purifier[1]

    #<1> right dir ->
    lower_last_one=A[air_x][-1]
    A[air_x]=[-1,0]+A[air_x][1:-1]

    #<2> down dir
    lower_last_one_2=A[-1][-1]
    for i in range(R-1,air_x,-1):
        if i != (air_x+1):
            A[i][-1]=A[i-1][-1]
        else:
            A[i][-1]=lower_last_one

    #<3> left dir <-
    lower_last_one_3=A[-1][0]
    A[-1]=A[-1][1:-1]+[lower_last_one_2]+[A[-1][-1]]

    #<4> upper dir
    for i in range(air_x+1,R-1):
        if i == (R-2):
            A[i][0] = lower_last_one_3
        else: #i!=(R-1)
            A[i][0] = A[i+1][0]

ans = 0
for x in range(R):
    for y in range(C):
        if A[x][y]>0:
            ans+=A[x][y]
print(ans)

 

🥶

① 여러 미세먼지가 '동시에' 양 방향으로 흩날림을 주의하면 되는 문제: 따라서 바로 바로 update해서는 안되므로 변화량 구하기 따로 / update 따로 deque을 2번 돌렸다: 바로 배열을 update할 수 없으므로 / 미세먼지를 deque에 돌려 0보다 크다면 spread 진행: 이 때 변화량이 있다면 deque에 (x, y, delta)를 넣음 / 변화량 있는 만큼 이후 deque을 다시 돌려 A update

② 공기청정기 총 8칸 각각 simulation index 생각하며 일일이 진행 ... 🥶

---

★ 20056 마법사 상어와 파이어볼 ★

 

import sys
input=sys.stdin.readline
from collections import deque
from collections import defaultdict
N,M,K=map(int,input().split())
masses=[[0]*N for _ in range(N)]
fireballs_grouped=deque()
for _ in range(M):
    r,c,m,s,d=map(int,input().split())
    fireballs_grouped.append((r-1,c-1,m,s,d))
dx,dy=[-1,-1,0,1,1,1,0,-1],[0,1,1,1,0,-1,-1,-1]
for i in range(K):
    fireballs_grouping=defaultdict(list)

    #moving fireballs
    len_fb=len(fireballs_grouped)
    for _ in range(len_fb):
        fbr,fbc,fbm,fbs,fbd=fireballs_grouped.popleft()
        nx,ny=fbr+dx[fbd]*fbs,fbc+dy[fbd]*fbs
        if ny < 0 or N <= ny:
            remain = abs(ny)%(N)
            if remain == 0:
                ny = 0
            else:
                if ny < 0:
                    ny = (N-remain)
                else:
                    ny = remain
            
        if nx < 0 or N <= nx:
            remain = abs(nx)%(N)
            if remain == 0:
                nx = 0
            else:
                if nx < 0:
                    nx = (N-remain)
                else:
                    nx = remain

        fireballs_grouping[(nx,ny)].append((fbm,fbs,fbd))

    #gathering fireballs
    for x,y in fireballs_grouping:
        if len(fireballs_grouping[(x,y)]) == 1: #only 1
            m,s,d=fireballs_grouping[(x,y)][0]
            fireballs_grouped.append((x,y,m,s,d))
        else: #more than 1
            m,s,d,l=0,0,0,len(fireballs_grouping[(x,y)])
            for mm, ss, dd in fireballs_grouping[(x,y)]:
                m+=mm
                s+=ss
                if dd%2==0:
                    d+=1
            m=int(m/5)
            s=int(s/l)
            if m > 0:
                if d == l or d == 0: #all evens or all odds
                    for n in [0,2,4,6]:
                        fireballs_grouped.append((x,y,m,s,n))
                else:
                    for n in [1,3,5,7]:
                        fireballs_grouped.append((x,y,m,s,n))

    if i==(K-1): #if this is the last time
        ans=0
        for _ in range(len(fireballs_grouped)):
            fireball = fireballs_grouped.popleft()
            ans+=fireball[2]
        print(ans)

 

🥶

① 첫 개별 파이어볼들의 모음을 fireballs_grouped로 deque에 차곡차곡 쌓기 / 합치기 전 개별 파이어볼들의 이동 후 모음을 fireballs_grouping으로 defaultdict(list)로 구현해 쌓기(★자료구조 deque / 겹치는 자료는 defaultdict(list) 활용)

② fireballs_grouped에서 1개씩 차곡차곡 파이어볼을 빼내면서 주어진 방향과 속력에 맞게 파이어볼 이동. 즉 x, y만 업데이트

③ 방향과 속력에 맞게 이동하는 과정에서 방향 번호에 맞게 dx, dy 방향벡터 리스트 만들기 + fbs 속력만큼 방향벡터 값을 곱하고 난 뒤, 해당크기를 N으로 나눈 나머지가 0이라면 첫 행/열, 그렇지 않다면 음수일 경우 N-remain을 nx,ny로 / N 이상일 경우 remain을 nx,ny로 보정(즉, 행과 열을 벗어날 경우 index 처리를 어떻게 해주는 지가 문제의 핵심)

④ 이후 이동하면, 같은 nx, ny가 있을 수 있으므로, 이를 위해 dictionary의 key값으로 (nx,ny)를 defaultdict(list)에 update

⑤ 이후 fireballs_grouping을 돌면서 해당 key값 list에 1개만 있다면 다시 fireballs_grouped에 넣기 / 2개 이상이라면 해당 key값 list 돌면서 질량 m, 속력 s, 방향 d update(이 때 update된 m이 0보다 클 경우만 취급 / 0보다 크다면 d를 update할 때 짝수의 개수만큼 +1, 즉 0 또는 list 개수만큼 d값이 나온다면 전부 홀수/짝수이므로 이 때는 0, 2, 4, 6 방향을 가진 4개 fireball deque에 append / 아니면 1, 3, 5, 7 방향을 가진 4개 fireball deque에 append) 

⑥ 마지막 K-1번째 loop이라면 deque에서의 fireball 꺼내며 m 누적으로 더해 m 최종 출력

---

★ 14503 로봇 청소기 ★

 

import sys
input=sys.stdin.readline

N,M=map(int,input().split())
x,y,d=map(int,input().split())
robot_cleaning_map=[]
cleaned=[[False]*M for _ in range(N)]
for _ in range(N):
    robot_cleaning_map.append(list(map(int,input().split())))
ans=0
dx,dy=[-1,0,1,0],[0,1,0,-1]
bdx,bdy=[1,0,-1,0],[0,-1,0,1]
while 1:
    if not cleaned[x][y]: #not cleaned
        cleaned[x][y] = True #clean
        ans+=1

    cnt,cleaned_cnt=0,0
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<N and 0<=ny<M:
            if robot_cleaning_map[nx][ny] != 1: #if not a wall
                cnt+=1
                if cleaned[nx][ny]:
                    cleaned_cnt+=1
    
    if cnt==cleaned_cnt: #all cleaned
        nx,ny=x+bdx[d],y+bdy[d]
        if robot_cleaning_map[nx][ny] !=1: #if in array and not a wall - can go backwards
            x,y=nx,ny
            continue
        else:
            break
    else: #if not all cleaned
        for _ in range(4):
            if (d-1)<0: d=3
            else: d-=1
            if d == 0: #north
                if robot_cleaning_map[x-1][y] != 1 and not cleaned[x-1][y]:
                    x-=1
                    break
            elif d == 1: #east
                if robot_cleaning_map[x][y+1] != 1 and not cleaned[x][y+1]:
                    y+=1
                    break
            elif d == 2: #south
                if robot_cleaning_map[x+1][y] != 1 and not cleaned[x+1][y]:
                    x+=1
                    break
            else: #west
                if robot_cleaning_map[x][y-1] != 1 and not cleaned[x][y-1]:
                    y-=1
                    break
print(ans)

 

🥶 청소 유무 visited 배열 사용 + 주변이 벽이 아닌 case 중 청소 여부 개수에 따라 진행 + back으로 진행하는 방향벡터 bdx / bdy + 90도 시계반대방향으로 돌며 확인. 찾으면 break로 바로 진행

---

★ 3190 뱀 ★

 

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

N=int(input()) #NxN

K=int(input())
apples=set()
for _ in range(K):
    r,c=map(int,input().split())
    apples.add((r-1,c-1)) #starts from (0,0)

L=int(input())
ds=[]
for _ in range(L):
    X,C=input().rstrip().split()
    ds.append((int(X),C))
d_i=0
dx,dy=[-1,0,1,0],[0,1,0,-1]#up right down left
cur_d=1 #current direction: right
snakes=[[False]*N for _ in range(N)]

time=0
snakes[0][0]=True
snake_body=deque([(0,0)])
while 1:
    
    x,y=snake_body[0][0],snake_body[0][1]
    nx,ny=x+dx[cur_d],y+dy[cur_d] #update pos

    if nx<0 or N<=nx or ny<0 or N<=ny: #crashed into the wall
        print(time+1)
        break #game over
    if snakes[nx][ny]: #if crashed in itself
        print(time+1)
        break #game over

    if (nx,ny) in apples: #if apples
        apples.discard((nx,ny)) #apple disappeared
        snakes[nx][ny] = True
        snake_body.appendleft((nx,ny))

    else: #no apples
        tx,ty=snake_body[-1][0],snake_body[-1][1]
        snake_body.pop()
        snakes[tx][ty]=False

        snakes[nx][ny]=True
        snake_body.appendleft((nx,ny))
    
    time+=1

    #direction update
    if d_i <= (L-1):
        if time == ds[d_i][0]:
            if ds[d_i][1] == 'L': #turn left
                cur_d=(cur_d-1)%4
            else: #'D'
                cur_d=(cur_d+1)%4
            d_i+=1

 

🥶 몇 가지만 문제에 특화된 아이디어 기억하면 됨. (1) 뱀이 자기 자신에 부딪히는 건 visited 방문 여부 배열로 check / (2) deque 구현해서 뱀의 머리와 꼬리 deque의 앞과 끝만 주의해서 처리하면 됨 / (3) apples는 set()에 저장 / (4) dir 방향배열 사용 + % 모듈러로 1, 2, 3, 4 방향 제어 / (5) 시뮬레이션 시 time 변수 변화 제어

---