[삼성sw 5653] 줄기세포 배양(파이썬)

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

SW Expert Academy

참 까다로운 bfs문제.

우선, 이 문제에서

줄기세포가 퍼지는 걸

bfs로 구현한다까지는 쉽게 떠오르기 쉽습니다.

그 후, 조건보고 코드 짤려고하면

머리가 터집니다.

여기서 까다로운 점들과 풀었던 점을 적어봅니다.

 

1. 살고 죽는 거 어떻게 표현하지?

이 문제는 세포의 범위가 무한대이다.

범위값도 없어...어떻게?

-->visited를 딕셔너리로 받아준다.

그리고 딕셔너리에 

[투입시간, 생명력]을 넣어준다.

K시간이 지났을 때 살아남는다면

투입시간+생명력*2가 K보다 클 때이다.

(투입시간+생명력-->활성

활성+생명력+1-->죽음

고로 투입시간+2*생명력이

K보다 크면 K시간까지 활성이든 비활성이든

어찌되었든 살아있다는 의미)

 

2. 세포가 생명력만큼 살아있다?

예를들면 2라면 2만큼 살아있다는건데

그럼 두번deque를 돌려야?

-->그럴 필요 없다.

2시간후에서 활성화된 2를 보겠습니다.

3시간이 지난 후에도

해당 좌표의 2는 여전히 활성화되어있습니다.

그런데 굳이 더 고려할 필요가 없습니다.

왜냐하면 이미 상하좌우로

번식할 수 없기 때문입니다.

1시간 뒤가 되도

여전히 번식할 수 없는 곳은 번식이 불가능하고,

이미 1시간 전에 번식한 곳은

번식이 안 되기 때문에

활성화가 되더라도

번식의 역할을 수행할 수 없습니다.

 

3. 활성화주기??

실제로 코드를 다 짜고 이 부분 떄문에 애를 먹었습니다.

예제1의 결과값이 제가 짠 것과 많이 달랐습니다.

저는 초반에

현재시간%(세포의 수)로 나눈 값이 x일때

1~x까지의 세포가 퍼진다고 코드를 짰습니다.

하지만 문제에서 요구하는 바는 이것이 아니었습니다.

예제1을 기준으로

4,6시간뒤에는 세포가 번식이 없는 케이스가 생겼습니다.

직접 노트에

시간별로 세포가 번식하는 경우를 살펴보니

일정한 주기가 있었습니다.

1->2주기

2->3주기

그럼 3은 4주기??

라고 가설을 내리고 예제2를 봤더니 

생각한 게 맞았습니다.

그렇다면 세포별 활성화되는 시간은

(생명력+1)*K+(생명력)에 해당하는 값이었습니다.

시간을 돌릴 때 마다

생명력이 큰 순서대로 이 값에 해당하는지 파악하여

이 값이 맞다면 번식을 해줬습니다.

큰 순서대로 한 이유는

'겹칠 경우 가장 생명력이 높은 세포가 번식한다'

라는 조건이 있었기 때문입니다.

만약 특정 시간에 

여러 세포가 동시에 퍼진다해도

생명력 순서대로 퍼트린다면

가장 높은 생명력 세포에게 우선권이 주어지니깐

해당 조건을 만족합니다.

 

좀 더 쉽게 말로 풀자면

(1,1)좌표에 3,5 두 생명력을 지닌 세포가 들어갈 수 있다 가정합니다.

5를 먼저 번식시키면

(1,1)좌표에는 5가 들어갑니다.

그 후 3을 번식시키면

이미 (1,1)좌표에는 5가 들어가있으니

해당 지점으로는 번식할 수 없습니다.

 

from collections import deque

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

T=int(input())

for t in range(1,T+1):
    N,M,K=map(int,input().split())

    room=[]
    visited=dict()
    sell_num=0
    #1. 먼저 줄기세포를 방아준다
    for x in range(N):
        tmp=list(map(int,input().split()))
        for y in range(M):
            if tmp[y]>0:
                sell_num=max(sell_num,tmp[y])

        room.append(tmp)
    #sell=[deque()]*(sell_num+1)로하니, 모든 큐에 좌표가 다 넣어져서 수정
    sell=[deque()for _ in range(sell_num+1)]

    for x in range(N):
        for y in range(M):
            if room[x][y]>0:

                num=room[x][y]

                sell[num].append((x,y))
                visited[x,y]=[0,num]

    #2 줄기세포 번식
    for time in range(0,K):
        # print(time)
        # print(sell)
        for go in range(sell_num,0,-1):

            #직접 노트에 활성화되는 규칙을 찾아본 결과
            #(생명력+1)*K+(생명력) 주기로 활성화되더라고요.
            flag=(time-go)%(go+1)

            if flag==0:
                tmp=set()

                for _ in range(len(sell[go])):
                    x,y=sell[go].popleft()

                    for d in range(4):
                        nx=x+dx[d]
                        ny=y+dy[d]

                        if visited.get((nx,ny)):
                            continue

                        visited[nx,ny]=[time,go]
                        tmp.add((nx,ny))

                for tx,ty in tmp:
                    sell[go].append((tx,ty))

    cnt=0
    for fx,fy in visited:


        grid=visited.get((fx,fy))
        put_time=grid[0]
        life=grid[1]
        #투입시간+생명력-->활성시간
        #활성시간+생명력+1-->죽음
        #따라서 투입시간+생명력 *2 값이 K보다 크거나 같으면 생존
        if put_time+(life*2)>=K:

            cnt+=1

    print("#%d %d"%(t,cnt))

시간대로 bfs를 해주는 유형의 발전형입니다.

bfs를 할 때 주기를 고려해주는

독특한 문제입니다.