[구현] 백준 17143 : 낚시왕 - 파이썬

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

17143번: 낚시왕

 

 

생각하기

상어의 정보 저장?

• 리스트에 각 상어의 r, c, s, d, z(위치, 크기, 방향, 속도)를 저장
• shark[r][c] 는 (r,c)에 있는 상어 -> 상어의 위치가 변하고 위치가 중요하기 때문에 현재 문제에는 이러한 접근이 구현하기 편함

상어의 같은 위치에 여러마리

• 모든 상어를 이동 시키고 모든 칸을 살펴 보면서 2마리 이상이면 한마리로 -> 배열이 여러차원으로 형성될수 있다
• 이동하면서 항상 한마리만 남게 하기 -> 배열을 하나만 놔도 되므로 간단하므로 이 방법 채택

전체적인 플로우

1. 낚시왕이 이동
2. 상어를 잡는다
3. 상어가 이동

상어의 다음 이동 위치 구하기

시작 위치(position)에서 속도(s)를 가지고 방향(d)로 움직였을 때의 위치

처음에는 R, C 만큼 나눠주고 나머지를 구하는 그런 생각들을 했었는데

결론적으로 말하자면 상어의 방향도 계속 바뀌기 때문에 저렇게 수식으로 구하는 경우 한계가 있다

그냥 한칸씩 이동시키면서 조건 맞춰주는 것이 최적의 솔루션

 

구현하기

class 선언

상어에 대한 정보 (speed, size, direction)을 가지고 있는 class 선언

class를 가지고 shark 위치를 알려주는 배열을 만들 예정

 

 

shark[r][c] = r.c에 있는 상어 모두 저장(1,2 마리가 아닐 수가 있음)

주의할 점은 동시에 이동을 하고 잡아먹어야 함

• cur_sharks[R][C] 이동 전의 상어 위치
• next_sharks[R][C] 이동 후의 상어 위치

배열을 두가지로 나누어서 cur_shark를 next_shark로 대치하는 방식을 사용한다

 

다음 상어의 이동 위치와 해당 이동 위치에서의 방향

• check_limit_x : 좌우로 움직였을 때 계산해주는 메소드
• check_limit_y : 위아래로 움직였을 때 계산해주는 메소드

 

# 낚시왕 오른쪽 1칸 이동
# 낚시왕의 열 중에서 땅과 가장 가까운 상어 잡기 -> 잡으면 상어 사라짐
# 상어 이동 (격자판 넘으면 -> 방향 반대로 바꿔서 속력 유지 이동 / 두마리 이상인 경우 가장 큰 상어가 차지)

# d=1 위 / d=2 아래 / d=3 오른쪽 / d=4 왼쪽

# 낚시왕이 잡고 다음에 상어 이동


from operator import ne


R, C, M = map(int, input().split())

class Shark:
    def __init__(self, size=0, speed=0, direction=0):
        self.size = size
        self.speed = speed
        self.direction = direction
    

def check_limit_x(position, d, s):
    # 좌우 (행) 으로 움직일 때, 다음 위치 추정 메소드
    while s:
        if d == 4:
            position -=1
            if position == 0:
                position += 2
                d = 3

        else:
            position += 1
            if position == C+1:
                position -= 2
                d = 4

        s-=1

    return (position, d)



def check_limit_y(position, d, s):
    # 위아래 (열)로 움직였을 때, 다음 위치 추정 메소드
    while s:
        if d == 1:
            position -=1
            if position == 0:
                position += 2
                d = 2
        else:
            position += 1
            if position == R+1:
                position -= 2
                d= 1
        
        s-=1

    return (position, d)

   

cur_sharks = [[Shark() for j in range(C+1)] for i in range(R+1)]



for i in range(M):
    # r- row, c- col, s - 속력, d - 이동방향, z - 크기
    r, c, s, d, z = map(int, input().split())
    cur_sharks[r][c] = Shark(z, s, d)


answer = 0
for p in range(1, C+1):
    
    # p 기준으로 상어 잡기 / 행이 가장 작은 값을 가지는 아이로
    for i in range(1, R+1):
        if cur_sharks[i][p].size != 0:
            answer += cur_sharks[i][p].size
            cur_sharks[i][p] = Shark()
            break


    # 각 water[r][c] = shark의 idx
    next_sharks = [[Shark() for tmp_c in range(C+1)] for tmp_r in range(R+1)]

    # 상어 이동하기
    for i in range(1, R+1):
        for j in range(1, C+1):
            if cur_sharks[i][j].size == 0:
                continue
        
            nr, nc = i, j
            # !!! 클래스 멤버 변수를 메소드의 매개변수로 넘기면 그냥 변수를 넘기는 것과 달리 차마조가 되므로 변수로 풀어주었다 !!!
            dir, speed = cur_sharks[i][j].direction, cur_sharks[i][j].speed

            # 위 / 아래 방향인 경우
            if dir == 1 or dir == 2:
                nr, nd = check_limit_y(i, dir, speed)
            # 오른쪽 / 왼쪽 방향인 경우
            else:
                nc, nd = check_limit_x(j, dir, speed)


            if next_sharks[nr][nc].size != 0:
                if cur_sharks[i][j].size > next_sharks[nr][nc].size:
                    next_sharks[nr][nc] =Shark(cur_sharks[i][j].size, cur_sharks[i][j].speed, nd)
            else:
                next_sharks[nr][nc] = Shark(cur_sharks[i][j].size, cur_sharks[i][j].speed, nd)
                

    for i in range(1, R+1):
        for j in range(1, C+1):
            cur_sharks[i][j] = Shark(next_sharks[i][j].size, next_sharks[i][j].speed, next_sharks[i][j].direction)

        

