17143번 - 낚시왕

문제

 

17143번: 낚시왕 (acmicpc.net)

17143번: 낚시왕

풀이 1

첫 번째

문제를 모두 읽고, 큰 틀을 먼저 잡는다. 구조적인 틀은 조건을 그대로 구현하면 된다.

1. 낚시왕이 오른쪽으로 한 칸 이동한다.
2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
3. 상어가 이동한다.

낚시꾼이 땅에서 가장 가까운 상어를 잡는것을 구현하는 가장 직관적인 접근은, 평소처럼 board를 만들어 열->행 순으로 탐색하면 될 것이다. 결국 문제는 상어의 움직임을 어떻게 구현할 것인가? 로 좁혀진다.

for col in range(1,c+1):
    for row in range(1,r+1):
        # 가장 땅에 가까이 있는 상어 포획
    # 상어 움직임

두 번째

상어는 좌표, 속도, 방향, 크기로 주어지는데, 조건에서 크기는 중복되지 않는다고 명시했으므로 크기가 곧 상어의 고유식별자가 될 수 있으며, "상어가 서로를 잡아먹을 때"는 다른 조건 없이 오직 크기가 가장 큰 상어만 남기면 된다는 것을 알 수 있다. 상어의 움직임을 구현할 때 속도와 크기는 변하지 않고 오직 좌표와 방향만 바뀌므로, 이 둘을 편하게 디버깅 할 수 있게 board에는 오직 상어의 크기만 놓고, 따로 딕셔너리를 만들어 상어의 크기를 key 값으로 하고 그 외 정보들을 value로 넣는다. 이렇게 하면 디버깅 시 board를 출력하여 상어의 좌표가 올바르게 연산되는지 확인할 수 있고, 딕셔너리를 출력하여 상어가 바라보는 향하는 방향을 쉽게 확인 가능하다.

데이터를 어떻게 받아올지 설계가 끝났다면, 본격적으로 상어의 움직임을 구현해볼 차례이다. 역량테스트에 종이와 펜을 왜 주는지 알 수 있는 부분인데, 구현 문제는 되도록이면 머리로만 풀려고 하지 말고 손으로 직접  써보며 확실히 설계를 끝낸 뒤에 코딩에 들어가는게 좋겠다. 상어의 움직임은 꽤나 복잡한데, 결정적으로 진행방향으로 가다가 벽을 만나면 바로 반대방향으로 움직이기 때문이다. 이를 직접 그려보며 생각해보기 전 까지는 원형 리스트를 돌고 있다는 것을 눈치채기 어려운데, 예시에서 상어 C 의 움직임을 예를 들어 설명해보도록 하겠다. 처음 상어 C의 위치는 다음과 같을 것이다.

1	2	3	4	5	6
			C

C의 속도는 8 이므로, 1초 뒤 다음과 같이 움직일 것이다. C의 진행방향은 역방향이기 때문에, 아래와 같은 리스트를 계속해서 돌게 되는 것이다. 이 문제에서 가장 중요한 발상으로, 직접 노트에 상황을 구현해보며 얻은 결과이므로 추후 구현문제에서는 이와 같은 시도를 적극적으로 해볼 필요가 있겠다.

6	5	4	3	2	1	2	3	4	5
C

위와 같은 발상에 따라 행,열 모두 정방향, 역방향 원형 리스트를 만들어준다.

row_circle_f = list(range(1,r)) + list(range(r,1,-1))
row_circle_b = list(range(r,1,-1)) + list(range(1,r))
col_circle_f = list(range(1,c)) + list(range(c,1,-1))
col_circle_b = list(range(c,1,-1)) + list(range(1,c))

세 번째

상어의 1초뒤 위치를 올바르게 얻어냈다면, 1초뒤 바라볼 방향에 대한 고려를 해줘야한다. 이는 간단하게 구현 가능한데, 설명보다는 아래 코드를 보는게 더 빠를것 같다.

idx = ((_row-1)+speed) % (2*r - 2)
direct = 1 if idx > r-1 else direct
_row = row_circle_f[idx]

네 번째

마지막으로 갱신한 딕셔너리 정보들을 board에 옮길 차례이다. 여기서 크기가 제일 큰 상어만 남는다는 조건을 구현해주면 되는데, 직관적으로 max와 min을 이용해 패배한 상어는 딕셔너리에서 지워주면 되겠다.

winner,looser = max(new_board[_row][_col],size),min(new_board[_row][_col],size)
new_board[_row][_col] = winner
del sharks[looser]

코드

r,c,m = map(int,input().split())
board = [[0]*(c+1) for _ in range(r+1)]
sharks = dict()
for _ in range(m):
    _r,_c,s,d,z = map(int,input().split())
    board[_r][_c] = z
    sharks[z] = [_r,_c,s,d]


