[BOJ] 7573 고기잡이 (Python3)

문제

한국인의 식단에서 생선은 매우 중요한 단백질 공급원이다. 반면, 지구 온난화로 인한 바닷물의 온도 상승, 그리고 지금까지 마구잡이로 물고기를 잡은 결과로 점점 우리나라의 바다에서 물고기의 수가 줄어들고 있다. 정부에서는 이 문제를 심각하게 생각하여, 물고기를 잡을 수 있는 곳과 여기서 고기잡이 배가 사용할 수 있는 그물의 폭에 제한을 두었다. 물고기는 바다 표면 근처에 살기 때문에, 그물의 높이는 중요하지 않다. 따라서 그물은 길이가 l인 직선으로 생각할 수 있고, 물고기를 잡을 때, 그물은 한 변의 길이가 1 이상 정수인 직사각형 모양으로 치게 된다. 예를 들어, l = 10이라면, 칠 수 있는 그물의 모양은 1×4, 2×3, 3×2, 4×1과 같이 4가지 형태의 직사각형이 된다.

고기를 잡을 수 있는 곳은 N×N 크기의 모눈종이 모양으로 되어 있다. 각 모눈에는 좌표가 주어지며, 가장 왼쪽 위 모눈이 (1,1)이고, 가장 오른쪽 아래 모눈이 (N,N)이다. 총 M 마리의 물고기가 서로 다른 모눈 위에 한 마리씩 살고 있으며, 물고기는 움직이지 않는다. 고기잡이 배는 한 모눈 위에 위치를 잡고 자신의 오른쪽과 아래쪽으로 그물을 친다. 일단 그물을 치면, 그물 안, 그리고 그물에 걸친 물고기들을 잡을 수 있다. 예를 들면, 다음 그림은 N = 7, l = 10 이고 M = 6 마리의 물고기가 (2,2), (2,4), (3,3), (5,6), (6,2), (7,4)에 살고 있을 때, (2,2)에 놓인 고기잡이 배가 2×3 모양으로 그물을 친 예를 보이고 있다. 이때 고기잡이 배는 총 3마리의 물고기를 잡을 수 있다. 고기를 잡을 수 있는 영역 밖으로 그물을 치는 경우는 없다.

고기를 잡을 수 있는 영역, 물고기의 위치, 그물의 폭이 주어졌을 때 한 번의 그물치기로 잡을 수 있는 가장 많은 물고기의 마릿수를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 모눈종이의 크기, 그물의 길이, 물고기의 수를 나타내는 세 개의 정수 N, l, M이 하나의 공백을 두고 주어진다. 단, 2 ≤ N ≤ 10,000, 4 ≤ l ≤ 100, 1 ≤ M ≤100 이다. l은 l ≤ 4N - 4을 만족하는 짝수이다. 두 번째 줄부터 이후 M 개의 줄에는 각 물고기의 좌표가 하나의 공백을 두고 주어진다. 물고기의 좌표 순서는 무작위로 주어진다.

출력

첫 줄에 주어진 입력에서 잡을 수 있는 가장 많은 물고기의 마릿수를 하나의 정수로 출력한다.

정답 코드

import sys 
input = sys.stdin.readline

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

for i in range(m):
    x, y = map(int, input().split())
    fish.append((x, y))



def getNet(n):
    netSize = l // 2
    
    nets = []
    
    for i in range(1, netSize):
        netX = netSize - i
        netY = i
        
        nets.append((netX, netY))
    return nets
        
nets = getNet(n)

answer = 0

for net in nets:
    for fx, fy in fish:
        for mx in range(net[0] + 1):
            nx = fx - mx
            ny = fy
            
            if nx < 0 or nx >= n or ny < 0 or ny >=n:
                continue
            
            count = 0
            
            for rx, ry in fish:
                if nx <= rx <= nx + net[0] and ny <= ry <= ny + net[1]:
                    count += 1
                    
            
            answer = max(answer, count)
            
        for my in range(net[1] + 1):
            nx = fx
            ny = fy - my
            
            if nx < 0 or nx >= n or ny < 0 or ny >=n:
                continue
            
            count = 0
            
            for rx, ry in fish:
                if nx <= rx <= nx + net[0] and ny <= ry <= ny + net[1]:
                    count += 1
                    
            
            answer = max(answer, count)
            
print(answer)

문제 풀이

처음에는 그래프로 실제 그물을 이차원 배열로 표현했는데, 이렇게 하면 메모리초과가 발생한다.

다시 생각해보면 이 문제는 실제로 공간을 표현할 필요 없이, 그물의 공간범위에 포함 되는 물고기가 몇개인지만 확인해주면 답을 찾을 수 있다.

중요한건 각 물고기 별로 그물을 펼치되, 물고기가 꼭짓점에 있는 경우 외에도 가장자리에 걸치는 부분까지 탐색해주어야 모든 테스트 케이스를 통과할 수 있다.