[Samsung] 2021-2 오후 2번 미로 타워 디펜스

April 7, 2023

[Samsung] 2021-2 오후 2번 미로 타워 디펜스

Question

Language: Python

Difficulty: Gold 2

해당 문제에서 구현해야될 부분은 크게 4가지이다.

몬스터의 공격
빈칸 당겨주기
인접한 몬스터에 대한 제거
새로운 몬스터 맵핑

각 세부 과정은 아래와 같다

몬스터의 공격

중심 좌표를 기준으로 주어진 방향, 크기 만큼 이동하면서 해당 경로 내에 있는 몬스터 제거하고 포인트를 누적한다.

#몬스터 공격
def attack_monsters(dir,size):
    global board

    points=0

    #중심 좌표
    center_row=n//2
    center_col=n//2

    for i in range(1,size+1):
        value=board[center_row+dy[dir]*i][center_col+dx[dir]*i]
        board[center_row+dy[dir]*i][center_col+dx[dir]*i]=0
        points+=value

    return points

빈칸 당겨주기

2차원 배열 상태에서 빈칸을 당겨주는 작업은 까다롭다. 따라서 리스트 형태로 변환한다. 이때, 중심좌표에서 첫좌표까지 이동하면서 리스트에 값을 삽입해야하기 때문에 아래와 같이 움직임에 대한 리스트를 사전에 정의한다.

#중심에서 꼬리 방향까지 나가는 이동방식 
def find_movements():
    movements=[]
    dir_fragments=[[2,1],[0,3]]
    for i in range(1,n):
        dir_fragment=dir_fragments[i%2 == 0]
        movements.extend([dir_fragment[0]]*i)
        movements.extend([dir_fragment[1]]*i)
    
    movements.extend([2]*(n-1))
    return movements

#빈칸이 있는 칸 당겨주기: 2차원 --> 1차원
def flatten_board(movements):
    monster_list=[]

    row=n//2
    col=n//2

    for dir in movements:
        row+=dy[dir]
        col+=dx[dir]

        monster=board[row][col]
        #빈칸인 경우 넘어간다.
        if monster == 0:
            continue

        monster_list.append(monster)
    
    return monster_list

인접한 몬스터에 대한 제거

인접한 몬스터에 대해서 같은 값을 가지는 몬스터가 4개 이상인 경우 제거하고, 이러한 경우가 발생할 때까지 계속해서 진행한다. 이는 리스트를 순회하면서 몬스터의 값에 대한 갯수를 누적하면서 4이상이 되는 경우에는 제거하고, 그렇지 않은 경우에는 새로운 리스트에 추가하는 방식으로 진행한다. 제거된 몬스터 만큼 포인트를 누적한다.

#4개 이상의 인접한 값이 있는 경우 제거
def destroy_monster(monster_list):
    points=0
    while True:
        #새롭게 초기화된 몬스터 리스트
        new_monster_list=[]

        #이전까지 저장된 몬스터의 값과 갯수
        value_count=0
        prev_value=monster_list[0]

        for next_value in monster_list:
            #다음 값이 다른 몬스터의 값인 경우
            if next_value != prev_value:
                
                #같은 값을 가진 몬스터의 갯수가 4개 보다 작을 때만 리스트에 추가한다.
                if value_count < 4:
                    new_monster_list.extend([prev_value]*value_count)
                #4이상인 경우 터트리고 점수를 획득한다.
                else:
                    points+=(prev_value*value_count)

                prev_value=next_value
                value_count=1
            else:
                value_count+=1
        
        #마지막의 경우에 대한 처리
        #같은 값을 가진 몬스터의 갯수가 4개 보다 작을 때만 리스트에 추가한다.
        if value_count < 4:
            new_monster_list.extend([prev_value]*value_count)
        else:
            points+=(prev_value*value_count)

        #더 이상 위의 경우가 없는 경우 빠져나온다.
        if len(new_monster_list) == len(monster_list):
            break

        #크기가 변한 경우 계속해서 진행한다.
        monster_list=new_monster_list[:]
    
    return monster_list,points

새로운 몬스터 맵핑

3번의 과정이 완료된 이후에는 남아있는 몬스터에 대해서 (값의 갯수, 몬스터의 값) 형태로 새롭게 매핑해야한다. 이 경우도 3번과 비슷한 로직으로 처리할 수 있다.

#값,갯수 짝으로 맵핑: 1차원 --> 2차원
def mapping_monster(monster_list):

    #새롭게 초기화된 몬스터 리스트
    new_monster_list=[]

    #이전까지 저장된 몬스터의 값과 갯수
    value_count=0
    prev_value=monster_list[0]

    for next_value in monster_list:
        #다음 값이 다른 몬스터의 값인 경우
        if next_value != prev_value:
            #몬스터의 값과 갯수로 맵핑한 것을 리스트에 삽입한다.
            new_monster_list.extend([value_count,prev_value])
            prev_value=next_value
            value_count=1
        else:
            value_count+=1
    
    #마지막의 경우에 대한 처리
    new_monster_list.extend([value_count,prev_value])

    return new_monster_list

이후 1차원 리스트를 2차원 맵형태로 변환하는 작업을 수행한다. 이때에도 2번 마찬가지로 중심 좌표에서 첫 좌표를 이동하는 movements를 활용하여 이동하면서 값들을 2차원 배열에 표시한다.

