[삼성 SW 역량 테스트 기출, Python] 메두사와 전사들 풀이

2024 오후 하반기 1번 문제였던 '메두사와 전사들' 문제 풀이입니다.

 

1. 문제 링크

https://www.codetree.ai/ko/frequent-problems/problems/medusa-and-warriors/description?introductionSetId=&bookmarkId=

 

2. 한줄평

알고리즘이 어렵진 않지만 챙겨야할 디테일이 너무너무 많은 문제ㅠㅠ

문제 조건에 전사가 0명 이상이라고 해서 0명일때는 전사위치 정보를 입력 안받도록 처리했었습니다..하지만 문제를 보면 '다음줄에 M명의 전사 좌표가 나온다'고 되어있으므로 전사가 0명일때도(M=0일때도) 빈 line을 입력받아야한다는것! 그래도 코테 전에 이런 디테일 때문에 틀려봤으니 실전에서는 같은 문제로 틀릴것 같진 않네요☺️

 

3. 풀이

N, M = map(int, input().split())
s_r, s_c, e_r, e_c = map(int, input().split())
current_see_matrix = None
current_monster_pos = (s_r, s_c)
park_pos = (e_r, e_c)
current_is_move_list = None

hero_pos_list = []
hero_pos_info = list(map(int, input().split()))
for i in range(0, M):
    hero_pos_list.append((hero_pos_info[2*i], hero_pos_info[2*i+1]))

board = [list(map(int, input().split())) for _ in range(N)]

def get_see_matrix(pos, d, is_max = False, is_min = False):
    '''
    dir: 상하좌우 각각 0, 1, 2, 3
    시야각인 곳은 1, 아닌 곳은 0으로 표시
    is_max: max 한계가 pos로 정해져있음(작은애들만)
    is_min: min 한계가 pos로 정해져있음(큰애들만)
    '''
    new_matrix = [[0]*N for _ in range(N)]
    pos_x, pos_y = pos

    if d == 0 or d ==1:
        if is_max == False:
            max_value = N-1
        else:
            max_value = pos_y
        if is_min == False:
            min_value = 0
        else:
            min_value = pos_y
    else:
        if is_max == False:
            max_value = N-1
        else:
            max_value = pos_x
        if is_min == False:
            min_value = 0
        else:
            min_value = pos_x

    if d == 0:
        length = 1
        for row in range(pos_x-1, -1, -1):
            for column in range(max(min_value, pos_y-length), min(pos_y+length+1, max_value+1)):
                new_matrix[row][column] = 1
            length += 1

    elif d == 1:
        length = 1
        for row in range(pos_x+1, N):
            for column in range(max(min_value, pos_y-length), min(pos_y+length+1, max_value+1)):
                new_matrix[row][column] = 1
            length += 1
    elif d == 2:
        length = 1
        for column in range(pos_y-1, -1, -1):
            for row in range(max(min_value, pos_x-length), min(pos_x+length+1, max_value+1)):
                new_matrix[row][column] = 1
            length += 1

    elif d ==3:
        length = 1
        for column in range(pos_y+1, N):
            for row in range(max(min_value, pos_x-length), min(pos_x+length+1, max_value+1)):
                new_matrix[row][column] = 1
            length += 1

    return new_matrix
    #
    # for i in range(N):
    #     print(new_matrix[i])

def get_final_see_matrix(d):
    '''
    시야각에 가린 버전의 matrix 제공
    '''
    monster_x, monster_y = current_monster_pos
    see_matrix = get_see_matrix(current_monster_pos, d)
    for hero_pos in hero_pos_list:
        hero_x, hero_y = hero_pos
        if see_matrix[hero_x][hero_y] == 1: # 시야각에 들어오는거
            if d == 0 or d ==1: # 상하방향일 경우
                if hero_y < monster_y:
                    hero_matrix = get_see_matrix(hero_pos, d, is_max=True)
                elif hero_y > monster_y:
                    hero_matrix = get_see_matrix(hero_pos, d, is_min=True)
                elif hero_y == monster_y:
                    hero_matrix = get_see_matrix(hero_pos, d, is_min=True, is_max=True)
            elif d == 2 or d ==3:
                if hero_x < monster_x:
                    hero_matrix = get_see_matrix(hero_pos, d, is_max=True)
                elif hero_x > monster_x:
                    hero_matrix = get_see_matrix(hero_pos, d, is_min=True)
                elif hero_x == monster_x:
                    hero_matrix = get_see_matrix(hero_pos, d, is_min=True, is_max=True)

            for i in range(N):
                for j in range(N):
                    if see_matrix[i][j] == 1 and hero_matrix[i][j] ==1:
                        see_matrix[i][j] = 0
        else:
            continue

    return see_matrix

