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

2024. 10. 8. 17:10·coding test - python/Code Tree
728x90
반응형

 

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

 

삼멘

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

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

 

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

국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

www.codetree.ai


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 설정 확실하게

 

 

728x90
반응형

'coding test - python > Code Tree' 카테고리의 다른 글

삼성 SW역량테스트 기출 / 2023 상반기 오후 1번 문제 메이즈러너 - 회전, BFS, 가장 작은 정사각형 찾고 회전 / Python 파이썬  (4) 2024.10.09
달팽이 너같은거...  (5) 2024.10.09
삼성 SW역량테스트 기출 / 2024 상반기 오전 1번 문제 고대 문명 유적 탐사 - 얕은복사, 깊은 복사 / Python 파이썬  (8) 2024.10.05
삼성 SW역량테스트 기출 / 2024 상반기 오후 1번 문제 마법의 숲 탐색 - 회전하면서 하강 / Python 파이썬  (0) 2024.10.02
삼성 SW역량테스트 기출 / 2023 하반기 오후 1번 문제루돌프의 반란 - 시뮬레이션 / Python 파이썬  (0) 2024.09.30
'coding test - python/Code Tree' 카테고리의 다른 글
  • 삼성 SW역량테스트 기출 / 2023 상반기 오후 1번 문제 메이즈러너 - 회전, BFS, 가장 작은 정사각형 찾고 회전 / Python 파이썬
  • 달팽이 너같은거...
  • 삼성 SW역량테스트 기출 / 2024 상반기 오전 1번 문제 고대 문명 유적 탐사 - 얕은복사, 깊은 복사 / Python 파이썬
  • 삼성 SW역량테스트 기출 / 2024 상반기 오후 1번 문제 마법의 숲 탐색 - 회전하면서 하강 / Python 파이썬
sillon
sillon
꾸준해지려고 합니다..
    반응형
  • sillon
    sillon coding
    sillon
  • 전체
    오늘
    어제
    • menu (614)
      • notice (2)
      • python (68)
        • 자료구조 & 알고리즘 (23)
        • 라이브러리 (19)
        • 기초 (8)
        • 자동화 (14)
        • 보안 (1)
      • coding test - python (301)
        • Programmers (166)
        • 백준 (76)
        • Code Tree (22)
        • 기본기 문제 (37)
      • coding test - C++ (5)
        • Programmers (4)
        • 백준 (1)
        • 기본기문제 (0)
      • 공부정리 (5)
        • 신호처리 시스템 (0)
        • Deep learnig & Machine lear.. (41)
        • Data Science (18)
        • Computer Vision (17)
        • NLP (40)
        • Dacon (2)
        • 모두를 위한 딥러닝 (강의 정리) (4)
        • 모두의 딥러닝 (교재 정리) (9)
        • 통계 (2)
      • HCI (23)
        • Haptics (7)
        • Graphics (11)
        • Arduino (4)
      • Project (21)
        • Web Project (1)
        • App Project (1)
        • Paper Project (1)
        • 캡스톤디자인2 (17)
        • etc (1)
      • OS (10)
        • Ubuntu (9)
        • Rasberry pi (1)
      • App & Web (9)
        • Android (7)
        • javascript (2)
      • C++ (5)
        • 기초 (5)
      • Cloud & SERVER (8)
        • Git (2)
        • Docker (1)
        • DB (4)
      • Paper (7)
        • NLP Paper review (6)
      • 데이터 분석 (0)
        • GIS (0)
      • daily (2)
        • 대학원 준비 (0)
      • 영어공부 (6)
        • job interview (2)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    백준
    Python
    소수
    programmers
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
sillon
삼성 SW역량테스트 기출 / 2023 상반기 오전 1번 문제 포탑부수기 - BFS (조건문 확인 계속하기) / Python 파이썬
상단으로

티스토리툴바