row_circle_f = list(range(1,r)) + list(range(r,1,-1))
row_circle_b = list(range(r,1,-1)) + list(range(1,r))
col_circle_f = list(range(1,c)) + list(range(c,1,-1))
col_circle_b = list(range(c,1,-1)) + list(range(1,c))


def get_next_coor(_row,_col,speed,direct):
    # 정방향
    if direct == 2 or direct == 3:
        if direct == 2: # 하
            idx = ((_row-1)+speed) % (2*r - 2)
            direct = 1 if idx > r-1 else direct
            _row = row_circle_f[idx]
        else:           # 우
            idx = ((_col-1)+speed) % (2*c - 2)
            direct = 4 if idx > c-1 else direct
            _col = col_circle_f[idx]
    # 역방향
    else:
        if direct == 1: # 상
            idx = ((r-_row) + speed) % (2*r - 2)
            direct = 2 if idx > r-1 else direct
            _row = row_circle_b[idx]
        else:           # 좌
            idx = ((c-_col) + speed) % (2*c - 2)
            direct = 3 if idx > c-1 else direct
            _col = col_circle_b[idx]
    return (_row,_col,direct)


def get_updated():
    new_board = [[0] * (c + 1) for _ in range(r + 1)]
    keys = list(sharks.keys())
    # 상어들이 1초 뒤 가 있을 위치, 바라보는 방향 갱신
    for size in keys:
        _row, _col, speed, direct = sharks[size]
        _row, _col, direct = get_next_coor(_row,_col,speed,direct)
        sharks[size][0],sharks[size][1] = _row,_col
        sharks[size][3] = direct
    # 1초 뒤 정보들을 바탕으로 실제 board 갱신
    for size in keys:
        _row, _col = sharks[size][0], sharks[size][1]
        # 만약 해당 좌표가 비어있으면
        if new_board[_row][_col] == 0:
            new_board[_row][_col] = size
        # 만약 해당 좌표에 이미 상어가 있다면
        else:
            # 더 크기가 큰 상어가 차지
            winner,looser = max(new_board[_row][_col],size),min(new_board[_row][_col],size)
            new_board[_row][_col] = winner
            del sharks[looser]
    return new_board


answer = 0
for col in range(1,c+1):
    for row in range(1,r+1):
        # 가장 땅에 가까이 있는 상어 포획
        if board[row][col] > 0:
            answer += board[row][col]
            sharks.pop(board[row][col],None)
            board[row][col] = 0
            break
    # 상어 움직임
    board = get_updated()

print(answer)

풀이 2

위 풀이는 상어의 진행경로를 구현하지 않고, 행과 열을 원형리스트로 해석해서 상어가 도달할 위치와 그때의 방향을 직접 계산한다.

이번 풀이는 상어의 진행경로를 직접 구현해서 풀이했다. 보드를 갱신할 때 new_board를 직접 복사하는것이 아닌 참조하도록 했는데, 문제없이(?) 잘 작동한다. 아마 순회가 끝나도 객체가 사라지지 않고 그대로 남아있는 모양이다...

# 북 남 동 서
dRow = [0,-1,1,0,0]
dCol = [0,0,0,1,-1]

R,C,M = map(int,input().split())
# 속력, 이동방향, 크기
board = [[[] for col in range(C + 1)] for row in range(R + 1)]
for _ in range(M):
    r,c,s,d,z = map(int,input().split())
    board[r][c] = [s,d,z]

answer = 0
cnt = 0
for fisher in range(1,C+1):
    # 더이상 잡을 상어가 없으면 종료
    if cnt >= M:
        break
    # 상어 잡기
    for row in range(1,R+1):
        if board[row][fisher]:
            answer += board[row][fisher][2]
            cnt += 1
            board[row][fisher].clear()
            break
    # 상어 이동
    new_board = [[[] for col in range(C + 1)] for row in range(R + 1)]
    for row in range(1,R+1):
        for col in range(1,C+1):
            if board[row][col]:
                x,y = row,col
                spd,dir,siz = board[row][col]
                for _ in range(spd):
                    nx, ny = x + dRow[dir], y + dCol[dir]
                    if not (1 <= nx <= R and 1 <= ny <= C):
                        if dir == 1:dir = 2
                        elif dir == 2: dir = 1
                        elif dir == 3: dir = 4
                        elif dir == 4: dir = 3
                        nx, ny = x + dRow[dir], y + dCol[dir]
                    x,y = nx,ny
                if not new_board[x][y] or new_board[x][y][2] < siz:
                    new_board[x][y] = [spd,dir,siz]
    board = new_board

print(answer)