백준 21610 파이썬

문제

마법사 상어와 비바라기

백준 21610 바로가기

코테 시즌 기념 삼성 기출문제를 풀어봤다.
상어문제 푸는데 거의 1시간 반이나 걸렸다... 더 노력해야겠다..

풀이

내가 많은 삼성문제를 풀어 본 적은 없지만 삼성 기출은 약간의 패턴(?) 이 있다.
네이버로 이직했던 회사 선배도 그랬다

방향성 가지고 배열탐색하기
라고 생각한다. 정확한 명칭은 뭐...

조건 1: 구름이동 간단하게 바꾸기

이 문제에서는 구름 이동시에 1-> N 으로 , N-> 1로가는 순서가 존재한다.
이 부분을 잘 생각해주어야 한다. 이부분에서 코드가 조금 난잡해지긴 했다.
물복사 버그 쓸때는 적용 안된다;;;;;

ex) N=10 일때 15칸 움직이는 것은 몇칸움직이는 것과 같을까?

조건 2 : 같은 칸에서 구름 중복생성 안된다

사라진 구름이 있던 위치에는 구름이 생성되면 안된다.
이부분을 위해서 가장 많이 사용했던 visited 사용하여 체크할까도 생각했지만,
그냥 새로운 배열에

list.append()

사용했다.
N의 범위가 크지않아서 가능할 거라고 생각했다 ^_^ (정답~!)

나머지는 순서에 따라 진행하면 된다.

1. 구름 이동 함수 구현
2. 해당 위치에 물의 양 증가 구현
3. 조건에 맞춰 물의 양 증가 추가 구현
4. 새로운 구름의 위치 저장 함수 구현

정답 코드

#필요한 것들 셋팅하는 코드이다.
import sys
input = sys.stdin.readline

N,M=map(int,input().split())
arr=[[0 for _ in range(N+1)]]
arr+=[[0]+list(map(int,input().split())) for _ in range(N)]
cloud=[[False for _ in range(N+1)] for _ in range(N+1)]
visited=[[False for _ in range(N+1)] for _ in range(N+1)]
# 구름 초기화
cloud[N][1]=True
cloud[N][2]=True
cloud[N-1][1]=True
cloud[N-1][2]=True


# 1. 구름 이동 함수 구현 
def move_cloud(d,s):
    # 왼, 왼위, 위, 오위,오,오아래,아래,왼아래 순으로
    direction=[[0,-1],[-1,-1],[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1]]
    d_x=direction[d-1][0]*(s%N)
    d_y=direction[d-1][1]*(s%N)
    visited=[]
    for i in range(1,N+1):
        for j in range(1,N+1):
            if cloud[i][j]==True:
                cloud[i][j]=False
                visited.append([i,j])
    for mv in visited:
        # d_x 일단 처리 해줘야 함
        if d_x < 0 :
            d_x= N+d_x
        if d_y<0:
            d_y=N+d_y
        # -(N-1)<d_x,d_y<N-1
        # 1<mv<N
        # 아무리 많이 벗어나도 2N이상 벗어날 수 없음
		
        # 이 아래 부분은 사실 필요없을 것같지만 뭐 코드 추가한다고 해서 시간복잡도 증가하는 것도 아니고 
        # 혹시나 해서 넣었다. 그래서 더 복잡해보인다.
        if mv[0]+d_x<=0:
            n_x=N-(mv[0]+d_x)
        elif mv[0]+d_x > N :
            n_x=mv[0]+d_x-N
        else:
            n_x=mv[0]+d_x

        if mv[1]+d_y<=0:
            n_y=N-(mv[1]+d_y)
        elif mv[1]+d_y>N:
            n_y=mv[1]+d_y-N
        else:
            n_y=mv[1]+d_y
        #n_x와 n_y위치가 정해짐
        cloud[n_x][n_y]=True
# 2. 물의 양 증가 구현 
def rain_by_cloud():
    for i in range(1,N+1):
        for j in range(1,N+1):
            if cloud[i][j]:
                arr[i][j]+=1
# 3. 물 복사 버그 구현 
# 전형적인 bfs할때 많이 쓰는 포맷이다. 
def copy_water(r,c):
    cnt=0
    direct=[[-1,-1],[-1,1],[1,-1],[1,1]]
    for k in range(4):
        n_r=r+direct[k][0]
        n_c=c+direct[k][1]
        if 1<=n_r<=N and 1<=n_c<=N and arr[n_r][n_c]>0:
            cnt+=1
    arr[r][c]+=cnt
        
# 4. 구름 생성 구현 
# 전체 탐색하면서 이전 구름인 경우 체크해 주고 나중에 바꿔주었다. 
def make_cloud():
    cloud_before = []
    for i in range(1,N+1):
        for j in range(1,N+1):

            if arr[i][j]>=2 and cloud[i][j]==False:
                cloud[i][j]=True
                arr[i][j]-=2
            elif cloud[i][j]:
                # 이전 체크
                cloud_before.append([i,j])
    for b in cloud_before:
        cloud[b[0]][b[1]]=False

# 주어진 구름 이동 만큼 이동시키고 바뀌는 것 함수로 나뉘어 구현 
for _ in range(M):
    d,s=map(int,input().split())
    move_cloud(d,s)
    rain_by_cloud()
    for i in range(1,N+1):
        for j in range(1,N+1):
            if cloud[i][j]:
                copy_water(i,j)
    make_cloud()

# 최종 물의 양 계산 
res=sum(sum(arr[i]) for i in range(N+1))
print(res)

결과 정답