[파이썬] 백준 17143 : 낚시왕 (골드1)

[파이썬] 백준 17143 : 낚시왕 (골드1)

17143번: 낚시왕 (acmicpc.net)

17143번: 낚시왕

---

문제

---

풀이

0. 방향성 생각

• 딕셔너리 입력 받기 -> 낚시하기 -> 상어 이동하기 + 잡아먹기 -> 새로운 딕셔너리 만들기
• 저 사이클을 한 stage로 만들어서 진행한다.

1. fishing 함수

def fishing(info:dict, x:int) -> int:
    info[x].sort(reverse=True)
    if info[x]:
        shark = info[x].pop()
        return info,shark[-1]
    return info,0

• info라는 딕셔너리는 info[x좌표] = [(y1,s1,d1,size1), ...] 이런식으로 이루어져있다.
• 해당 x좌표에 상어가 존재할 때, 거꾸로 정렬해주고 y값이 가장 작은 상어를 낚는다

2. 상어 좌표 update, move_eat 함수 정의

• 입력 크기를 보면 알겠지만 arr를 직접 구현해서 for, while문으로 구하는 문제가 아니다.
• 규칙을 찾아서 상어의 위치를 바로 계산하는게 핵심.
• 규칙은 어떻게 찾냐? 입력으로 주어진 상어들의 속력에 따라 어디로 이동하는지 확인해본다.
• 본문 그림에 있는 상어 중 속도가 8인 상어의 이동을 관찰해보자

• 발퀄 죄송
• 일단 주기가 10이다. 10이라는 숫자는 2*(w-1)에서 나왔다. (다른 상어들도 관찰해보면 쉽게 알 수 있다)
• 왼쪽 구석에 속도가 3인 상어를 보면 위에 있던 패턴인 <--, --> ,<--과 다르게 -->, <-- 패턴만 존재한다.
• 왼쪽 또는 오른쪽 벽에서 시작하면 패턴을 단순화시키고 조건문을 줄일 수 있다.
• 다시 위에 상어로 돌아와서 왼쪽 방향을 보면서 시작하므로, 오른쪽 벽의 맨 끝에 붙여서 시작한다고 가정하자.
• 속도가 8인 상어가 더 이전에서 시작하려면 뒤로 이동한 거리만큼 속도를 더해주어야한다.
• (4,2)에 있던 상어가 (6,2)에서 출발을 하면서 속도는 8 -> 10로 변경 (실제 인덱스는 1씩 작음)
• y좌표일 때도 마찬가지로 같은 연산을 취해줘서 계산해준다.
• divmod를 이용해서 나머지를 구하고 최소한의 이동만 시켜준다.

def update(tinfo:dict,shark:tuple):
    x,y,s,d,size = shark
    if ((x,y) in tinfo and size > tinfo[(x,y)][-1]) or (x,y) not in tinfo:
        tinfo[(x,y)] = (s,d,size)
        
def move_eat(info:dict) -> dict:
    tinfo = {}
    for x in info.keys():
        for y,s,d,size in info[x]:
            if d==1:
                _,q = divmod(s+(h-1)-y,2*(h-1))
                if q < h-1: shark = (x,(h-1)-q,s,1,size)
                else: shark = (x,q-(h-1),s,2,size)               
            elif d==2:
                _,q = divmod(s+y,2*(h-1))
                if q < h-1: shark = (x,q,s,2,size)
                else: shark = (x,2*(h-1)-q,s,1,size)
            elif d==3:
                _,q = divmod(s+x,2*(w-1))
                if q < w-1: shark = (q,y,s,3,size)
                else: shark = (2*(w-1)-q,y,s,4,size)
            elif d==4:
                _,q = divmod(s+(w-1)-x,2*(w-1))
                if q < w-1: shark = ((w-1)-q,y,s,4,size)
                else: shark = (q-(w-1),y,s,3,size)
            update(tinfo,shark)
    return tinfo

• 위 수식을 구현하면 저런식으로 나온다.
• 나머지 q를 구하고, q의 범위에 따라서 벽에 박고 되돌아올지, 아니면 박지 않고 그대로 갈지 정해진다.
• 이 범위에 따라 이동한 상어가 바라보는 방향도 달라진다.
• 위 상어가 오른쪽으로 붙어서 속력 10으로 이동했다고 치면, 절반은 안박고 나머지 절반은 박아서 되돌아온다.
• 인덱스 규칙은 위에서 구한 주기 2(w-1) 또는 2(h-1)을 이용해서 구한다.

3. summary

def summary(tinfo:dict) -> dict:
    ninfo = dd(list)
    for x,y in tinfo.keys():
        s,d,size = tinfo[(x,y)]
        ninfo[x].append((y,s,d,size))
    return ninfo

• info는 x좌표를 키로 받고, temp_info는 중복제거를 위해서 (x,y)를 키로 받았다.
• 이를 다시 x를 키로 받는 new_info를 만들어주어야 한다.

3. 출력

h,w,m = map(int,input().split())
info = dd(list)
for _ in range(m):
    y,x,s,d,size = map(int,input().split())
    info[x-1].append((y-1,s,d,size))

answer = 0
for i in range(w):
    info,kg = fishing(info,i)
    answer += kg
    tinfo = move_eat(info)
    info = summary(tinfo)
print(answer)

• 입력은 x-1,y-1로 바꿔서 인덱스 바꿔주기
• 낚시하면서 낚은 상어들을 kg로 받고 계속 더해준다.
• 이후 출력해주기.

---

전체코드

from collections import defaultdict as dd
import sys
input = lambda : sys.stdin.readline().rstrip()

def fishing(info:dict, x:int) -> int:
    info[x].sort(reverse=True)
    if info[x]:
        shark = info[x].pop()
        return info,shark[-1]
    return info,0

def update(tinfo:dict,shark:tuple):
    x,y,s,d,size = shark
    if ((x,y) in tinfo and size > tinfo[(x,y)][-1]) or (x,y) not in tinfo:
        tinfo[(x,y)] = (s,d,size)
        
def move_eat(info:dict) -> dict:
    tinfo = {}
    for x in info.keys():
        for y,s,d,size in info[x]:
            if d==1:
                _,q = divmod(s+(h-1)-y,2*(h-1))
                if q < h-1: shark = (x,(h-1)-q,s,1,size)
                else: shark = (x,q-(h-1),s,2,size)               
            elif d==2:
                _,q = divmod(s+y,2*(h-1))
                if q < h-1: shark = (x,q,s,2,size)
                else: shark = (x,2*(h-1)-q,s,1,size)
            elif d==3:
                _,q = divmod(s+x,2*(w-1))
                if q < w-1: shark = (q,y,s,3,size)
                else: shark = (2*(w-1)-q,y,s,4,size)
            elif d==4:
                _,q = divmod(s+(w-1)-x,2*(w-1))
                if q < w-1: shark = ((w-1)-q,y,s,4,size)
                else: shark = (q-(w-1),y,s,3,size)
            update(tinfo,shark)
    return tinfo

def summary(tinfo:dict) -> dict:
    ninfo = dd(list)
    for x,y in tinfo.keys():
        s,d,size = tinfo[(x,y)]
        ninfo[x].append((y,s,d,size))
    return ninfo

h,w,m = map(int,input().split())
info = dd(list)
for _ in range(m):
    y,x,s,d,size = map(int,input().split())
    info[x-1].append((y-1,s,d,size))

answer = 0
for i in range(w):
    info,kg = fishing(info,i)
    answer += kg
    tinfo = move_eat(info)
    info = summary(tinfo)
print(answer)

 

코멘트

쉬운듯? 실력이 늘어서그런가