[코드트리: Python] - 싸움땅

[문제]

https://www.codetree.ai/training-field/frequent-problems/problems/battle-ground/description?page=3&pageSize=5

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

문제를 따라 읽으며 그대로 구현하면 되는 문제입니다.

 

크게 어려운 테크닉은 없으며, 반대 방향 및 회전에 대해서만 주의하시면 되겠습니다.

---

[초기화]

    def __init__(self):
        self.n, self.m, self.k = map(int, input().split())
        self.grid = [[-1] * (self.n + 2)] + \
                    [[-1] + list(map(int, input().split())) + [-1] for _ in range(self.n)] + \
                    [[-1] * (self.n + 2)]
        self.players = [[0] * 4] + [list(map(int, input().split())) for _ in range(self.m)]
        self.points = [0] * (self.m + 1)
        self.gun = [0] * (self.m + 1)
        self.gun_grid = [[[] for _ in range(self.n + 2)] for _ in range(self.n + 2)]
        self.directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]

좌표가 1부터 시작한다는 점에 여백을 추가하였습니다.

 

또한 문제 조건에 맞춰 추가적인 변수를 선언하였습니다.

 

변수들의 경우, 좌표와 플레이어 번호가 1부터 시작하므로 격자에 여백을 추가하였습니다. 해당 부분은 편의에 맞게 조정하시면 되겠습니다.

• points: 각 플레이어의 점수
• gun: 각 플레이어의 총기 소지 유무
• gun_grid: 총의 정보를 표현할 격자
• directions: 문제에서 제시한 방향

    def init_grid(self):
        for y in range(1, self.n + 1):
            for x in range(1, self.n + 1):
                if self.grid[y][x] > 0:
                    self.gun_grid[y][x] = [self.grid[y][x]]

주어진 격자에 맞춰 gun_grid에 총에 대한 정보를 리스트형태로 추가합니다.

 

이를 따로 관리하는 이유는, "놓여있는 총들", "나머지 총들은"이라는 묘사를 통해 바닥에 총이 여러 대가 있음을 알 수 있기 때문입니다.

 

처음에 간과했던 부분은 총에 대한 유지였습니다.

 

grid를 통해 항상 공격력이 가장 높은 총으로 초기화하였는데, 생각해 보니 두 명의 플레이어가 모두 같은 공간으로 이동할 일이 있으며 총을 주워야 하는 상황일 때, 앞선 방법으로 초기화를 진행하는 경우 향후 방문하는 사람이 총을 주울 수 없는 문제가 발생하였습니다.

 

이를 해결하고 각 위치에 리스트를 가지는 총 관리용 격자를 도입하게 되었습니다.

---

[풀이]

우선 지문을 읽고, 구현해야 할 기능들을 지문 순서에 맞게 정의합니다.

1. 플레이어 이동
2. 총 줍기
3. 싸우기
4. 싸움에서 진 사람 처리
5. 싸움에서 이긴 사람 처리

    def move(self):
        for player in range(1, self.m + 1):
            y, x, d, s = self.players[player]
            dy, dx = self.directions[d]
            my, mx = y + dy, x + dx
            if not (1 <= my <= self.n and 1 <= mx <= self.n):  # 벽에 부딪히면
                my, mx = y - dy, x - dx
                d = (d + 2) % 4
            self.players[player] = [my, mx, d, s]

            for enemy in range(1, self.m + 1):
                if player == enemy:  # 나는 범위에서 제외
                    continue
                if [my, mx] == self.players[enemy][:2]:  # 적이 있다면
                    self.fight(player, enemy, my, mx)
                    break
            else:  # 적이 없다면
                self.get_gun(player, my, mx)

플레이어 이동에 대한 코드입니다.

 

각 플레이어 별로 정보를 가져와, 방향에 맞춰 이동을 시뮬레이션합니다.

 

이때, 격자를 벗어나게 될 경우, 위치와 방향을 반대로 조정합니다.

 

이후 이동한 장소에 적이 있는지 반복문을 통해 확인합니다.

 

만약 시뮬레이션된 좌표와 동일한 좌표를 가지는 플레이어가 있는 경우 싸움을 시작합니다.

 

하지만 break 없이 반복이 끝났다면 적을 만나지 못했다는 의미이므로 총을 줍는 행동으로 넘어가게 됩니다.

    def get_gun(self, player, my, mx):
        self.gun_grid[my][mx].sort()  # 가장 강한 총을 줍기 위해
        if self.gun_grid[my][mx]:  # 총이 바닥에 있고
            if self.gun[player] == 0:  # 내가 총이 없다면
                self.gun[player] = self.gun_grid[my][mx].pop()
            else:
                if self.gun[player] < self.gun_grid[my][mx][-1]:
                    put_gun = self.gun[player]
                    self.gun[player] = self.gun_grid[my][mx].pop()
                    self.gun_grid[my][mx].append(put_gun)

