[코드트리/삼성SW역량테스트] 루돌프의 반란 (Python)

Problem : https://www.codetree.ai/training-field/frequent-problems/problems/rudolph-rebellion

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

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 01:37:46

 

---

 

문제 설명 / 입력 및 출력

 

 

자세한 설명은 코드트리 사이트 링크를 참조해 주세요!

 

 

---

 

풀이

 

조금 클래스 구조로 풀어보는 것까진 좋았는데, 맞왜틀이 너무 많이 뜬다. 아마 구현하면서 애초에 머릿속으로 생각했던 프로그램이 흐름과 많이 달라져서 생긴 문제가 아니었나 싶다.

 

문제에서 요구하는 대로 충실히 구현하면 되는 문제. 다른 기교 없이 산타와 루돌프를 조건에 맞게 구현하면 된다. 

• 산타 입장에서 루돌프와 부딪혔을 때 / 루돌프 턴에 산타와 부딪혔을 때 산타의 이동 방향 업데이트에 주의하자.
• 산타 입장에서의 이동 우선순위 및 루돌프 입장에서의 입력 우선순위를 조심하도록 하자.

 

풀이 코드

import sys
input = sys.stdin.readline

dr = [-1, -1, 0, 1, 1, 1, 0, -1]
dc = [0, 1, 1, 1, 0, -1, -1, -1]
MAX = float('inf')

rudolph = None
santas = list()
N, M, P, C, D = map(int, input().split())
maps = [[-1]*N for _ in range(N)]

def distance(r, c, t) :
    return (r - t.r) ** 2 + (c - t.c) ** 2

class Santa :
    def __init__(self, r, c, i) :
        self.r = r
        self.c = c
        self.i = i
        self.score = 0
        self.stuned = 0
        self.out = False
        maps[r][c] = i

    def where(self) :
        return (self.r, self.c)
    
    def move(self) :
        if self.out :
            return
        if self.stuned :
            self.stuned -= 1
            return
        orig = distance(self.r, self.c, rudolph)

        best, br, bc, bd = orig, self.r, self.c, -1
        for i in range(0, 8, 2) :
            ar, ac = self.r + dr[i], self.c + dc[i]
            dist = distance(ar, ac, rudolph)
            if -1 < ar < N and -1 < ac < N and best > dist and maps[ar][ac] in [0, -1] :
                best, br, bc, bd = dist, ar, ac, i
        if best == orig :
            return

        maps[self.r][self.c] = -1
        self.r, self.c = br, bc
        if rudolph.where() == self.where() :
            self.stuned = 1
            self.score += D
            self.r -= dr[bd] * D
            self.c -= dc[bd] * D
            if not (-1 < self.r < N and -1 < self.c < N) :
                self.out = True
                return
            if maps[self.r][self.c] > 0 :
                other = santas[maps[self.r][self.c]-1]
                other.move_forced((bd+4) % 8)
        maps[self.r][self.c] = self.i
            
    def move_forced(self, bd) :
        maps[self.r][self.c] = -1
        self.r += dr[bd]
        self.c += dc[bd]
        if not (-1 < self.r < N and -1 < self.c < N) :
            self.out = True
            return
        if maps[self.r][self.c] > 0 :
            other = santas[maps[self.r][self.c]-1]
            other.move_forced(bd)
        maps[self.r][self.c] = self.i
    
class Rudolph :
    def __init__(self, r, c) :
        self.r = r
        self.c = c
        maps[r][c] = 0

    def where(self) :
        return (self.r, self.c)
    
    def move(self) :
        best, best_santa = MAX, None
        for santa in santas :
            if santa.out :
                continue
            dist = distance(self.r, self.c, santa)
            if best > dist or best == dist and best_santa.where() < santa.where() :
                best, best_santa = dist, santa
        bm, br, bc, bd = best, self.r, self.c, -1
        for i in range(8) :
            ar, ac = self.r + dr[i], self.c + dc[i]
            dist = distance(ar, ac, best_santa)
            if -1 < ar < N and -1 < ac < N and bm > dist :
                bm, br, bc, bd = dist, ar, ac, i
        
        maps[self.r][self.c] = -1
        self.r = br
        self.c = bc

        if self.where() == best_santa.where() :
            best_santa.score += C
            best_santa.stuned = 2
            best_santa.r += dr[bd]*C
            best_santa.c += dc[bd]*C
            if not (-1 < best_santa.r < N and -1 < best_santa.c < N) :
                best_santa.out = True
            else :
                if maps[best_santa.r][best_santa.c] > 0 :
                    other = santas[maps[best_santa.r][best_santa.c]-1]
                    other.move_forced(bd)
                maps[best_santa.r][best_santa.c] = best_santa.i

        maps[self.r][self.c] = 0


rr, rc = map(int, input().split())
rudolph = Rudolph(rr-1, rc-1)
santa_list = sorted([list(map(int, input().split())) for _ in range(P)])
for i, r, c in santa_list :
    santas.append(Santa(r-1, c-1, i))
for _ in range(M):
    rudolph.move()
    for santa in santas :
        santa.move()
    left = P
    for santa in santas :
        if santa.out :
            left -= 1
            continue
        santa.score += 1
    if not left :
        break

for santa in santas :
    print(santa.score, end = ' ')

풀이 완료!