728x90
*문제 출처는 코드트리에 있습니다.
삼멘
문제 제목: 포탑 부수기 - BFS
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 > SAMSUNG SWT(SW역량 테스트)' 카테고리의 다른 글
삼성 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 |