def floaten(movements,monster_list):
    global board

    new_board=[[0] * n for _ in range(n)]
    length=len(monster_list)
    index=0

    #중심 좌표
    row=n//2
    col=n//2

    #맵핑해야되는 리스트가 기존의 2차원 배열보다 큰 경우 나머지 부분을 자른다.
    if length > len(movements):
        length=len(movements)
        monster_list=monster_list[:length]

    for index in range(length):
        dir=movements[index]
        row+=dy[dir]
        col+=dx[dir]

        new_board[row][col]=monster_list[index]
    
    for row in range(n):
        for col in range(n):
            board[row][col]=new_board[row][col]

Solution

#중심에서 꼬리 방향까지 나가는 이동방식 
def find_movements():
    movements=[]
    dir_fragments=[[2,1],[0,3]]
    for i in range(1,n):
        dir_fragment=dir_fragments[i%2 == 0]
        movements.extend([dir_fragment[0]]*i)
        movements.extend([dir_fragment[1]]*i)
    
    movements.extend([2]*(n-1))
    return movements

#몬스터 공격
def attack_monsters(dir,size):
    global board

    points=0

    #중심 좌표
    center_row=n//2
    center_col=n//2

    for i in range(1,size+1):
        value=board[center_row+dy[dir]*i][center_col+dx[dir]*i]
        board[center_row+dy[dir]*i][center_col+dx[dir]*i]=0
        points+=value

    return points

    
#빈칸이 있는 칸 당겨주기: 2차원 --> 1차원
def flatten_board(movements):
    monster_list=[]

    row=n//2
    col=n//2

    for dir in movements:
        row+=dy[dir]
        col+=dx[dir]

        monster=board[row][col]
        #빈칸인 경우 넘어간다.
        if monster == 0:
            continue

        monster_list.append(monster)
    
    return monster_list


#4개 이상의 인접한 값이 있는 경우 제거
def destroy_monster(monster_list):
    points=0
    while True:
        #새롭게 초기화된 몬스터 리스트
        new_monster_list=[]

        #이전까지 저장된 몬스터의 값과 갯수
        value_count=0
        prev_value=monster_list[0]

        for next_value in monster_list:
            #다음 값이 다른 몬스터의 값인 경우
            if next_value != prev_value:
                
                #같은 값을 가진 몬스터의 갯수가 4개 보다 작을 때만 리스트에 추가한다.
                if value_count < 4:
                    new_monster_list.extend([prev_value]*value_count)
                #4이상인 경우 터트리고 점수를 획득한다.
                else:
                    points+=(prev_value*value_count)

                prev_value=next_value
                value_count=1
            else:
                value_count+=1
        
        #마지막의 경우에 대한 처리
        #같은 값을 가진 몬스터의 갯수가 4개 보다 작을 때만 리스트에 추가한다.
        if value_count < 4:
            new_monster_list.extend([prev_value]*value_count)
        else:
            points+=(prev_value*value_count)

        #더 이상 위의 경우가 없는 경우 빠져나온다.
        if len(new_monster_list) == len(monster_list):
            break

        #크기가 변한 경우 계속해서 진행한다.
        monster_list=new_monster_list[:]
    
    return monster_list,points


#값,갯수 짝으로 맵핑: 1차원 --> 2차원
def mapping_monster(monster_list):

    #새롭게 초기화된 몬스터 리스트
    new_monster_list=[]

    #이전까지 저장된 몬스터의 값과 갯수
    value_count=0
    prev_value=monster_list[0]

    for next_value in monster_list:
        #다음 값이 다른 몬스터의 값인 경우
        if next_value != prev_value:
            #몬스터의 값과 갯수로 맵핑한 것을 리스트에 삽입한다.
            new_monster_list.extend([value_count,prev_value])
            prev_value=next_value
            value_count=1
        else:
            value_count+=1
    
    #마지막의 경우에 대한 처리
    new_monster_list.extend([value_count,prev_value])

    return new_monster_list

def floaten(movements,monster_list):
    global board

    new_board=[[0] * n for _ in range(n)]
    length=len(monster_list)
    index=0

    #중심 좌표
    row=n//2
    col=n//2

    #맵핑해야되는 리스트가 기존의 2차원 배열보다 큰 경우 나머지 부분을 자른다.
    if length > len(movements):
        length=len(movements)
        monster_list=monster_list[:length]

    for index in range(length):
        dir=movements[index]
        row+=dy[dir]
        col+=dx[dir]

        new_board[row][col]=monster_list[index]
    
    for row in range(n):
        for col in range(n):
            board[row][col]=new_board[row][col]

    
def solution():
    #중심에서 첫번째 좌표까지의 이동
    movements=find_movements()
    total_points=0

    for dir, size in rounds:
        #몬스터 공격
        points=attack_monsters(dir,size)
        total_points+=points

        #빈칸이 있는 칸 당겨주기: 2차원 --> 1차원
        monster_list=flatten_board(movements)

        #4개 이상의 인접한 값이 있는 경우 제거
        monster_list,points=destroy_monster(monster_list)
        total_points+=points

        #값,갯수 짝으로 맵핑
        monster_list=mapping_monster(monster_list)

        #2차원으로 매핑
        floaten(movements,monster_list)

    print(total_points)

if __name__ == "__main__":
    n,m=map(int,input().split())
    board=[list(map(int,input().split())) for _ in range(n)]
    rounds=[list(map(int,input().split())) for _ in range(m)]

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

    solution()

Twitter Facebook LinkedIn

Jehyun Jung

[Samsung] 2021-2 오후 2번 미로 타워 디펜스

[Samsung] 2021-2 오후 2번 미로 타워 디펜스

Question

Language: Python

Difficulty: Gold 2

Solution

공유하기

댓글남기기

참고

Typescript Module Issue

Changing Java Version in Linux

[BOJ] Q1725 히스토그램

[Programmers] Q176962 과제 진행하기