[Samsung] 2021-2 오후 1번 팩맨

[Samsung] 2021-2 오후 1번 팩맨

Question

Language: Python

Difficulty: Gold 1

해당 문제의 풀이는 마법사 상어와 복제를 참고하면 된다.

Solution 1

from collections import deque
#몬스터 복제 시도
def ready_to_reproduce(monster_map):
    eggs=[]

    for row in range(4):
        for col in range(4):
            if len(monster_map[row][col]) !=0:
                for dir in monster_map[row][col]:
                    eggs.append((row,col,dir))
    return eggs

#몬스터의 이동
def move_monsters(monster_map,dead_map):
    new_monster_map=[[[] for _ in range(4)] for _ in range(4)]

    for row in range(4):
        for col in range(4):
            if len(monster_map[row][col]) !=0:
                for dir in monster_map[row][col]:
                    #8번의 회전 시도 가능
                    for i in range(9):
                        next_dir=(dir+i)%8
                        next_row=row+dy[next_dir]
                        next_col=col+dx[next_dir]
                        #격자를 벗어나거나 팩맨이 있거나 시체가 있는 경우에는 반시계 방향으로 회전
                        if not check_range(next_row,next_col) or (next_row,next_col) == (packman_row,packman_col) or dead_map[next_row][next_col] !=0:
                            continue
                        new_monster_map[next_row][next_col].append(next_dir)
                        break
                        
                    #8번의 회전으로 모두 수행한 경우 그 자리에서 이동하지 않는다.
                    else:
                        new_monster_map[row][col].append(dir)

    #변경 사항 반영
    for row in range(4):
        for col in range(4):
            monster_map[row][col]=new_monster_map[row][col][:]

#팩맨이 이동가능한 경로 찾기
def possible_packman_moves(index,monster_map,row,col,monster_count,path):
    global packman_candidates,visited
    if index == 3:
        packman_candidates.append((monster_count,path))
        return

    #상좌하우 방향만 검사한다.
    for dir in range(0,8,2):
        next_row=row+dy[dir]
        next_col=col+dx[dir]

        #격자를 벗어나는 경우
        if not check_range(next_row,next_col):
            continue
        
        #이미 이전에 방문한 경우 
        if visited[next_row][next_col]:
            possible_packman_moves(index+1,monster_map,next_row,next_col,monster_count,path+str(dir))
            continue

        visited[next_row][next_col]=True
        possible_packman_moves(index+1,monster_map,next_row,next_col,monster_count+len(monster_map[next_row][next_col]),path+str(dir))
        visited[next_row][next_col]=False



#팩맨의 이동
def move_packman(monster_map,dead_map):  
    global packman_row,packman_col,packman_candidates,visited
    packman_candidates=[]
    visited=[[False] * 4 for _ in range(4)]
    
    #가능한 이동경로 모두 찾기
    possible_packman_moves(0,monster_map,packman_row,packman_col,0,"")

    packman_candidates.sort(key=lambda x: (-x[0],x[1]))
    _,path=packman_candidates[0]

    for dir in path:
        dir=int(dir)

        packman_row+=dy[dir]
        packman_col+=dx[dir]

        #이동과정에 몬스터가 있는 경우 몬스터는 죽이고, 시체는 생성한다.
        if len(monster_map[packman_row][packman_col]) !=0:
            monster_map[packman_row][packman_col]=[]
            dead_map[packman_row][packman_col]=3


#시체의 소멸 진행
def remove_dead(dead_map):
    #시체의 생존 기간 감소
    for row in range(4):
        for col in range(4):
            if dead_map[row][col] > 0:
                dead_map[row][col]-=1

#몬스터 복제의 완료
def make_monster(monster_map,eggs):
    for row,col,dir in eggs:
        monster_map[row][col].append(dir)

#범위 확인
def check_range(row,col):
    if row < 0 or row >=4 or col < 0 or col>=4:
        return False
    return True

