[소프티어] HSAT 2회 정기 코딩 인증평가 기출 : 사물인식 최소 면적 산출 프로그램 (파이썬)

백트래킹 문제

https://softeer.ai/class/devcrew/study/resource/detail/description/6277?id=310&resourceId=366

Softeer - 현대자동차그룹 SW인재확보플랫폼

---

문제 

현대자동차그룹에 입사한 당신은 레이더 기술을 활용해 차량 주변의 장애물과 사물을 인식하는 프로그램을 만드는 업무를 담당하고 있다.

 

 

당신은 다양한 입력 값들로 인식된 사물에 대해 최소 면적을 계산해보는 테스트를 하는 중이다. 이번 테스트의 조건은 다음과 같다.

 

레이더를 통해 인식된 정보의 입력값은 평면에 N개의 점으로 주어진다. 각각의 점들은 총 K개의 색깔 중 하나를 가지고 있다. 각 점의 색깔은 {1, 2, …, K} 중의 한 정수로 표현된다.

 

당신은 입력값으로 주어진 K개의 색깔 {1, 2, …, K}에 대해 해당 색깔을 가지는 점들을 적어도 하나씩 포함하는 사물 중 넓이가 가장 작은 것을 찾아서 그 넓이를 출력하는 프로그램을 작성하려고 한다. 이때, 각 점을 포함한 사물은 반드시 직사각형으로 인식된다.

 

여기서 사물로 인식되는 직사각형은 네 변이 모두 수평 혹은 수직인 것에 한정하며, 직사각형의 내부가 아닌 경계에 놓은 점들도 그 직사각형에 포함된다고 생각한다. 직사각형의 가로 또는 세로의 길이가 0이 되어 선분 혹은 점으로 나타나는 경우도 직사각형의 한 경우로 생각하며 이런 경우 직사각형의(사물) 넓이는 0이다. (하나의 좌표에 여러 개의 점이 있을 수 있다.)

 

주어지는 입력값에 대해 K개의 색을 가진 점들을 적어도 하나씩 포함하는 사물(직사각형) 중 넓이가 가장 작은 것의 넓이를 출력하는 프로그램을 만들어보자.

제약조건

1 ≤ N ≤ 100

1 ≤ K ≤ 20

-1,000 ≤ x, y ≤ 1,000

1 ≤ k ≤ K

입력형식

입력으로는 점의 개수인 자연수 N과 각 점들이 가질 수 있는 색깔의 총 개수인 자연수 K가 첫 줄에 주어진다.

이후, N줄에는 입력으로 주어지는 점의 좌표 (x, y)와 그 점의 색깔 k가 세 개의 정수 x, y, k로 각 줄에 주어진다.

출력형식

주어진 입력에 대해 K개의 색깔 {1, 2, …, K} 각각에 대해 해당 색깔을 가지는 점들을 적어도 하나씩 포함하는 사물(직사각형) 중 넓이가 가장 작은 것을 찾아서 그 넓이를 정수 형태로 출력한다.

입력예제1

5 2 -4 -2 1 -5 -3 1 5 -4 2 4 -5 2 3 -8 2

출력예제1

10

입력예제2

5 3 3 7 1 5 8 1 6 5 2 7 1 3 9 3 3

출력예제2

14

입력예제3

7 3 -4 0 1 -5 -1 1 0 43 2 3 23 3 8 -19 2 10 0 3 20 0 2

출력예제3

0

입력예제4

3 3 1 1 1 1 1 2 1 1 3

출력예제4

0

---

💡 풀이코드 (실패 - Cartesian Product)

 

각각의 k 색깔의 리스트에서 반드시 하나의 원소씩 선택해야 하므로 데카르트의 곱 방식으로 생각하였다.

즉, arr 배열에서 각 색깔(k)에 해당하는 인덱스에 있는 리스트들에서 반드시 값을 하나씩 선택하여 조합해야 하는 것이다.

 

이를 위해 다음과 같이 2가지 방식으로 모든 경우의 수(product)를 생성해주었다.

 

import sys 
from itertools import product 

n, k = map(int, sys.stdin.readline().split())
arr = [[] for _ in range(k + 1)]
begin = [0 for _ in range(k + 1)]

xArr = [0 for _ in range(k+1)]
yArr = [0 for _ in range(k+1)]


for _ in range(n):
    x, y, color = map(int, sys.stdin.readline().split())
    arr[color].append((x, y))

result = list(product(*arr[1:]))  # 언패킹(*) 사용
print(result)

result = []
tmp = [[] for _ in range(k + 1)]
# tmp = []

