알고리즘
[코드트리/Python] 포탄 부수기
스연
2023. 10. 13. 20:54
728x90
포탄 부수다 내 멘탈 부숨
1. 포탄부수기 (골1)
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
문제
풀이
CODE1 - 실패
from collections import deque
def solution(n, m, k, board):
HANDICAP = n + m
attacker_list = []
def get_attacker(board, attacker_list):
min_strongest = 1e9
min_list = []
# 공격력이 가장 낮은 포탑 찾기, 거꾸로 탐색해서 열이 큰 순서로 저장되게 하기
for i in range(n-1, -1, -1):
for j in range(m-1, -1, -1):
if 0 < board[i][j] < min_strongest:
min_strongest = board[i][j] # 최솟값 업데이트
min_list = [(i, j)] # 낮은 포탑 리스트 재정의
elif board[i][j] == min_strongest:
min_list.append((i, j))
# 공격력이 제일 낮은 포탑이 1개면 해당 좌표 반환
if len(min_list) == 1:
return min_list[0]
# 만약 공격력이 낮은 포탑이 2개 이상인 경우
else:
# 가장 최근에 공격한 포탑을 반환
for each in attacker_list[::-1]:
if each in min_list:
return each
# 행과 열의 합이 가장 큰 포탑 반환
biggest = 0
ans = (-1, -1)
for i in range(len(min_list)):
if min_list[i][0] + min_list[i][1] > biggest:
biggest = min_list[i][0] + min_list[i][1]
ans = min_list[i]
return ans
def get_victim(board, attacker_list):
max_strongest = 0
max_list = []
# 공격력이 가장 높은 포탑 찾기, 정방향으로 탐색해서 열이 작은 순서로 저장되게 하기
for i in range(n):
for j in range(m):
if i != attacker_list[-1][0] or j != attacker_list[-1][1]: # 공격자 제외
if max_strongest < board[i][j]:
max_strongest = board[i][j] # 최댓값 업데이트
max_list = [(i, j)] # 높은 포탑 리스트 재정의
elif board[i][j] == max_strongest:
max_list.append((i, j))
# 공격력이 제일 높은 포탑이 1개면 해당 좌표 반환
if len(max_list) == 1:
return max_list[0]
# 만약 공격력이 높은 포탑이 2개 이상인 경우
else:
# 가장 나중에 공격한 포탑을 반환 -> 가장 최근에 공격한 순서부터 존재하면 attacker_list에서 삭제
for each in attacker_list[::-1]:
if each in max_list:
# 공격 리스트에 하나만 있으면 어쩔 수 없이 리턴
if len(max_list) == 1:
return each
else:
# 아닌 경우 후보에서 해당 포탑 제외
max_list.remove(each)
# 행과 열의 합이 가장 작은 포탑 반환
smallest = 1e9
ans = (-1, -1)
for i in range(len(max_list)):
if max_list[i][0] + max_list[i][1] < smallest:
smallest = max_list[i][0] + max_list[i][1]
ans = max_list[i]
return ans
def bfs_laser(sx, sy, ex, ey):
visit_check = [[0 for _ in range(m)] for _ in range(n)]
queue = deque([])
queue.append((sx, sy, []))
visit_check[sx][sy] = 1
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0] # 우하좌상 반영
while queue:
x, y, route = queue.popleft()
for i in range(4):
nx, ny = (x + dx[i]) % n, (y + dy[i]) % m
if 0 <= nx < n and 0 <= ny < m:
if not visit_check[nx][ny] and board[nx][ny]:
visit_check[nx][ny] = 1
if nx == ex and ny == ey:
return True, route
else:
queue.append((nx, ny, route + [(nx, ny)]))
return False, []
# k번의 반복
for _ in range(k):
is_relation = [[0 for _ in range(m)] for _ in range(n)]
# 1. 공격자 선정
attacker_x, attacker_y = get_attacker(board, attacker_list)
# 1-1. 공격자 리스트 추가
attacker_list.append((attacker_x, attacker_y))
# 1-2. 핸디캡 적용
board[attacker_x][attacker_y] += HANDICAP
attack_amount = board[attacker_x][attacker_y]
# 2. 공격자의 공격
# 2-1. 자신을 제외한 가장 강한 포탑 찾기
victim_x, victim_y = get_victim(board, attacker_list)
is_relation[attacker_x][attacker_y] = 1
is_relation[victim_x][victim_y] = 1
# 3. 레이저 공격 or 포탄 공격
# 3-1. 레이저 공격 가능 여부 확인
can_laser_attack, route = bfs_laser(attacker_x, attacker_y, victim_x, victim_y)
# 3-2. 레이저 공격 가능
if can_laser_attack:
# 공격 경로에 있는 포탑 공격력 감소
if route:
for each in route:
board[each[0]][each[1]] -= (attack_amount // 2)
is_relation[each[0]][each[1]] = 1
# 공격 대상 포탑 공격력 감소
board[victim_x][victim_y] -= attack_amount
# 3-3. 레이저 공격 불가. 포탄 공격 수행
else:
board[victim_x][victim_y] -= attack_amount
dx, dy = [-1, -1, -1, 0, 0, 1, 1, 1], [-1, 0, 1, -1, 1, -1, 0, 1]
for i in range(8):
nx = (victim_x + dx[i]) % n
ny = (victim_y + dy[i]) % m
if board[nx][ny]:
if not (nx == attacker_x and ny == attacker_y):
if not (nx == victim_x and ny == victim_y):
board[nx][ny] -= (attack_amount // 2)
is_relation[nx][ny] = 1
# 4. 공격 후 공격력 0 이하의 포탑은 부서짐 처리 & 5. 포탑 정비 & 6. 부서지지 않은 포탑이 1개면 종료
not_broken = 0
for i in range(n):
for j in range(m):
if board[i][j] > 0:
not_broken += 1 # 6
else:
board[i][j] = 0 # 4
if not_broken == 1:
break
for i in range(n):
for j in range(m):
if board[i][j] > 0:
if not is_relation[i][j]:
board[i][j] += 1 # 5
# 7. 가장 강한 포탑의 공격력 출력
biggest = 0
for i in range(n):
for j in range(m):
if board[i][j] > biggest:
biggest = board[i][j]
print(biggest)
if __name__ == "__main__":
n, m, k = map(int, input().split())
board = []
for _ in range(n):
board.append(list(map(int, input().split())))
solution(n, m, k, board)
CODE2 - 성공
from collections import deque
def solution(n, m, k, board):
HANDICAP = n + m
attacker_dict = {}
for i in range(n):
for j in range(m):
attacker_dict[(i, j)] = 0
def get_attacker(board, attacker_dict):
min_strongest = 1e9
min_list = []
max_attack = 0
# 공격력이 가장 낮은 포탑 찾기
for i in range(n):
for j in range(m):
if 0 < board[i][j] < min_strongest:
min_strongest = board[i][j] # 최솟값 업데이트
min_list = [(i, j)] # 낮은 포탑 리스트 재정의
max_attack = attacker_dict[(i, j)]
elif board[i][j] == min_strongest:
# 최근 공격 시점이 더 최근이면 갱신
if attacker_dict[(i, j)] > max_attack:
max_attack = attacker_dict[(i, j)]
min_list = [(i, j)]
# 같으면 append, 작으면 신경 안쓰기
elif attacker_dict[(i, j)] == max_attack:
min_list.append((i, j))
# 공격력이 제일 낮은 포탑이 1개면 해당 좌표 반환
if len(min_list) == 1:
return min_list[0]
# 만약 공격력이 낮고 최근 공격 시점이 같은 포탑이 2개 이상인 경우
# 행과 열의 합이 가장 큰 포탑 반환 -> 아닐 경우 열이 큰 포탑 자동 찾기
else:
min_list.sort(key=lambda x: (-(x[0] + x[1]), -x[1]))
return min_list[0]
def get_victim(board, attacker_dict):
max_strongest = 0
max_list = []
min_attack = 1e9
# 공격력이 가장 높은 포탑 찾기, 정방향으로 탐색해서 열이 작은 순서로 저장되게 하기
for i in range(n):
for j in range(m):
if not (i == attacker_x and j == attacker_y): # 공격자 제외
if max_strongest < board[i][j]:
max_strongest = board[i][j] # 최댓값 업데이트
max_list = [(i, j)] # 높은 포탑 리스트 재정의
min_attack = attacker_dict[(i, j)]
elif board[i][j] == max_strongest:
if attacker_dict[(i, j)] < min_attack:
min_attack = attacker_dict[(i, j)]
max_list = [(i, j)]
elif attacker_dict[(i, j)] == min_attack:
max_list.append((i, j))
# 공격력이 제일 높은 포탑이 1개면 해당 좌표 반환
if len(max_list) == 1:
return max_list[0]
# 만약 공격력이 높고 공격 시점이 같은 포탑이 2개 이상인 경우
else:
# 행과 열의 합이 가장 작은 포탑 반환
max_list.sort(key=lambda x: (x[0] + x[1], x[1]))
return max_list[0]
def bfs_laser(sx, sy, ex, ey):
visit_check = [[0 for _ in range(m)] for _ in range(n)]
queue = deque([])
queue.append((sx, sy, []))
visit_check[sx][sy] = 1
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0] # 우하좌상 반영
while queue:
x, y, route = queue.popleft()
for i in range(4):
nx, ny = (x + dx[i]) % n, (y + dy[i]) % m
if 0 <= nx < n and 0 <= ny < m:
if not visit_check[nx][ny] and board[nx][ny]:
visit_check[nx][ny] = 1
if nx == ex and ny == ey:
return True, route
else:
queue.append((nx, ny, route + [(nx, ny)]))
return False, []
# k번의 반복
for t in range(1, k + 1):
is_relation = [[0 for _ in range(m)] for _ in range(n)]
# 1. 공격자 선정
attacker_x, attacker_y = get_attacker(board, attacker_dict)
# 1-1. 공격자 리스트 추가
attacker_dict[(attacker_x, attacker_y)] = t
# 1-2. 핸디캡 적용
board[attacker_x][attacker_y] += HANDICAP
attack_amount = board[attacker_x][attacker_y]
# 2. 공격자의 공격
# 2-1. 자신을 제외한 가장 강한 포탑 찾기
victim_x, victim_y = get_victim(board, attacker_dict)
is_relation[attacker_x][attacker_y] = 1
is_relation[victim_x][victim_y] = 1
# 3. 레이저 공격 or 포탄 공격
# 3-1. 레이저 공격 가능 여부 확인
can_laser_attack, route = bfs_laser(attacker_x, attacker_y, victim_x, victim_y)
# 3-2. 레이저 공격 가능
if can_laser_attack:
# 공격 경로에 있는 포탑 공격력 감소
if route:
for each in route:
board[each[0]][each[1]] -= (attack_amount // 2)
is_relation[each[0]][each[1]] = 1
# 공격 대상 포탑 공격력 감소
board[victim_x][victim_y] -= attack_amount
# 3-3. 레이저 공격 불가. 포탄 공격 수행
else:
board[victim_x][victim_y] -= attack_amount
dx, dy = [-1, -1, -1, 0, 0, 1, 1, 1], [-1, 0, 1, -1, 1, -1, 0, 1]
for i in range(8):
nx = (victim_x + dx[i]) % n
ny = (victim_y + dy[i]) % m
if board[nx][ny]:
if not (nx == attacker_x and ny == attacker_y):
if not (nx == victim_x and ny == victim_y):
board[nx][ny] -= (attack_amount // 2)
is_relation[nx][ny] = 1
# 4. 공격 후 공격력 0 이하의 포탑은 부서짐 처리 & 5. 포탑 정비 & 6. 부서지지 않은 포탑이 1개면 종료
not_broken = 0
for i in range(n):
for j in range(m):
if board[i][j] > 0:
not_broken += 1 # 6
else:
board[i][j] = 0 # 4
if not_broken == 1:
break
for i in range(n):
for j in range(m):
if board[i][j] > 0:
if not is_relation[i][j]:
board[i][j] += 1 # 5
# 7. 가장 강한 포탑의 공격력 출력
biggest = 0
for i in range(n):
for j in range(m):
if board[i][j] > biggest:
biggest = board[i][j]
print(biggest)
if __name__ == "__main__":
n, m, k = map(int, input().split())
board = []
for _ in range(n):
board.append(list(map(int, input().split())))
solution(n, m, k, board)- 구현 & bfs
- 정말 겨우겨우겨우겨우 풀었다. 너무 힘들고 진이 빠졌지만, 그 과정에서 정말 많이 배웠다. 실전이 아닌 미리 이런 경험을 해볼 수 있는 것에 감사하다.
- 문제를 풀면서 배운 점
- 허투로 주는 조건은 없다. 해당 조건이 왜 주어졌을지, 어떤 식으로 문제를 풀기 바라는 것 같은지 출제자의 의도를 깊게 고민해보자.
- 조건들이 로직 속에서 잘 구현되고 있는지 꼼꼼하게 고민되자. 예를 들어 1 ~ 4 순위를 통해 답을 골라가는 과정에서 if 문으로 갈래가 나뉜다면 갈래가 나뉜 후에도 차 순위의 조건들이 모든 곳에서 잘 검증되고 있는지 파악하자.
- 반례를 생각하는 과정에서는 무조건 print를 찍거나, 확인하기보다는 문제에서 주어진 조건들과 내 코드를 비교해서 문제가 있을 법한 상황을 생각하고 그 후 그에 맞는 반례를 고민해서 문제를 해결해보자
- 제출기록
728x90