[백준 7573] 고기잡이

문제 출처 : https://www.acmicpc.net/problem/7573

고기잡이(7573)

이 문제는 2013년 정보 올림피아드 지역본선 중등부 2번 문제 입니다.

문제 이해하기

그물을 이용하여 한 번에 잡을 수 있는 최대 물고기 마리수를 출력하는 문제 입니다. 문제를 읽어보면 모눈 종이의 크기가 10,000 입니다. 그리고 그물의 크기가 100으로 그물의 모양만 50여개 정도 있습니다. 이런 상황에서 모눈 종이를 기준으로 물고기를 찾는다면 시간초과에 빠질수 밖에 없습니다. 다행히 물고기의 수는 최대 100마리 이기 때문에 모눈종이를 기준으로 하지 않고 물고기를 기준으로 그물을 설치한다면 시간초과에 걸리지 않을 수 있습니다.

물고기를 기준으로 그물을 설치하고, 물고기의 마리수를 세는 아이디어는 있지만 그것을 어떻게 구현할 지 막막합니다. 물고기를 어떻게 배치하는 것이 효과적일지 생각해 보겠습니다. 물고기를 가장 많이 잡으려면 물고기를 최대한 그물의 끝에 배치해야 합니다.

물고기가 위와 같이 있을 때 그냥 그물 안에 넣는 방법을 생각하면 위와 같이 2마리 밖에 잡지 못하지만 물고기가 그물의 끝에 있으면 아래와 같이 3마리를 잡을 수 있습니다.

물고기를 그물의 끝에 배치해야 최대의 물고기를 잡을 수 있다는 것을 알게 되었습니다. 그럼 이제 물고기를 잡기 위해서 그물을 설치하는 방법을 생각해 보겠습니다. 그물 위에 물고기를 위치한다는 것을 알고 있어도 어떻게 배치 하느냐에 따라 결과가 천차만별 이기 때문 입니다.

빨간색 그물을 설치하는 경우는 3마리를 모두 잡을 수 있지만 회색, 노란색, 파란색등의 그물은 분명 물고기랑 인접해 있지만 3마리를 다 잡지 못하는 것을 알 수 있습니다. 물고기의 위치에 따라 모든 그물의 위치를 전부 다 해보는 방법도 있겠지만 그렇게 한다면 고려할 것이 너무 많습니다. 따라서 그물이 위치할 수 있는 범위만 고려하는 방법을 사용하겠습니다. 각각의 물고기의 y좌표, 혹은 x좌표를 기준으로 범위만 지정하는 것입니다.

위 그림은 주황색 물고기의 y축만 기준으로 탐색하는 것입니다. 주황색 물고기의 x축은 전혀 고려하지 않고 y축 기준으로만 범위를 잡았습니다.

다음으로 파란색 물고기 위치에서 x축 그물 만을 표시한 부분이 하늘색 부분 입니다. 초록색 물고기 기준으로 그물을 던진 부분은 진한 초록색 부분 입니다. 주황색 물고기 기준으로도 그물을 설치하는 것이 맞습니다. 그림이 너무 지저분해 보여서 주황색 물고기 기준은 하지 않은 것입니다. 이렇게 각 물고기의 x축, y축으로 기준을 잡아도 모든 경우를 하나하나 다 해보지 않고 그물을 설치할 수 있습니다.

코드 작성

그럼 코드를 작성해 보겠습니다.

입력 받기

mii = lambda : map(int, input().split())
N, I, M = mii()

fish = []
for _ in range(M):
    y, x = mii()
    fish.append((y, x))

모눈종이의 크기 N, 그물의 길이 I, 물고기의 수 M을 입력 받습니다. 다음으로 M개의 물고기 위치를 받습니다. 물고기의 위치를 입력받아 fish라는 리스트에 넣어주었습니다.

그물 설정

nets = []
half_I = I // 2
for x in range(1,half_I):
    y = half_I - x
    nets.append((y, x))

그물의 크기를 생각해보겠습니다. 우리가 알고 있는 사실은 그물의 둘레가 I라는 사실 하나 입니다. 즉 그물의 크기가 정해져 있지 않다는 뜻입니다. 따라서 그물의 크기를 하나하나 만들어주어야 합니다. 그물의 크기는 2개의 가로 길이와 2개의 세로 길이로 만들어져 있습니다. 즉 전체 그물의 크기를 반으로 나누면 각각 하나의 가로의 길이, 세로의 길이로 나타낼 수 있다는 뜻입니다. 그래서 그물의 크기를 반으로 자른 half_I에서 그물의 x축 길이를 빼서 나머지 y축 길이로 만들어 주었습니다.

물고기 기준으로 그물 설치

ans = 0
for y, _ in fish:
    for _, x in fish:
        for ny, nx in nets:
            ans = max(ans, solve(y, x, ny, nx))

print(ans)

모든 물고기의 y축, x축이 그물을 설치할 수 있는 기준점이 됩니다. 그리고 그물의 길이 ny, nx를 사용하여 물고기를 잡는 것입니다. solve 함수에는 4개의 인자가 들어갑니다. y는 기준이 되는 어떤 물고기의 y 좌표 입니다. x는 기준이 되는 다른 물고기의 x 좌표 입니다. y, x의 기준이 되는 물고기는 같을수도 있고, 다를수도 있습니다. 그저 각 축의 기준이 되는것 뿐입니다. 다음으로 ny는 그물의 y축 길이 입니다. nx는 그물의 x축 길이 입니다. 이렇게 만들어진 4개의 좌표안에 물고기가 얼마나 있는지 찾아냅니다. 그리고 최대 물고기 수인 ans보다 크게 된다면 그 값을 교체해 줍니다.

그물안의 물고기 세기

def solve(sy, sx, ey, ex):
    cnt = 0
    for fy, fx in fish:
        if sy <= fy <= sy + ey and sx <= fx <= sx + ex:
            cnt += 1
    return cnt

그물안에 물고기가 얼마나 있는지 세어주는 함수 입니다. 그물의 크기 안에 해당 물고기가 존재한다면 cnt값을 1씩 늘려주고 최종적으로 얻은 cnt값을 리턴해 줍니다.

전체 코드

mii = lambda : map(int, input().split())
N, I, M = mii()

fish = []
for _ in range(M):
    y, x = mii()
    fish.append((y, x))

def solve(sy, sx, ey, ex):
    cnt = 0
    for fy, fx in fish:
        if sy <= fy <= sy + ey and sx <= fx <= sx + ex:
            cnt += 1
    return cnt

nets = []
half_I = I // 2
for x in range(1,half_I):
    y = half_I - x
    nets.append((y, x))

ans = 0
for y, _ in fish:
    for _, x in fish:
        for ny, nx in nets:
            ans = max(ans, solve(y, x, ny, nx))

print(ans)