def dfs(level):
    if level == k + 1:
        result.append(tmp[1:])  
        return

    for i in arr[level]:
        tmp[level] = i
        # tmp.append(i)
        dfs(level + 1) 
        # tmp.pop()  


dfs(1)

print(result)

 

1) itertools - product 사용

result = list(product(*arr[1:]))  # 언패킹(*) 사용

2) 백트래킹 

조합이므로 visited 배열은 필요 없다. 

▪︎ append, pop 

result = []
tmp = []

def dfs(level):
    if level == k + 1:
        result.append(tmp[:])  
        return

    for i in arr[level]:
        tmp.append(i)
        dfs(level + 1) 
        tmp.pop()

▪︎ result 배열에 바로 쓰기

result = []
tmp = [[] for _ in range(k + 1)]

def dfs(level):
    if level == k + 1:
        result.append(tmp[1:])  # 맨 앞의 []도 포함되므로 제거
        return

    for i in arr[level]:
        tmp[level] = i
        dfs(level + 1)

 

*위의 코드에서 visited가 필요 없는 이유

 

조합 구현에서 중복 선택을 방지하는 방법은 탐색 범위를 제한하는 "인덱스 기반 탐색"이다.

• 한 번 선택한 요소의 인덱스 이후부터만 다음 요소를 선택하도록 한다.
• 이미 선택된 요소 이전으로는 다시 탐색하지 않기 때문에 중복 선택이 일어나지 않는다.

예제: [1, 2, 3]에서 두 개를 고르는 과정

1. current_combination = [] (시작)
2. 선택: 1 → 다음 인덱스 탐색 범위: [2, 3]
   2.1 선택: 2 → 결과 저장: [1, 2]
   2.2 선택 취소: 2 → 다음 탐색: 3
   2.3 선택: 3 → 결과 저장: [1, 3]
3. 선택 취소: 1 → 다음 탐색 범위: [2, 3]
   3.1 선택: 2 → 다음 인덱스 탐색 범위: [3]
       3.1.1 선택: 3 → 결과 저장: [2, 3]​

문제점

불필요하게 모든 점의 조합을 계산하고, 값을 가지고 있다는 점이다.

우리는 최소 직사각형의 넓이만 계산하면 된다.

이말은 즉, 넓이를 계산하기 위해 x, y축으로 가장 큰 값과 가장 작은 값만 기록하고 이를 활용해 계산에 임하면 되는 것이다.

---

💡 풀이코드 (성공)

import sys 

n, k = map(int, sys.stdin.readline().split())
arr = [[] for _ in range(k + 1)]
result = sys.maxsize


for _ in range(n):
    x, y, color = map(int, sys.stdin.readline().split())
    arr[color].append((x, y))

def dfs(level, x_min, x_max, y_min, y_max):
    global result 
    if level == k + 1:
        result = min(result, ((y_max - y_min) * (x_max - x_min)))
        return
    
    for i in arr[level]:
        n_x_min = min(x_min, i[0])
        n_x_max = max(x_max, i[0])
        n_y_min = min(y_min, i[1])
        n_y_max = max(y_max, i[1])

        if (n_y_max - n_y_min) * (n_x_max - n_x_min) < result:
            dfs(level + 1, n_x_min, n_x_max, n_y_min, n_y_max)


dfs(1, 1000, -1000, 1000, -1000)

print(result)

 

1) 백트래킹 - 이부분 제거할 시 시간초과

만약 현재 넓이가 지금까지의 직사각형 최소 넓이(result)보다 작을 경우에만 dfs를 더 돌릴 가치가 있다고 판단하고, 재귀함수를 호출한다.

if (n_y_max - n_y_min) * (n_x_max - n_x_min) < result:
	dfs(level + 1, n_x_min, n_x_max, n_y_min, n_y_max)

 

2) DFS 메인 로직

level을 하나씩 늘려가며 즉, 색깔을 의미하는 k값을 하나씩 높혀가며 직사각형의 넓이를 결정할 가장 바깥 가장자리의 점들을 찾는다.

(그리고 이 가장자리의 점들만 변수에 기록해준다.)

어차피 우리는 직사각형 넓이만 구하면 되므로 각각의 k값 리스트에서 값을 하나씩 뽑아 만든 모든 점들의 조합을 기록하지 않는다.  

---

* 참고문헌

 

https://appdung-ioss.tistory.com/222

Softeer Level3: [HSAT 2회 정기 코딩 인증평가 기출] 사물인식 최소 면적 산출 프로그램 (Back Tracking / wi