def solution():
    #몬스터가 저장되어 있는 맵
    monster_map=[[[] for _ in range(4)] for _ in range(4)]
    #시체 맵
    dead_map=[[0] * 4 for _ in range(4)]

    #몬스터 맵에 몬스터 표시
    for row,col,dir in monsters:
        monster_map[row][col].append(dir)

    for i in range(t):
        eggs=ready_to_reproduce(monster_map)
        move_monsters(monster_map,dead_map)
        move_packman(monster_map,dead_map)
        remove_dead(dead_map)
        make_monster(monster_map,eggs)

    monster_count=0
    for row in range(4):
        for col in range(4):
            monster_count+=len(monster_map[row][col])
    
    print(monster_count)


if __name__ == "__main__":
    m,t=map(int,input().split())
    packman_row,packman_col=map(lambda x:int(x)-1,input().split())
    monsters=[list(map(lambda x: int(x)-1,input().split())) for _ in range(m)]
    packman_candidates=[]
    dy=[-1,-1,0,1,1,1,0,-1]
    dx=[0,-1,-1,-1,0,1,1,1]
    solution()

Solution 2

위의 풀이를 조금 개선한 코드이다.

방향이 8개로 정해져있다는 점에서, 각 좌표마다 각 방향을 가지는 물고기의 갯수를 유지하면서, 각 방향에 대해 일괄적으로 물고기들을 일괄적으로 변경하게 되면 시간 복잡도를 모든 물고기에서 4*4*8로 고정하여 효율적인 물고기 이동이 가능해진다.

def move_monsters(monster_map,dead_map):
    new_monster_map=[[[0]*8 for _ in range(4)] for _ in range(4)]

    for row in range(4):
        for col in range(4):
            for dir in range(8):
                if monster_map[row][col][dir] ==0:
                    continue
                #8번의 회전 시도 가능
                for i in range(9):
                    next_dir=(dir+i)%8
                    next_row=row+dy[next_dir]
                    next_col=col+dx[next_dir]
                    #격자를 벗어나거나 팩맨이 있거나 시체가 있는 경우에는 반시계 방향으로 회전
                    if not check_range(next_row,next_col) or (next_row,next_col) == (packman_row,packman_col) or dead_map[next_row][next_col] !=0:
                        continue
                    new_monster_map[next_row][next_col][next_dir]+=monster_map[row][col][dir]
                    break
                    
                #8번의 회전으로 모두 수행한 경우 그 자리에서 이동하지 않는다.
                else:
                    new_monster_map[row][col][dir]+=monster_map[row][col][dir]
    #변경 사항 반영
    for row in range(4):
        for col in range(4):
            for dir in range(8):
                monster_map[row][col][dir]=new_monster_map[row][col][dir]   

전체 코드

from collections import deque
#몬스터 복제 시도
def ready_to_reproduce(monster_map):
    eggs=[[[0]*8 for _ in range(4)] for _ in range(4)]

    for row in range(4):
        for col in range(4):
            for dir in range(8):
                eggs[row][col][dir]+=monster_map[row][col][dir]
    return eggs

#몬스터의 이동
def move_monsters(monster_map,dead_map):
    new_monster_map=[[[0]*8 for _ in range(4)] for _ in range(4)]

    for row in range(4):
        for col in range(4):
            for dir in range(8):
                if monster_map[row][col][dir] ==0:
                    continue
                #8번의 회전 시도 가능
                for i in range(9):
                    next_dir=(dir+i)%8
                    next_row=row+dy[next_dir]
                    next_col=col+dx[next_dir]
                    #격자를 벗어나거나 팩맨이 있거나 시체가 있는 경우에는 반시계 방향으로 회전
                    if not check_range(next_row,next_col) or (next_row,next_col) == (packman_row,packman_col) or dead_map[next_row][next_col] !=0:
                        continue
                    new_monster_map[next_row][next_col][next_dir]+=monster_map[row][col][dir]
                    break
                    
                #8번의 회전으로 모두 수행한 경우 그 자리에서 이동하지 않는다.
                else:
                    new_monster_map[row][col][dir]+=monster_map[row][col][dir]

                    
    
    #변경 사항 반영
    for row in range(4):
        for col in range(4):
            for dir in range(8):
                monster_map[row][col][dir]=new_monster_map[row][col][dir]

