삼성 SW역량테스트 기출 / 2023 상반기 오전 1번 문제 포탑부수기 - BFS (조건문 확인 계속하기) / Python 파이썬

 

*문제 출처는 코드트리에 있습니다.

 

삼멘

문제 제목: 포탑 부수기 - BFS

문제 사이트: https://www.codetree.ai/training-field/frequent-problems/problems/destroy-the-turret/submissions?page=3&pageSize=5

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

---

sudo

 

sudo에는 alive가 있는데 고치다보니 alive는 의미가 없는거같아서 그냥 없애줬다

"""
sudo
# 포탑 부수기

# 최초에 공격력이 0일 수 있음. 0이하면 공격X

# 공격력이 줄거나 늘어날 수 있음
attacker = [] # 매턴 공격자 정보 저장(find 함수 실행시는 이전 공격자가 됨)
target_potop = [] # 피공격자(가장 공격력 높음)
alive = [] # 공격받기 전 살아있는 포탑의 좌표

## attack,  공격자는 자신을 제외한 가장 강한 포탑 공격 ##

def first_attack(): # 첫번쨰 공격 레이저 (bfs)
    # 공격자의 위치에서 공격 대상 포탑까지의 최단 경로로 공격
    # 부서진 포탑은 못타고, 살아있는 포탑 위로 넘어가야함

    ax,ay = attacker[-1][0], attacker[-1][1]
    queue = deuqe([[ax,ay]])
    direct = ((0,1),(1,0),(0,-1),(-1,0)) #우하좌상
    visited = [[[False] * M] for _ in range(N)]
    while queue:
        q = queue.popleft()
        qx, qy = q[0], q[1]
        if qx,qy == target:
            return
        for i in range(4):
            xx = qx + direct[i][0]
            yy = qy + direct[i][1]
            
    # 경로 target 못만나면 포탄 공격

def second_attack(): # 첫번째에 공격 못하면 포탄 공격
    # 격자 범위를 벗어나는 것도 고려해야함
    # 해당 포탄의 8 방향이 피해를 입음 (격자 벗어나면 반대편 격자로)


def find_attacker():
    global attacker, target_potop, maps, alive
    # 가장 약한 포탑이 공격자가됨 - 탐색
    MIN = float('inf')
    MIN_point = [] # 공격자 선정

    MAX = flaot('-inf') # 피공격자 선정
    MAX_point = [] # target_potop

    # 가장 공격력 낮은 포탑이 2 이상이면
    # 가장 최근에 공격 - 전역변수 > 행 열 합 가장 큰 포탑 > 열값 가장 큰 포탑
    for i in range(N):
        for j in range(M):
            # 살아남은 포탑 좌표 찾기
            if maps[i][j] > 0:
                alive.append([i,j])
            # 공격력 낮은 포탑 찾기
            if maps[i][j] < MIN:
                MIN = maps[i][j]
                MIN_point = [i,j]
            elif maps[i][j] == MIN:
                # 가장 최근에 공격 - 전역변수 
                if attacker and maps[attacker[-1][0]][attacker[-1][1]] == MIN: # 최근 공격자
                    MIN_point = find_attacker
                # 행렬합 큰
                elif (MIN_point[0] + MIN_point[1]) < i + j:
                    MIN_point = [i,j]
                # 열값 큰
                elif ((MIN_point[0] + MIN_point[1]) == i + j) and MIN_point[1] < j"
                    MIN_point = [i,j]
            
            if maps[i][j] > MAX:
                MAX = maps[i][j] # ... MAX 로직 작성

            
    
    # 공격력은 (현재 공격력 + N X M 만큼 늘어남)
    if MIN_point:
        maps[MIN_point[0]][MIN_point[1]] += (N + M)
    else: # MIN_POINT 못찾으면 가장 최근에 공격한 애
        ax,ay = attacker[-1][0],attacker[-1][0]
        MIN_point = [ax,ay]
    attacker.append([MIN_point[0],MIN_point[1]])

while K > 0:
    # 1. 공격자, 피공격자 선정
    find_attacker() # 시간 초과시 0인 수들은 무시할 것도 고려
    # 2. 공격자의 공격
    result1 = first_attack() # 레이저 공격시도
    if not result1: # 레이저 공격이 안된다면
        result2 = second_attack() #포탄 공격
    heal_potop() # 공격과 무관했던 포탑들 공격력 증가
    K -= 1

print(strong_potop) # 남아있는 포탑중 가장 강한 포탑 공격력 출력


"""

 

나의 풀이

 

first_attack() 에서 

