Softeer - 사물인식 최소 면적 산출 프로그램

문제요약

2차원 좌표평면에 n개의 점이 있고, 각 점은 색이 있다. k개의 색이 주어질 때, 모든 종류의 색이 적어도 하나는 포함되는 직사각형의 최소 넓이를 구하라

풀이요약

1. 재귀 + 브루트포스를 이용해 풀 예정(범위가 1 <= n <= 100, 1 <= k <= 20으로 작은 편)
2. 모든 색 종류에 모든 좌표를 확인하여 최대, 최소 x,y값을 구하고 넓이를 구한다.

코드

# softeer 사물인식 최소 면적 산출 프로그램
# https://softeer.ai/practice/info.do?idx=1&eid=531&sw_prbl_sbms_sn=232752

from collections import defaultdict
import sys

sys.setrecursionlimit(10**9)

# key는 색 종류 재귀를 도는 동안, max_x, max_y, min_x, min_y값을 갱신한다.
def dfs(key, max_x, max_y, min_x, min_y, square):
    global answer, k, color
    # key가 k+1이라면 모든 색 종류를 순회한 것
    if key == k+1:
        answer = min(answer, square)
        return
    # 만약 해당 색의 좌표가 존재한다면
    if color[key]:
        for nx, ny in color[key]:
            nmax_x, nmin_x = max(nx,max_x), min(nx,min_x)
            nmax_y, nmin_y = max(ny,max_y), min(ny,min_y)
            next_square = (nmax_x-nmin_x) * (nmax_y-nmin_y)
            # 정답보다 다음 직사각형 넓이가 작다면 dfs를 추가로 돈다.
            if next_square < answer:
                dfs(key+1, nmax_x, nmax_y, nmin_x, nmin_y, next_square)
    # 해당 색 좌표가 없으면 넘김
    else:
        dfs(key+1,max_x, max_y, min_x, min_y, square)


n,k = map(int,input().split())
# 딕셔너리로 색을 받아줄 예정
color = defaultdict(list)
answer = int(1e9)

for _ in range(n):
    x,y,c = map(int,input().split())
    color[c].append((x,y))

# 최초 색 잡아주기
idx = 1
while idx <= k:
    if color[idx]:
        break
    idx += 1
# 첫 idx부터 돌아주자
for x,y in color[idx]:
    dfs(idx,x,y,x,y,0)

print(answer)

후기

사실 그렇게 어렵진 않은 문제였는데 풀이할 때 뭐가 문제였냐면...

문제 이해를 늦게 해버렸다...!

1. 예제를 보고 점 2개만을 경계로 가지는 직사각형만 구함
2. 예제는 모두 통과했으나, subtask에서 많이 틀림
3. 이론상 모든 점이 경계가 될 수 있고, 경계가 되는 좌표는 최대 4개임!
4. 즉 (0,0), (2,2), (1,3),(3,1) 이라면 점 2개만 가지고 경계를 구할 수 없다....
5. 순진하게 예제는 점 2개만 경계를 가지는 걸 보여줘서 그대로 믿어버림....
6. 그래서 실패한 코드

from collections import defaultdict


def check(cidx,nidx,ccx,ccy,nnx,nny):
    max_x = max(ccx,nnx)
    max_y = max(ccy,nny)
    min_x = min(ccx,nnx)
    min_y = min(ccy,nny)
    flag = [0]*(k+1)

    for i in range(1,k+1):
        if i == cidx or i == nidx:
            flag[i] = 1
            continue
        for r,c in color[i]:
            print(i,r,c,min_x,max_x,min_y,max_y)
            if min_x <= r <= max_x and min_y <= c <= max_y:
                print(r,c)
                flag[i] = 1
                break
    for i in range(1,k+1):
        if not flag[i]:
            return False
    return True


n, k = map(int,input().split())
color = defaultdict(list)

for _ in range(n):
    x,y,c = map(int,input().split())
    color[c].append((x,y))

answer = int(1e9)

for i_idx in range(1,k+1):
    for cx,cy in color[i_idx]:
        for j_idx in range(i_idx+1,k+1):
            for nx,ny in color[j_idx]:
                if check(i_idx,j_idx,cx,cy,nx,ny):
                    answer = min(answer, (max(cx,nx)-min(cx,nx))*(max(cy,ny)-min(cy,ny)))

print(answer)

그래서 문제를 제대로 읽고 이해하는 노력해야 하지 않을까