#팩맨이 이동가능한 경로 찾기
def possible_packman_moves(index,monster_map,row,col,monster_count,path):
    global packman_candidates,visited
    if index == 3:
        packman_candidates.append((monster_count,path))
        return

    #상좌하우 방향만 검사한다.
    for dir in range(0,8,2):
        next_row=row+dy[dir]
        next_col=col+dx[dir]

        #격자를 벗어나는 경우
        if not check_range(next_row,next_col):
            continue
        
        #이미 이전에 방문한 경우 
        if visited[next_row][next_col]:
            possible_packman_moves(index+1,monster_map,next_row,next_col,monster_count,path+str(dir))
            continue

        visited[next_row][next_col]=True
        possible_packman_moves(index+1,monster_map,next_row,next_col,monster_count+sum(monster_map[next_row][next_col]),path+str(dir))
        visited[next_row][next_col]=False



#팩맨의 이동
def move_packman(monster_map,dead_map):  
    global packman_row,packman_col,packman_candidates,visited
    packman_candidates=[]
    visited=[[False] * 4 for _ in range(4)]
    
    #가능한 이동경로 모두 찾기
    possible_packman_moves(0,monster_map,packman_row,packman_col,0,"")

    packman_candidates.sort(key=lambda x: (-x[0],x[1]))
    _,path=packman_candidates[0]

    for dir in path:
        dir=int(dir)

        packman_row+=dy[dir]
        packman_col+=dx[dir]

        #이동과정에 몬스터가 있는 경우 몬스터는 죽이고, 시체는 생성한다.
        if sum(monster_map[packman_row][packman_col]) !=0:
            monster_map[packman_row][packman_col]=[0]*8
            dead_map[packman_row][packman_col]=3


#시체의 소멸 진행
def remove_dead(dead_map):
    #시체의 생존 기간 감소
    for row in range(4):
        for col in range(4):
            if dead_map[row][col] > 0:
                dead_map[row][col]-=1

#몬스터 복제의 완료
def make_monster(monster_map,eggs):
    for row in range(4):
        for col in range(4):
            for dir in range(8):
                monster_map[row][col][dir]+=eggs[row][col][dir]

#범위 확인
def check_range(row,col):
    if row < 0 or row >=4 or col < 0 or col>=4:
        return False
    return True


def solution():
    #몬스터가 저장되어 있는 맵
    monster_map=[[[0]*8 for _ in range(4)] for _ in range(4)]
    #시체 맵
    dead_map=[[0] * 4 for _ in range(4)]

    #몬스터 맵에 몬스터 표시
    for row,col,dir in monsters:
        monster_map[row][col][dir]+=1

    for i in range(t):
        eggs=ready_to_reproduce(monster_map)
        move_monsters(monster_map,dead_map)
        move_packman(monster_map,dead_map)
        remove_dead(dead_map)
        make_monster(monster_map,eggs)

    monster_count=0
    for row in range(4):
        for col in range(4):
            monster_count+=sum(monster_map[row][col])
    
    print(monster_count)


if __name__ == "__main__":
    m,t=map(int,input().split())
    packman_row,packman_col=map(lambda x:int(x)-1,input().split())
    monsters=[list(map(lambda x: int(x)-1,input().split())) for _ in range(m)]
    packman_candidates=[]
    dy=[-1,-1,0,1,1,1,0,-1]
    dx=[0,-1,-1,-1,0,1,1,1]
    solution()