print(answer)

 

 

상어의 위치를 나타내는 배열을 하지 않고 

상어를 담는 리스트를 이용하여 푸는 방법도 있다

 

# 낚시왕 오른쪽 1칸 이동
# 낚시왕의 열 중에서 땅과 가장 가까운 상어 잡기 -> 잡으면 상어 사라짐
# 상어 이동 (격자판 넘으면 -> 방향 반대로 바꿔서 속력 유지 이동 / 두마리 이상인 경우 가장 큰 상어가 차지)

# d=1 위 / d=2 아래 / d=3 오른쪽 / d=4 왼쪽

# 낚시왕이 잡고 다음에 상어 이동


R, C, M = map(int, input().split())

class Shark:
    def __init__(self, row, col, size=0, speed=0, direction=0):
        self.row = row
        self.col = col
        self.size = size
        self.speed = speed
        self.direction = direction
    

def check_limit_x(position, d, s):
    # 좌우 (행) 으로 움직일 때, 다음 위치 추정 메소드
    while s:
        if d == 4:
            position -=1
            if position == 0:
                position += 2
                d = 3

        else:
            position += 1
            if position == C+1:
                position -= 2
                d = 4

        s-=1

    return (position, d)



def check_limit_y(position, d, s):
    # 위아래 (열)로 움직였을 때, 다음 위치 추정 메소드
    while s:
        if d == 1:
            position -=1
            if position == 0:
                position += 2
                d = 2
        else:
            position += 1
            if position == R+1:
                position -= 2
                d= 1
        
        s-=1

    return (position, d)

   



sharks = []

for i in range(M):
    # r- row, c- col, s - 속력, d - 이동방향, z - 크기
    r, c, s, d, z = map(int, input().split())
    sharks.append(Shark(r, c, z, s, d))

sharks_exist = [True] * M

answer = 0
for p in range(1, C+1):
    
    # p 기준으로 상어 잡기 / 행이 가장 작은 값을 가지는 아이로
    min_row = int(1e9)
    catch_idx = -1
    for s_idx in range(M):
        if sharks_exist[s_idx] == False:
            continue
        
        # p와 같은 col에 있는 상어인 경우
        if sharks[s_idx].col == p and min_row > sharks[s_idx].row:
            min_row = sharks[s_idx].row
            catch_idx = s_idx
            
    if catch_idx != -1:
        answer += sharks[catch_idx].size
        sharks_exist[catch_idx] = False


    # 각 water[r][c] = shark의 idx
    water_tmp = [[-1]*(C+1) for _ in range(R+1)]

    # 상어 이동하기
    rmv_shark_idx = []
    for s_idx in range(M):
        if sharks_exist[s_idx] == False:
            continue

        nr, nc = sharks[s_idx].row, sharks[s_idx].col
        # 위 / 아래 방향인 경우
        if sharks[s_idx].direction == 1 or sharks[s_idx].direction == 2:
            nr, nd = check_limit_y(sharks[s_idx].row, sharks[s_idx].direction, sharks[s_idx].speed)
        # 오른쪽 / 왼쪽 방향인 경우
        else:
            nc, nd = check_limit_x(sharks[s_idx].col, sharks[s_idx].direction, sharks[s_idx].speed)

        sharks[s_idx].row, sharks[s_idx].col, sharks[s_idx].direction = nr, nc, nd

        if water_tmp[nr][nc] != -1:
            cmp_shark_idx = water_tmp[nr][nc]
            if sharks[cmp_shark_idx].size > sharks[s_idx].size:
                rmv_shark_idx.append(s_idx)
            else:
                water_tmp[nr][nc] = s_idx
                rmv_shark_idx.append(cmp_shark_idx)
        else:
            water_tmp[nr][nc] = s_idx

    for rm_idx in rmv_shark_idx:
        sharks_exist[rm_idx] = False
        

print(answer)

 

시간은 적게 걸리지만 사실상 거의 차이가 안날 뿐더러

구현 방법이 후자의 방법이 더 어렵기 때문에 전자의 방법으로 푸는 것이 맞는 것 같다