레이저 포탑 부술때 바로 옆에 있는 포탑을 부수면,

지나온 경로 path 가 [] 으로 뜬다.

 

근데 path 자체로 처음에 True False를 구하려고하니 오류가 자꾸 났음..!(타겟하는 애를 쳤는지/ 안쳤는지)

그래서 조건문을 수정해줬더니 통과됐다.

 

앞으로 리스트 자체로 True False 를 바로 급하게 받는거보다..확실한 Flag 변수를 선언해야겠음

이전코드

    attacked_potop = first_attack()  # 레이저 공격시도
    if not attacked_potop:  # 레이저 공격이 안된다면
        attacked_potop = second_attack()  # 포탄 공격

여기서 first_attack()에서 반환하는 값은 BFS로 지나온 경로였음 

근데 바로 옆에 있는 애를 칠때는 BFS 경로에 아무것도 안담겨서 attacked_potop이 [] 라서 조건문에 걸려서 포탄공격도 하는 중첩 공격을 하게됨..

 

Flag 를 제대로 수정하고 난 뒤 최종코드

 

from collections import deque

# 포탑 부수기

# 최초에 공격력이 0일 수 있음. 0이하면 공격X
N,M,K = map(int,input().split())
maps = [list(map(int,input().split())) for _ in range(N)]

# 공격력이 줄거나 늘어날 수 있음
attacker = []  # 매턴 공격자 정보 저장(find 함수 실행시는 이전 공격자가 됨)
target_potop = []  # 피공격자(가장 공격력 높음)


# 공격을 했던 시점들 저장
attack_timeline = [[0]*M for _ in range(N)]

for i in range(N):
    for j in range(M):
        attack_timeline[i][j] = 0

## attack,  공격자는 자신을 제외한 가장 강한 포탑 공격 ##
def first_attack():
    global maps
    # 첫번쨰 공격 레이저 (bfs)
    # 공격자의 위치에서 공격 대상 포탑까지의 최단 경로로 공격
    # 부서진 포탑은 못타고, 살아있는 포탑 위로 넘어가야함
    ax, ay = attacker[0], attacker[1]
    tx, ty = target_potop[0], target_potop[1]
    queue = deque([[ax, ay,[]]])
    direct = ((0, 1), (1, 0), (0, -1), (-1, 0))  # 우하좌상
    visited = [[False] * M for _ in range(N)]
    visited[ax][ay] = True
    # 경로 지나온 애들도 피해입음
    path = [] # [i,j,score] # 지나온 애들의 스코어와 [i,j]가 깎인다하자...
    target_attack = False # 첫번째 공격에서 포탑을 공격했는지 유무
    while queue:
        q = queue.popleft()
        qx, qy, qpath = q[0], q[1],q[2]
        if [qx, qy] == [tx, ty]:
            target_attack = True
            path = qpath
            break
        for i in range(4):
            xx = qx + direct[i][0]
            yy = qy + direct[i][1]
            xx = abs(xx % N)
            yy = abs(yy % M)
            if 0 <= xx < N and 0 <= yy < M and maps[xx][yy] > 0 and visited[xx][yy] == False:
                visited[xx][yy] = True
                if xx == tx and yy == ty:
                    queue.append([xx, yy, qpath])
                    break
                else:
                    npath = qpath + [[xx, yy]]
                    queue.append([xx, yy, npath])

    # 경로 target 만나면 포탑 공격
    if target_attack == True:
        # 지나온 길은 공격자의 공격력의 절반
        half_score = maps[ax][ay] // 2
        score = maps[ax][ay]
        for x,y in path:
            if maps[x][y] - half_score < 0:
                maps[x][y] = 0
            else:
                maps[x][y] -= half_score
        if maps[tx][ty] - score < 0:
            maps[tx][ty] = 0 # 대상은 전체 피해
        else:
            maps[tx][ty] -= score

    return path, target_attack # 공격 받은 애들 좌표 저장

def second_attack():  # 첫번째에 공격 못하면 포탄 공격
    direct = ((1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,1),(1,-1),(-1,-1))
    x,y = target_potop[0], target_potop[1]
    half_score = maps[attacker[0]][attacker[1]] // 2
    attacked_potop = []
    for i in range(len(direct)):

        xx = x + direct[i][0]
        yy = y + direct[i][1]

        if xx >= N or xx < 0:
            xx = abs(xx % N)
        if yy >= M or yy < 0:
            yy = abs(yy % M)
        if [xx, yy] != attacker:
            if maps[xx][yy] > 0:
                if maps[xx][yy] - half_score > 0:
                    maps[xx][yy] -= half_score
                else:
                    maps[xx][yy] = 0
                attacked_potop.append([xx, yy])
    if maps[x][y] - maps[attacker[0]][attacker[1]] > 0:
        maps[x][y] -= maps[attacker[0]][attacker[1]]
    else:
        maps[x][y] = 0
    return attacked_potop