총을 주울 때는 총을 줍는 플레이어와 주울 위치를 함께 넘겨받습니다.

 

이후 해당 위치에 가장 강력한 총을 줍기 위한 준비로 정렬을 수행합니다.

 

그리고 문제에 제시된 대로 순차적으로 코드를 그대로 작성하시면 되겠습니다.

    def fight(self, player, enemy, y, x):
        player_atk = self.players[player][3] + self.gun[player]
        enemy_atk = self.players[enemy][3] + self.gun[enemy]
        if player_atk > enemy_atk:  # 주인공 승리
            self.points[player] += abs(player_atk - enemy_atk)
            self.after_fight(player, enemy, y, x)
        elif player_atk == enemy_atk:
            if self.players[player][3] > self.players[enemy][3]:  # 주인공 승리
                self.after_fight(player, enemy, y, x)
            elif self.players[player][3] < self.players[enemy][3]:  # 상대방 승리
                self.after_fight(enemy, player, y, x)
        else:  # 상대방 승리
            self.points[enemy] += abs(player_atk - enemy_atk)
            self.after_fight(enemy, player, y, x)

싸움에 대한 처리입니다.

 

이 또한 제시된 조건대로 순차적으로 처리하면 됩니다.

 

제가 해당 로직을 작성하면서 헷갈렸던 부분은 공격력이 같을 때였습니다. 왜냐하면 이긴 사람은 분명히 나타나지만, 점수는 0점을 얻기 때문입니다. 

 

그러므로 공격력이 같은 경우 굳이 포인트를 갱신하지 않아도 됩니다.

 

싸움에 대한 처리가 끝나면, 승자와 패자에 대한 후속처리를 진행합니다.

    def after_fight(self, winner, loser, y, x):
        if self.gun[loser] != 0:
            self.gun_grid[y][x].append(self.gun[loser])
            self.gun[loser] = 0  # 패자는 총 버림
        self.move_lose(loser)  # 패자 이동

        if self.gun_grid[y][x] and self.gun[winner] < self.gun_grid[y][x][-1]:  # 바닥에 총이 내거보다 좋으면 교환
            put_gun = self.gun[winner]
            self.gun[winner] = self.gun_grid[y][x].pop()
            self.gun_grid[y][x].append(put_gun)

승자와 패자, 싸움이 일어나 장소의 좌표를 넘겨받습니다.

 

패자는 자신이 가진 총을 내려두고, 이동을 수행합니다.

 

또한 총이 없는 상태는 굳이 리스트에 저장할 필요가 없으므로, 총을 가지고 있을 때만 내려두게 조건을 처리합니다.

 

이후 승자에 대한 처리를 수행합니다.

 

승자에 대한 처리의 경우 "원래 들고 있던 총 중 가장 공격력이 높은 총을 획득하고"라는 문장 때문에 처음에 실패하였습니다. 하지만 총이 없는 경우도 가장 공격력이 높은 총을 줍게 만들어야 합니다.

    def move_lose(self, loser):
        y, x, d, s = self.players[loser]

        for _ in range(4):
            dy, dx = self.directions[d]
            my, mx = y + dy, x + dx
            if not (1 <= my <= self.n and 1 <= mx <= self.n) or [i for i in self.players if i[:2] == [my, mx]]:
                d = (d + 1) % 4
            else:
                self.players[loser] = [my, mx, d, s]
                if self.gun_grid[my][mx]:
                    put_gun = self.gun[loser]
                    self.gun_grid[my][mx].sort()
                    self.gun[loser] = self.gun_grid[my][mx].pop()
                    if put_gun:
                        self.gun_grid[my][mx].append(put_gun)
                break

패자에 대한 이동처리입니다.

 

처음엔 자신의 방향에 맞춰 이동을 시뮬레이션합니다. 이때 조건에 따라 달리 처리합니다.

 

격자를 벗어나거나 적이 있는 경우 순서에 맞게 방향을 회전하게 되는데, 이 역시 처음에 고민이 많았습니다.

 

네 번 다 돌아도 정착할 수 없으면 어떻게 되나 많은 고민을 했으나, 관련에 대한 지시도 없고 결정적으로 통과가 된 것을 보아 해당 케이스는 없는 거 같습니다.

 

바닥에 총이 있는 경우, 공격력이 가장 강한 총을 줍고, 버릴 총이 있으면 바닥에 둡니다.

 

코드의 경우 순서상 총을 먼저 줍게 되면 버릴 수 없으므로, 처리를 먼저 진행합니다.

 

 또한 총을 줍는 시점에서 해당 행동은 끝나는 것이므로 break를 통해 종료합니다.