def decide_current_see_matrix():
    '''
    네 방향 비교해서 current_see_matrix hero 가장 많은 방향으로 update하고
    돌이 된 hero 표시하는 current_is_move_list update하고
    돌이 된 hero갯수 return
    '''
    global current_see_matrix, current_is_move_list
    max_stone_hero_num = None
    max_see_matrix = None
    max_is_move_list = None
    for i in range(4):
        temp_see_matrix = get_final_see_matrix(i)
        temp_count = 0
        temp_is_move_list = [True] * len(hero_pos_list)
        for hero_idx in range(len(hero_pos_list)):
            hero_pos = hero_pos_list[hero_idx]
            hero_x, hero_y = hero_pos
            if temp_see_matrix[hero_x][hero_y] == 1:
                temp_count += 1
                temp_is_move_list[hero_idx] = False

        if max_stone_hero_num == None:
            max_see_matrix = temp_see_matrix
            max_stone_hero_num = temp_count
            max_is_move_list = temp_is_move_list
        elif temp_count > max_stone_hero_num:
            max_see_matrix = temp_see_matrix
            max_stone_hero_num = temp_count
            max_is_move_list = temp_is_move_list

    current_see_matrix = max_see_matrix
    current_is_move_list = max_is_move_list
    return max_stone_hero_num

from collections import deque
def set_monster_shortest_path():
    '''
    출발지와 목적지를 포함한 path return
    만약 최단거리 없을 경우 None을 return 함!!!!
    '''
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    is_visited_list = [[False] * N for _ in range(N)]
    queue = deque()
    queue.append((current_monster_pos, [current_monster_pos]))
    is_visited_list[current_monster_pos[0]][current_monster_pos[1]] = True

    while(queue):
        cur_pos, path = queue.popleft()
        if cur_pos == park_pos:
            return path
        else:
            for dir in range(4):
                new_x, new_y = cur_pos[0]+dx[dir], cur_pos[1]+dy[dir]
                if 0<=new_x<N and 0<=new_y<N:
                    if is_visited_list[new_x][new_y] == False:
                        if board[new_x][new_y] == 0:
                            queue.append(((new_x, new_y), path+[(new_x, new_y)]))
                            is_visited_list[new_x][new_y] = True


    return None

def get_distance(pos_1, pos_2):
    return abs(pos_1[0]-pos_2[0])+abs(pos_1[1]-pos_2[1])


def update_hero_pos(current_pos, step_idx):
    '''
    is_alive 확인된 hero의 current_pos 넣어주기
    step_idx는 1 or 2 (첫번째 이동인지 두번째 이동인지
    new_pos와 움직였는지 여부 return 함(안움직였으면 new_pos는 current_pos)
    '''
    if step_idx == 1:
        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]
    elif step_idx ==2:
        dx = [0, 0, -1, 1]
        dy = [-1, 1, 0, 0]

    current_x, current_y = current_pos
    for dir in range(4):
        new_x, new_y = current_x+dx[dir], current_y+dy[dir]
        if 0<=new_x<N and 0<=new_y<N:
            if current_see_matrix[new_x][new_y] == 0:
                if get_distance((new_x, new_y), current_monster_pos) < get_distance(current_pos, current_monster_pos):
                    return (new_x, new_y), True

    return current_pos, False


def one_simulation():
    global monster_shortest_path, current_is_move_list, hero_pos_list, current_monster_pos

    current_monster_pos = monster_shortest_path[0]
    if current_monster_pos == park_pos:
        return None
    monster_shortest_path = monster_shortest_path[1:]
    stone_num = decide_current_see_matrix()

    move_num = 0
    attack_num = 0
    new_hero_pos_list = []
    for hero_idx in range(len(hero_pos_list)):
        if current_is_move_list[hero_idx] == True:
            new_pos, is_move = update_hero_pos(hero_pos_list[hero_idx], 1)
            if is_move:
                move_num+=1
                if new_pos == current_monster_pos:
                    attack_num += 1
                else:
                    new_pos, is_move = update_hero_pos(new_pos, 2)
                    if is_move:
                        move_num += 1
                        if new_pos == current_monster_pos:
                            attack_num +=1
            if new_pos != current_monster_pos:
                new_hero_pos_list.append(new_pos)
        else:
            new_hero_pos_list.append(hero_pos_list[hero_idx])
    hero_pos_list = new_hero_pos_list

    return move_num, stone_num, attack_num


monster_shortest_path = set_monster_shortest_path()
if monster_shortest_path == None:
    print(-1)
else:
    monster_shortest_path = monster_shortest_path[1:]
    while(True):
        result = one_simulation()
        if result == None:
            print(0)
            break
        else:
            move_num, stone_num, attack_num = result
            print(move_num, stone_num, attack_num)