해냈다... WOW
코드트리는 따로 깃허브 연동을 안해놔서 벨로그에 저장해두기
그리고 풀면서 느낀 삼성 코테 푸는 법 정리
1. 문제 꼼꼼히 읽으면서 어떻게 구현할지 확실하게 정리하기
절대 무작정 손대지 말고 하나하나 어떻게 구현하면 될지 꼭꼭꼭꼭꼭꼭꼭 생각부터 하자.
지난번에 대충 생각하고 풀려고 했다가 개망쳐서 이번에는 이렇게 쭉 정리하고 들어갔다.
함수를 어떤 단위로 쪼개서 구현할지, 무슨 자료구조를 쓸 건지 등등 구체적으로 다 생각해야 함
BFS로 최단거리만 계산해봤지 최단경로를 구해본적이 없어서 좀 당황탔다. => 이런거 꼭 생각하고 코딩 시작하기
2. 코드를 함수 단위로 크게 쪼개놓고 시작하기
이렇게 쪼개놓고 시작하면 훨씬 가독성도 좋고 기능별로 깔끔하게 구현할 수 있다.
def select_weakest():
return
def select_strongest():
return
def attack(start, end):
return
def maintain():
return
def check():
return False
# 입력은 생략
for k in range(K):
# 1. 가장 약한 포탑 고르기
s = select_weakest()
# 2. 가장 강한 포탑 고르기
e = select_strongest()
# 3. 공격하기
attack(s,e)
# 4. 정비하기
maintain()
# 5. 종료여부 확인하기
if check():
break하나하나 완성해가면서 모자랐던거 반영하기
3. 빡코딩
끝임ㅋ
이러고 그냥 주구장창 하나하나 꼼꼼하게 구현해나가면 됨. (그게 어려워서 문제지)
문제가 길어서 중간중간 놓치는 디테일 있을 수 있으니까 꼼꼼하게 확인하기
from collections import deque
def select_weakest(k):
temp = [[board[i][j][0], board[i][j][1], i+j, j, i] for i in range(N) for j in range(M) if board[i][j][0] != 0]
temp = sorted(temp, key=lambda x:(x[0],-x[1],-x[2],-x[3]))
board[temp[0][4]][temp[0][3]][0] += (N+M) # 핸디캡
board[temp[0][4]][temp[0][3]][1] = k # 턴수
return [temp[0][4], temp[0][3]] # 행, 열
def select_strongest(start):
temp = [[board[i][j][0], board[i][j][1], i + j, j, i] for i in range(N) for j in range(M) if board[i][j][0] != 0 and [i,j]!=start]
temp = sorted(temp, key=lambda x: (-x[0], x[1], x[2], x[3]))
return [temp[0][4], temp[0][3]] # 행, 열
def attack(start, end):
dr = [0, 1, 0, -1] # 우 하 좌 상
dc = [1, 0, -1, 0]
queue = deque()
queue.append(start)
visited = [[False for _ in range(M)] for _ in range(N)]
visited[start[0]][start[1]] = True
flag = False
path = [[[0,0] for _ in range(M)] for _ in range(N)] # 최단경로
path[start[0]][start[1]] = start
# 최단경로 찾기
while queue:
nr, nc = queue.popleft()
if nr == end[0] and nc == end[1]:
flag = True
break
for i in range(4):
nextr = nr + dr[i]
nextc = nc + dc[i]
# 범위 조정
if nextr < 0: # 위로 벗어남
nextr = N-1
if nextr >= N: # 아래로 벗어남
nextr = 0
if nextc < 0: # 왼쪽으로 벗어남
nextc = M-1
if nextc >= M: # 오른쪽으로 벗어남
nextc = 0
# 부서진 포탑은 지날 수 없음
if board[nextr][nextc][0] == 0:
continue
if visited[nextr][nextc] == False: # 아직 방문 X
queue.append([nextr, nextc])
visited[nextr][nextc] = True
path[nextr][nextc] = [nr, nc]
damage = board[start[0]][start[1]][0]
attacked = [start, end]
board[end[0]][end[1]][0] -= damage # 공격
if board[end[0]][end[1]][0] < 0:
board[end[0]][end[1]][0] = 0
if flag:
# 레이저 공격
tempr, tempc = path[end[0]][end[1]]
while (tempr, tempc) != (start[0], start[1]):
# print(tempr, tempc)
board[tempr][tempc][0] -= damage//2 # 절반 피해
if board[tempr][tempc][0] < 0:
board[tempr][tempc][0] = 0
attacked.append([tempr,tempc])
tempr, tempc = path[tempr][tempc]
else:
# 포탄 공격
dr = [-1,0,1]
dc = [-1,0,1]
for i in range(3):
for j in range(3):
nextr, nextc = end[0]+dr[i], end[1]+dc[j]
if nextr < 0: # 위로 벗어남
nextr = N - 1
if nextr >= N: # 아래로 벗어남
nextr = 0
if nextc < 0: # 왼쪽으로 벗어남
nextc = M - 1
if nextc >= M: # 오른쪽으로 벗어남
nextc = 0
if board[nextr][nextc][0] == 0 or [dr[i],dc[j]] == [0,0] or [nextr,nextc]==start: # 부서진 포탄은 X
continue
board[nextr][nextc][0] -= damage // 2 # 절반 피해
if board[nextr][nextc][0] < 0:
board[nextr][nextc][0] = 0
attacked.append([nextr,nextc])
return attacked
def maintain(attacked):
for i in range(N):
for j in range(M):
if board[i][j][0] > 0 and [i,j] not in attacked:
board[i][j][0] += 1
return
def check():
count = 0
for i in range(N):
for j in range(M):
if board[i][j][0] > 0:
count += 1
if count == 1:
return True
return False
N, M, K = map(int, input().split())
board = []
INF = 1e8
for _ in range(N):
row = list(map(int, input().split()))
b = []
for r in row:
b.append([r,0])
board.append(b)
for k in range(K):
# 1. 가장 약한 포탑 고르기
s = select_weakest(k+1) # k턴, 시작점 좌표 반환
# 2. 가장 강한 포탑 고르기
e = select_strongest(s) # 시작점 제외, 끝점 좌표 반환
# 3. 공격하기
attacked = attack(s,e) # 공격과 상관있는 포탑 반환
# 4. 정비하기
maintain(attacked) # 공격과 상관없는 포탑 공격력 + 1
# for b in board:
# print(b)
# 5. 종료여부 확인하기 (부서지지 않은 포탑 개수=1)
if check():
break
# 가장 강한 포탑 찾기
answer = -1
for i in range(N):
for j in range(M):
if board[i][j][0] > answer:
answer = board[i][j][0]
print(answer)아래는 풀면서 써놔야지 했던거
Tip1. 우선순위대로 고르기
- 똑같을 때를 대비한 여러 조건을 따져서 하나만 선택하는 경우
def select_one(start):
temp = [
[0번째 값에서 조건1에 쓰이는 값, 0번째 값에서 조건2에 쓰이는 값, ...],
[1번째 값에서 조건1에 쓰이는 값, 1번째 값에서 조건2에 쓰이는 값, ...],
[2번째 값에서 조건1에 쓰이는 값, 2번째 값에서 조건2에 쓰이는 값, ...],
...
]
temp = sorted(temp, key=lambda x: (조건1, 조건2, 조건3, ...)) # 우선순위대로 정렬
return temp[0] # 제일 앞에 있는 값if-else 분기문으로 하나하나 나누는 것보다 훨씬 깔끔하고 편한듯
- DFS/BFS같은데서 경로가 여러 개인데 우선순위 방향이 있는 경우
dr = [0, 1, 0, -1] # 우 하 좌 상 (우선순위 방향대로 조절)
dc = [1, 0, -1, 0]
while queue:
nr, nc = queue.popleft()
for i in range(4): # 차례대로 하나씩 봄
nextr = nr + dr[i]
nextc = nc + dc[i]
...그냥 어느 곳을 먼저 갈지 자식노드 방문 순서만 잘 조절해주면 됨
Tip2. BFS로 최단"경로" 구하기
25. 그래프(Graph) - 최단 경로 찾기 를 참고함
어렵지 않으니 외워두면 좋을 듯
# path[a][b] = [c,d]는 (c,d)->(a,b) 경로를 뜻함
path = [[[0,0] for _ in range(M)] for _ in range(N)] # 경로 상의 부모를 저장해두는 곳
path[start[0]][start[1]] = start # 시작점은 자기자신
while queue:
nr, nc = queue.popleft()
if nr == end[0] and nc == end[1]:
flag = True
break
for i in range(4):
nextr = nr + dr[i]
nextc = nc + dc[i]
# ... 생략 ...
if visited[nextr][nextc] == False:
queue.append([nextr, nextc])
visited[nextr][nextc] = True
path[nextr][nextc] = [nr, nc] # (nextr,nextc)에는 (nr,nc)로부터 왔다는 뜻
if flag: # 최단경로가 있을 때
tempr, tempc = end[0], end[1] # 끝점부터
while (tempr, tempc) != (start[0], start[1]): # 시작점까지 역추적
print(tempr, tempc) # 최단경로
tempr, tempc = path[tempr][tempc]
일기장같은 공부기록📝