[백준] 17143 - 낚시왕 (G2)

https://www.acmicpc.net/problem/17143

17143번: 낚시왕

이 문제는 겉보기에는 단순한 구현 / 시뮬레이션 문제이다.

상어 이동을 구현하고, 낚시만 하면 되는데, 이 상어 이동이 생각보다 까다롭다.

 

이동하다가 만나면 잡아먹는다는 점에서 구현하면서 윷놀이 문제 생각이 났다.

상어가 만나면 서로 잡아먹는다는 부분, 가장자리에 닿으면 방향이 반대로 바뀌는 부분을 구현하는게 힘들었다.

 

내가 이 문제를 풀면서 실수한 부분은 2가지였다.

 

1. 한번에 모아놓고 제일 크기가 큰 상어를 남기고 삭제하나 만날 때마다 작은 상어를 삭제하나

차이가 없을 것이라고 생각해, 만날 때마다 작은 상어를 삭제한 점.

 

삭제된 상어가 나중에 이동할 상어였을 수도 있기 때문에, 모든 이동을 마치고 한번에 삭제했어야 했다.

 

상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다.

이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.

 

문제에서는 이렇게 표현을 했는데, 나는 이 표현을 보고,

순간적으로 두 마리가 될 때마다 삭제하게 구현한 것이다.

 

2. 이동을 마치고 한번에 삭제할 때, 리스트를 순회하는 도중에 아이템을 삭제한 것

 

딕셔너리나 셋 자료구조의 경우, 순회하면서 아이템을 삭제할 수 없다.

파이썬에서 런타임오류를 발생시키기 때문이다.

하지만 리스트에서는 그런 오류가 없었다.

그렇기에 당연히 내가 의도한대로 삭제가 될 것이라고 생각했는데 아니었다.

 

인덱스로 접근한 것도 아니고

for shark in list_shark:
	if shark == biggest_shark:
 		continue
    list_shark.remove(shark)

이런 식으로 코드를 작성해서 상어를 삭제했다.

그런데 이렇게 삭제해도, 리스트 인덱스가 꼬이는지 상어를 하나씩 건너뛰면서 순회하는 문제가 발생했다.

그래서 상어가 완전히 다 삭제되지 않아 문제가 생겼다.

 

이를 통해, 자료구조 내부를 순회하는 도중에 자료를 추가하거나 삭제하는 작업은 하지 말아야겠다는 것을

다시 한번 기억했다.

 

---

나는 나머지 연산으로 상어 방향전환을 구현했다.

이건 (현재 위치 + 스피드) 값을 쭉 적어놓고 규칙을 찾으면 규칙이 보인다.

 

class Shark:
    global R, C

    def __init__(self, k, row, col, speed, direction, size):
        self.key = k
        self.row = row
        self.col = col
        self.speed = speed
        self.direction = direction
        self.size = size

        self.is_dead = False

    def __gt__(self, other): # self > other
        return self.size > other.size

    def __lt__(self, other):
        return self.size < other.size

    def __str__(self):
        return str(self.key)

    def move(self):
        R_MOD, C_MOD = (R-1)*2, (C-1)*2
        if self.direction in (3, 4): # 좌우로 이동
            if self.direction == 3:
                next_c = self.col + self.speed
            else:
                next_c = self.col - self.speed
            next_c %= C_MOD
            if next_c > C-1:
                if self.direction == 3:
                    self.direction = 4
                else:
                    self.direction = 3
                term = C_MOD - next_c
                self.col = term
            else:
                self.col = next_c
        else:
            if self.direction == 1:
                next_r = self.row - self.speed
            else:
                next_r = self.row + self.speed
            next_r %= R_MOD
            if next_r > R-1:
                if self.direction == 1:
                    self.direction = 2
                else:
                    self.direction = 1
                term = (R-1)*2 - next_r
                self.row = term
            else:
                self.row = next_r
                

R, C, M = map(int, input().split())
board = [[list() for _ in range(C)] for _ in range(R)]
shark_dict = dict()
for i in range(M):
    r, c, s, d, z = map(int, input().split())
    shark_dict[i] = Shark(i, r-1, c-1, s, d, z)
    board[r-1][c-1].append(shark_dict[i])

answer = 0
for time in range(C):
    # 상어 잡기
    for depth in range(R):
        shark_list = board[depth][time]

        assert len(shark_list) <= 1

        if shark_list and not shark_list[0].is_dead:
            answer += shark_list[0].size
            shark_list[0].is_dead = True
            board[depth][time].remove(shark_list[0])
            break

    # 상어 이동
    for key in shark_dict.keys():
        shark = shark_dict[key]

        if shark.is_dead:
            continue

        board[shark.row][shark.col].remove(shark) # 이전 위치를 비우기
        shark.move()
        board[shark.row][shark.col].append(shark)

    # 가장 큰 상어만 남기고 잡기
    for i in range(R):
        for j in range(C):
            if len(board[i][j]) > 1:
                biggest = max(board[i][j])
                for shark in board[i][j]:
                    if shark.size == biggest.size:
                        continue
                    shark.is_dead = True
                board[i][j] = [biggest]

print(answer)