# 격자 범위를 벗어나는 것도 고려해야함
# 해당 포탄의 8 방향이 피해를 입음 (격자 벗어나면 반대편 격자로)

def heal_potop(attacked_potop):
    global maps
    for i in range(N):
        for j in range(M):
            if maps[i][j] > 0:
                if [i,j] not in attacked_potop and [i,j] != attacker and [i,j] != target_potop:
                    maps[i][j] += 1
def find_attacker():
    global attacker, target_potop, maps
    # 가장 약한 포탑이 공격자가됨 - 탐색
    MIN = float('inf')
    MIN_point = []  # 공격자 선정

    MAX = float('-inf')  # 피공격자 선정
    MAX_point = []  # target_potop

    # 가장 공격력 낮은 포탑이 2 이상이면
    # 가장 최근에 공격 - 전역변수 > 행 열 합 가장 큰 포탑 > 열값 가장 큰 포탑
    for i in range(N):
        for j in range(M):
            # 살아남은 포탑 좌표 찾기
            if maps[i][j] > 0:
                # alive[i*M] = 1
                # 공격력 낮은 포탑 찾기
                if maps[i][j] < MIN:
                    MIN = maps[i][j]
                    MIN_point = [i, j]
                elif maps[i][j] == MIN:
                    # 가장 최근에 공격 - 전역변수
                    if attack_timeline[i][j] > attack_timeline[MIN_point[0]][MIN_point[1]]: # 최근 공격자
                        MIN_point = [i,j]
                    elif attack_timeline[i][j] == attack_timeline[MIN_point[0]][MIN_point[1]]: # 공격시점이 0일때만 같긴함
                        # 행렬합 큰
                        if (MIN_point[0] + MIN_point[1]) < i + j:
                            MIN_point = [i, j]
                        # 열값 큰
                        elif ((MIN_point[0] + MIN_point[1]) == i + j) and MIN_point[1] < j:
                            MIN_point = [i, j]

                # 공격력 큰 포탑 찾기
                if maps[i][j] > MAX:
                    MAX = maps[i][j]
                    MAX_point = [i, j]
                elif maps[i][j] == MAX:
                    # 공격한지 가장 오래된 포탑이 가장 강한 포탑
                    if attack_timeline[i][j] < attack_timeline[MAX_point[0]][MAX_point[1]]:
                        MAX_point = [i, j]
                    elif attack_timeline[i][j] == attack_timeline[MAX_point[0]][MAX_point[1]]:
                        # 행렬합 작은
                        if (MAX_point[0] + MAX_point[1]) > i + j:
                            MAX_point = [i, j]
                        # 열값 작은
                        elif ((MAX_point[0] + MAX_point[1]) == i + j) and MAX_point[1] > j:
                            MAX_point = [i, j]
    attacker = MIN_point
    target_potop = MAX_point
    if attacker != target_potop:
        maps[MIN_point[0]][MIN_point[1]] += (N + M)
time = 1
while K > 0:
    # 1. 공격자, 피공격자 선정
    find_attacker()  # 시간 초과시 0인 수들은 무시할 것도 고려
    attack_timeline[attacker[0]][attacker[1]] = time
    if attacker == target_potop:
        # maps[attacker[0]][attacker[1]] += K
        break
    # 2. 공격자의 공격
    # print(time)
    # print('attacker 선정')
    # print('attacker: ',attacker,'target: ',target_potop)
    # for i in maps:
    #     print(i)
    attacked_potop, target_attack = first_attack()  # 레이저 공격시도
    if target_attack == False:  # 레이저 공격이 안된다면
        attacked_potop = second_attack()  # 포탄 공격
    # result는 공격 받은 애들 좌표 위치 저장
    # print('공격후')
    # for i in maps:
    #     print(i)
    heal_potop(attacked_potop)  # 공격과 무관했던 포탑들 공격력 증가
    # print('힐링후')
    # for i in maps:
    #     print(i)
    # print()
    K -= 1
    time += 1

MAX = float('-inf')
for i in range(N):
    for j in range(M):
        if maps[i][j] > MAX:
            MAX = maps[i][j]
print(MAX)  # 남아있는 포탑중 가장 강한 포탑 공격력 출력

 

굳~

---

※ 알아야 할 것

- 조건문이랑 Flag 설정 확실하게