---

[전체 코드]

class Main:
    def __init__(self):
        self.n, self.m, self.k = map(int, input().split())
        self.grid = [[-1] * (self.n + 2)] + \
                    [[-1] + list(map(int, input().split())) + [-1] for _ in range(self.n)] + \
                    [[-1] * (self.n + 2)]
        self.players = [[0] * 4] + [list(map(int, input().split())) for _ in range(self.m)]
        self.points = [0] * (self.m + 1)
        self.gun = [0] * (self.m + 1)
        self.gun_grid = [[[] for _ in range(self.n + 2)] for _ in range(self.n + 2)]
        self.directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]

    def init_grid(self):
        for y in range(1, self.n + 1):
            for x in range(1, self.n + 1):
                if self.grid[y][x] > 0:
                    self.gun_grid[y][x] = [self.grid[y][x]]

    def move_lose(self, loser):
        y, x, d, s = self.players[loser]

        for _ in range(4):
            dy, dx = self.directions[d]
            my, mx = y + dy, x + dx
            if not (1 <= my <= self.n and 1 <= mx <= self.n) or [i for i in self.players if i[:2] == [my, mx]]:
                d = (d + 1) % 4
            else:
                self.players[loser] = [my, mx, d, s]
                if self.gun_grid[my][mx]:
                    put_gun = self.gun[loser]
                    self.gun_grid[my][mx].sort()
                    self.gun[loser] = self.gun_grid[my][mx].pop()
                    if put_gun:
                        self.gun_grid[my][mx].append(put_gun)
                break

    def after_fight(self, winner, loser, y, x):
        if self.gun[loser] != 0:
            self.gun_grid[y][x].append(self.gun[loser])
            self.gun[loser] = 0  # 패자는 총 버림
        self.move_lose(loser)  # 패자 이동

        if self.gun_grid[y][x] and self.gun[winner] < self.gun_grid[y][x][-1]:  # 바닥에 총이 내거보다 좋으면 교환
            put_gun = self.gun[winner]
            self.gun[winner] = self.gun_grid[y][x].pop()
            self.gun_grid[y][x].append(put_gun)

    def fight(self, player, enemy, y, x):
        player_atk = self.players[player][3] + self.gun[player]
        enemy_atk = self.players[enemy][3] + self.gun[enemy]
        if player_atk > enemy_atk:  # 주인공 승리
            self.points[player] += abs(player_atk - enemy_atk)
            self.after_fight(player, enemy, y, x)
        elif player_atk == enemy_atk:
            if self.players[player][3] > self.players[enemy][3]:  # 주인공 승리
                self.after_fight(player, enemy, y, x)
            elif self.players[player][3] < self.players[enemy][3]:  # 상대방 승리
                self.after_fight(enemy, player, y, x)
        else:  # 상대방 승리
            self.points[enemy] += abs(player_atk - enemy_atk)
            self.after_fight(enemy, player, y, x)

    def get_gun(self, player, my, mx):
        self.gun_grid[my][mx].sort()  # 가장 강한 총을 줍기 위해
        if self.gun_grid[my][mx]:  # 총이 바닥에 있고
            if self.gun[player] == 0:  # 내가 총이 없다면
                self.gun[player] = self.gun_grid[my][mx].pop()
            else:
                if self.gun[player] < self.gun_grid[my][mx][-1]:
                    put_gun = self.gun[player]
                    self.gun[player] = self.gun_grid[my][mx].pop()
                    self.gun_grid[my][mx].append(put_gun)

    def move(self):
        for player in range(1, self.m + 1):
            y, x, d, s = self.players[player]
            dy, dx = self.directions[d]
            my, mx = y + dy, x + dx
            if not (1 <= my <= self.n and 1 <= mx <= self.n):  # 벽에 부딪히면
                my, mx = y - dy, x - dx
                d = (d + 2) % 4
            self.players[player] = [my, mx, d, s]

            for enemy in range(1, self.m + 1):
                if player == enemy:  # 나는 범위에서 제외
                    continue
                if [my, mx] == self.players[enemy][:2]:  # 적이 있다면
                    self.fight(player, enemy, my, mx)
                    break
            else:  # 적이 없다면
                self.get_gun(player, my, mx)

    def solve(self):
        self.init_grid()
        for stage in range(1, self.k + 1):
            self.move()
            
        print(*self.points[1:])


problem = Main()
problem.solve()

---

문제가 꽤 애매모호한 포인트가 많았습니다. 하지만 삼성의 기출을 풀며 느낀 바, 기본적으로 문제에서 제시된 것만 수행하고 본인의 생각은 최대한 배제하는 것이, 삼성의 코테 문제를 구현을 하는 데 있어서는 가장 좋은 거 같습니다.