[SWEA 코딩] [모의 SW 역량테스트] 줄기세포배양 - PYTHON #5653

def bfs():
    cnt = 0 # 시간 체크용 cnt
    
    while cnt < k: # k 시간 전이면
    
        cnt += 1 # 시간 추가해주고
        
        sample = [] # sample 초기화
        
        number = len(q)
        # 조건에 따라 q의 길이가 변해서 발생할 수 있는 문제를 방지하고자 추가 함
        
        for qq in range(number):
        
            w = q.pop(0) # q의 가장 앞에꺼 추출
            
            if w[2] == 1: # w[2]가 1이면서
            
                if w[3] == 1: # w[3]이 1일 때,
                
                    for e in range(4): # 상 하 좌 우 확인용 for
                    
                        if visited[w[0]+x[e]][w[1]+y[e]] == 0:
                        # 상 하 좌 우 값이 0이면, 아직 세포가 번식하지 않은 곳
                        
                            visited[w[0] + x[e]][w[1] + y[e]] = w[2] # 0을 w[2]로 바꾸고
                            
                            sample.append([w[0] + x[e],w[1] + y[e],w[2],0])
                            # sample에 [i, j, w[2], 0] 집어 넣기
                            # x좌표 y좌표 생명력 시간 순

                        # sample이 필요한 이유
                        # 코드에서는 세포가 움직이는 순서가 존재 함
                        # 그래서 한 사이클 만큼의 번식 움직임을 sample에 넣어서
						# 이미 존재하는 값을 확인

                        else: # 값이 0이 아니면 == 이미 번식을 시도한 곳이면
                        
                            if w[2] > visited[w[0] + x[e]][w[1] + y[e]]:
                            # w[2]가 이미 번식을 시도한 세포보다 크면
                            
                                for s in sample:
                                
                                    if s[0] == w[0]+x[e] and s[1] == w[1]+y[e]:
                                    # x,y 값 동일한지 확인
                                    
                                        s[2] = w[2] # 값 바꾸기
                                        
                                        visited[w[0]+x[e]][w[1]+y[e]] = w[2] # 값 바꾸기

                else: # w[2]가 1이면서 w[3]이 1이 아닐 때,
                    w[3] += 1 # 시간 추가
                    q.append(w) # 다시 집어넣기

            else: # w[2]가 1이 아닌 경우
                if w[3] == w[2]: # w[2]와 w[3]이 같은 경우
                    for e in range(4):
                        if visited[w[0] + x[e]][w[1] + y[e]] == 0:
                            visited[w[0] + x[e]][w[1] + y[e]] = w[2]
                            sample.append([w[0] + x[e], w[1] + y[e], w[2], 0])

                        else:
                            if w[2] > visited[w[0] + x[e]][w[1] + y[e]]:
                                for s in sample:
                                    if s[0] == w[0] + x[e] and s[1] == w[1] + y[e]:
                                        s[2] = w[2]
                                        visited[w[0] + x[e]][w[1] + y[e]] = w[2]

                    w[3] += 1
                    q.append(w)

                elif w[3] == w[2]*2-1:
                # w[3]이 w[2]*2-1과 같은 경우 == 1시간 지나면 세포가 죽는 경우
                
                    pass # 시간 추가할 필요 없고, q에 다시 넣어 줄 필요 없다

                else: # 그 외
                    w[3] += 1
                    q.append(w)


        if len(sample) != 0: # sample이 비어있지 않으면
            q.extend(sample) # q에 추가


x = [-1,1,0,0] # 상 하 좌 우
y = [0,0,-1,1]

T = int(input())

for tc in range(1,1+T):
    n,m,k = map(int,input().split()) # n 세로 m 가로 k 시간

    board = [list(map(int,input().split())) for _ in range(n)] # 배양 용기

    visited = [[0]*(m+k+1) for _ in range(n+k+1)]
    # 2n 시간이 지나면 m,n에서 2n만큼 확장 된다고 판단해서 크기 결정 

    q = [] # [i, j, 생명력, 시간]이 들어감

    for i in range(n):
        for j in range(m):
            if board[i][j] != 0:
                q.append([i+(k//2)+1,j+(k//2)+1,board[i][j],0])
                # 가운데로 옮겨주기 위해서 k//2+1을 더해 줌
                
                visited[i+(k//2)+1][j+(k//2)+1] = board[i][j] # 해당 위치의 값 변경

    bfs()


    print('#{} {}'.format(tc,len(q)))

개인적인 풀이 방법, 효율적인 코드라 생각하지는 않지만 오랜 시도 끝에 풀어낸 문제라 나름 만족한다.

 

아직 bfs를 활용하는 것이 서툴지만 나름대로 bfs 흉내를 내보고자 노력했다.

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다.