[코테] 코드트리 - 포탑 부수기

김재연·2023년 10월 13일
0
post-thumbnail

해냈다... 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]
profile
일기장같은 공부기록📝

0개의 댓글