[BOJ/백준] 7573 고기잡이 파이썬

문제 링크 : https://www.acmicpc.net/problem/7573

7573번: 고기잡이

 

문제는 간단하지만 겨우겨우 18번만에 푼 문제이다.

풀다풀다 모르겠어서 다른분들의 알고리즘을 참고하고 해결하였다.

 

N이 10000이므로 배열에 다 넣고 돌리면 당연히 시간초과가 난다.

그러니 물고기에만 주목하면 된다.

 

모든 물고기에 대해서 그 물고기가 그물 테두리에 겹치도록 그물을 펼친 후 그 범위안에 들어오는 물고기를 세주면 된다.

현재 물고기의 좌표를 끝점, 현재 그물의 크기만큼 뺀값을 시작점으로 하는 사각형을 그렸을 때 테두리에서 그물을 펼치면 해당 물고기가 항상 테두리에 걸치도록 그물이 펼쳐진다.

현재 물고기가 3,3에 있고 그물의 크기가 3x3 이라면 시작점은 0,0 끝점은 3,3인 사각형의 테두리에서 그물을 펼치면 된다. 그리고 해당 그물을 펼쳤을 때 그 그물안에 들어오는 물고기의 개수를 세주면 된다.

그물을 펼칠때 주의할 점은 그물이 주어진 범위안에 들어오는지 체크해줘야한다. 만약 벗어났다면 해당 점은 지나가도록 구현했다.

 

from sys import stdin

input = stdin.readline
dx = [0,1,0,-1]
dy = [1,0,-1,0]

n,l,m = map(int, input().split())

fish = []
answer = 0
for _ in range(m):
    x,y = map(int, input().split())
    fish.append((x-1,y-1))
def solv():
    for sx,sy in fish:
        for l1 in range(1,l//2):
            l2 = l//2-l1
            move_net(sx-l1, sy-l2, l1, l2)
    print(answer)

def move_net(sx,sy,l1,l2):
    global answer
    d = 0
    l1_cnt, l2_cnt = l1, l2
    while d != 4:
        if d in [1, 3]:
            sx += dx[d]
            l1_cnt -= 1
            if l1_cnt == 0:
                l1_cnt = l1
                d += 1
        else:
            sy += dy[d]
            l2_cnt -= 1
            if l2_cnt == 0:
                l2_cnt = l2
                d += 1
        if sx >= 0 and sy >= 0:
            ex = sx + l1 + 1
            ey = sy + l2 + 1
            answer = max(answer, count_fish(sx, sy, ex, ey))

def count_fish(sx,sy,ex,ey):
    cnt = 0
    if ex > n or ey > n:
        return 0
    for x,y in fish:
        if sx <= x < ex and sy <= y < ey:
            cnt += 1
    return cnt

solv()