이 문제는 "백트래킹 알고리즘"을 잘 알고 있어야 하고, 동시에 이 알고리즘을 어떻게 효율적으로 짤 것인가를 생각해야만 하는 문제였다.
즉, 백트래킹 알고리즘을 구현한 후, 중복될만한 계산을 하지 않도록 만드는 장치를 더하는 것이 관건이었다.
현대자동차 소프티어 문제에서 일반적으로 효율을 그렇게 따지지 않지만, HSAT 정기 코딩 인증평가의 경우는 효율을 꽤나 중요하게 따지는 것을 이번 문제를 통해 알 수가 있었다.
이제 문제에 대한 해설을 시작하도록 하겠다.
코드는 2가지 구조로 구성이 된다.
1. 백트래킹 알고리즘 구현.
2. 직사각형 탐색 코드 구현.
3. 불필요한 연산 제거를 위한 코드.
1. 백트래킹 알고리즘 구현
우선 이 문제를 풀기 위해서 가장 먼저 해야할 일은 백트래킹 코드를 구현해야만 한다.
def backtracking(필요한 변수들):
if (종결조건):
종결조건에 해야만 하는 코드 적기.
return # 그리고 코드를 끝내줘야 한다.
# 백트래킹 동안 진행하고 싶은 코드 작성
~~~~~
# 그리고 어떤 조건 하에 백트래킹 함수를 다시 호출. (재귀적 사용)
if (백트래킹을 진행할 조건):
backtracking(필요한 변수들)
백트래킹을 구현하는 구조는 위와 같다. backtracking 이라는 이름으로 함수를 하나 만들고, 변수로는 필요할만한 변수들을 모두 넣어준다. 그리고 함수의 초입부에 이 함수를 끝내는 종결조건을 넣어주고, 종결조건에 해당하는 코드를 작성해주어야만 한다. 그렇지 않으면 코드가 무한으로 돌아가기 때문이다.
그리고 나서 종결조건 부분 코드를 작성한 후 필요한 백트래킹 동안 해야하는 연산을 넣어주고, 그 다음 어떠한 조건을 기준으로 백트래킹을 돌리도록 코드를 짜준다.
# 백트래킹 진행할 클래스
class Solution():
def __init__(self):
# 최소 면적 초기값은 가능한 가장 큰 값으로 설정 (최소값 연산이기 때문.)
self.min_area = 2000*2000+1
# 인풋: 환경 (color_dots), 더할 색깔, 종결 조건, 왼쪽x, 오른쪽x, 아래y, 위y,
def backtracking(self, color_dots, color, terminal_condition, x_left, x_right, y_lower, y_upper):
# 만약 종결조건이라면 (이 경우 현재의 색의 인덱스가 주어진 색의 인덱스보다 더 클경우)
# 이 경우 이미 모든 색에 대해 백트래킹을 진행한 상태
if (color > terminal_condition):
# 직사각형 면적 구해주고
rect_area = (x_right-x_left)*(y_upper-y_lower)
# 최소 면적 갱신 후
self.min_area = min(self.min_area, rect_area)
# 함수를 마친다.
return
for dot_x, dot_y in color_dots[color]:
# 각 x,y의 위치를 하나하나 탐색하며 직사각형을 서서히 넓힌다.
# 이를 위해 직사각형 각각의 x,y 후보군을 얻어냄
x_left_cand = min(x_left, dot_x)
x_right_cand = max(x_right, dot_x)
y_lower_cand = min(y_lower, dot_y)
y_upper_cand = max(y_upper, dot_y)
# 면적을 구해봄.
tmp = (x_right_cand-x_left_cand)*(y_upper_cand-y_lower_cand)
# 지금까지의 직사각형이 최소 면적보다 작을 경우에만 다음 계산 진행.
# 만약 최소 면적보다 이미 크다면 불필요한 계산이므로 계산을 진행하지 않음.
if tmp < self.min_area:
self.backtracking(color_dots, color+1, terminal_condition, x_left_cand, x_right_cand, y_lower_cand, y_upper_cand)
이 문제를 위한 백트래킹 코드는 위와 같다. 말그대로 종결조건을 넣어준 후 그 종결조건에 필요한 코드를 backtracking 초입부에 적어주었고, 백트래킹 연산에 필요한 코드들을 모두 작성해주었다.
2. 직사각형 탐색 코드 구현
그 다음으로는 직사각형을 알아내는 코드를 설명하겠다. 이 문제에서 요구하는 내용은 각각의 "색"들을 모두 가진 점들이 이루는 직사각형의 최소 넓이를 구하는 것이다. 이를 위해 "직사각형"을 얻어내는 규칙을 알 필요가 있다.
직사각형은 왼쪽 끝의 위치 x_left, 오른쪽 끝의 위치 x_right, 아래쪽 끝의 위치 y_lower, 그리고 마지막으로 위쪽 끝의 위치 y_upper가 존재한다.
그리고 각각의 점은 각 색깔에 해당하는 점들을 하나하나 보면서, 누적 최소/최대값과 각각의 점들의 x,y 위치를 비교하면서, 최소 연산 및 최대 연산을 진행하면 직사각형의 모서리 x,y 위치를 모두 구할 수 있다.
for dot_x, dot_y in color_dots[color]:
# 각 x,y의 위치를 하나하나 탐색하며 직사각형을 서서히 넓힌다.
# 이를 위해 직사각형 각각의 x,y 후보군을 얻어냄
x_left_cand = min(x_left, dot_x)
x_right_cand = max(x_right, dot_x)
y_lower_cand = min(y_lower, dot_y)
y_upper_cand = max(y_upper, dot_y)
코드로 표현하면 위와 같다. 이 부분의 코드는 이해하고 나서 되도록이면 코드 자체를 외워두면 좋을 것 같다.
3. 불필요한 연산 제거를 위한 코드.
그렇게 모서리를 구했으면 마지막으로 *불필요한 연산을 제거하기 위한 코드*를 작성해주어야만 한다. 이는 현대 HSAT 또는 HDAT를 준비하고 있다면 연습을 꼭 많이 해봐야만 하는 부분이다.
이 문제의 경우 불필요한 연산을 없애기 위해선,
*** 각각의 색에 해당하는 점들을 하나하나 탐색하는 과정에서 직사각형의 넓이를 임의로 구해보고, 지금까지 얻어낸 최소 넓이랑 비교해서 만약 최소 넓이보다 이미 큰 상태라면 이 계산을 하지 않도록 해주는 코드를 작성***
해야만 한다.
for dot_x, dot_y in color_dots[color]:
# 각 x,y의 위치를 하나하나 탐색하며 직사각형을 서서히 넓힌다.
# 이를 위해 직사각형 각각의 x,y 후보군을 얻어냄
x_left_cand = min(x_left, dot_x)
x_right_cand = max(x_right, dot_x)
y_lower_cand = min(y_lower, dot_y)
y_upper_cand = max(y_upper, dot_y)
# 면적을 구해봄.
tmp = (x_right_cand-x_left_cand)*(y_upper_cand-y_lower_cand)
# 지금까지의 직사각형이 최소 면적보다 작을 경우에만 다음 계산 진행.
# 만약 최소 면적보다 이미 크다면 불필요한 계산이므로 계산을 진행하지 않음.
if tmp < self.min_area:
self.backtracking(color_dots, color+1, terminal_condition, x_left_cand, x_right_cand, y_lower_cand, y_upper_cand)
이 부분은 위와 같다. 각각의 백트래킹 연산 과정에 있어서 직사각형의 모양을 서서히 구해가는데, 거기서 넓이를 임시로 구해보고, 넓이가 이전에 구했던 최소 넓이보다 이미 크다면 아예 계산을 생략시키도록 해주는 것이다.
이렇게 하면 불필요한 연산을 대폭 줄일 수 있게 된다.
그리고 마지막으로 위의 3가지 코드를 잘 합친다면 이 문제를 해결할 수 있다.
***시행착오***
import sys
# 점의 갯수 (N) 그리고 색깔 총 개수 (K) 를 받는다.
N, K = map(int, sys.stdin.readline().split())
# k는 1부터 K 까지이므로 K+1개를 쓰고 0번째 값은 사용하지 않는다.
color_dot = [[] for _ in range(K+1)]
for _ in range(N):
x, y, k = map(int, sys.stdin.readline().split())
# 색마다 위치를 정리한다.
color_dot[k].append([x,y])
class Solution():
def __init__(self):
# store dots which have all colors
self.path_x = []
self.path_y = []
# # store each area for all concidence
# self.result = []
# store minimum area
self.min_area = 2000*2000 + 1
# terminate_len = K
def backtracking(self, color_dots, color, end_len):
if (len(self.path_x) == end_len):
# left side x
x_left = min(self.path_x)
# right side x
x_right = max(self.path_x)
# lower side y
y_lower = min(self.path_y)
# upper side y
y_upper = max(self.path_y)
# compute the area
rect_area = (x_right-x_left)*(y_upper - y_lower)
# self.result.append(rect_area)
self.min_area = min(self.min_area, rect_area)
return
# 가장 오른쪽에 넣는다.
for dot in color_dots[color]:
self.path_x.append(dot[0])
self.path_y.append(dot[1])
self.backtracking(color_dots, color+1, end_len)
# 가장 오른쪽 요소를 뺀다
self.path_x.pop()
self.path_y.pop()
sol = Solution()
sol.backtracking(color_dot, 1, K)
print(sol.min_area)
이 문제를 풀면서 시행착오를 겪었는데, 바로 "3번", 즉 불필요한 연산을 제거해주는 장치를 작성하지 않아서였다.
위처럼 종결조건이 나타나기 전까지는 각각의 점들의 x,y 위치를 저장해준 후, 종결조건에 다다랐을 때 모든 점들의 x의 최소/최대값을 통해 x_left, x_right을 구하고, y의 최소/최대값을 통해 y_lower, y_upper을 구해 직사각형의 넓이를 구해 이 최소값을 누적하는 방식으로 진행했었다.
하지만 이렇게 되면 어쨌든 중간 계산을 확인하지 않고 무작정 모두 계산하는 방식이라 요구된 계산 시간 5초를 쉽게 넘겨 오답을 받게 된다.
그래서 이 종결 조건에서 몰빵된 계산을 종결조건이 아닌 곳에 분배하고, 이 계산 과정에 있어서 중복된 계산이 일어날만한 요소를 없애주어야만 했다.
코드
import sys
# 점의 개수 (N) 와 점들이 가질 수 있는 색깔의 총 개수 (K) 를 받는다.
N, K = map(int, sys.stdin.readline().split())
# 각 색깔에 해당하는 점들을 받아들일 리스트를 준비한다.
color_dots = [[] for _ in range(K+1)] # 1부터 K까지 사용할 것이므로 range(K+1)
for _ in range(N):
# x, y, 그리고 색을 받는다.
x, y, k = map(int, sys.stdin.readline().split())
# 그리고 색점을 저장하는 리스트에 하나하나 담는다.
color_dots[k].append([x,y])
# 백트래킹 진행할 클래스
class Solution():
def __init__(self):
# 최소 면적 초기값은 가능한 가장 큰 값으로 설정 (최소값 연산이기 때문.)
self.min_area = 2000*2000+1
# 인풋: 환경 (color_dots), 더할 색깔, 종결 조건, 왼쪽x, 오른쪽x, 아래y, 위y,
def backtracking(self, color_dots, color, terminal_condition, x_left, x_right, y_lower, y_upper):
# 만약 종결조건이라면 (이 경우 현재의 색의 인덱스가 주어진 색의 인덱스보다 더 클경우)
# 이 경우 이미 모든 색에 대해 백트래킹을 진행한 상태
if (color > terminal_condition):
# 직사각형 면적 구해주고
rect_area = (x_right-x_left)*(y_upper-y_lower)
# 최소 면적 갱신 후
self.min_area = min(self.min_area, rect_area)
# 함수를 마친다.
return
for dot_x, dot_y in color_dots[color]:
# 각 x,y의 위치를 하나하나 탐색하며 직사각형을 서서히 넓힌다.
# 이를 위해 직사각형 각각의 x,y 후보군을 얻어냄
x_left_cand = min(x_left, dot_x)
x_right_cand = max(x_right, dot_x)
y_lower_cand = min(y_lower, dot_y)
y_upper_cand = max(y_upper, dot_y)
# 면적을 구해봄.
tmp = (x_right_cand-x_left_cand)*(y_upper_cand-y_lower_cand)
# 지금까지의 직사각형이 최소 면적보다 작을 경우에만 다음 계산 진행.
# 만약 최소 면적보다 이미 크다면 불필요한 계산이므로 계산을 진행하지 않음.
if tmp < self.min_area:
self.backtracking(color_dots, color+1, terminal_condition, x_left_cand, x_right_cand, y_lower_cand, y_upper_cand)
# 클래스 생성
sol = Solution()
# 백트래킹 돌린다. (유의할 점은, 색깔은 1부터 시작이므로 시작점을 1로,
# 그리고 x_left, y_lower은 최소값 연산이므로 가능한한 가장 큰 최댓값으로 초기값 설정,
# x_right, y_upper은 최댓값 연산이므로 가능한 가장 큰 최솟값으로 초기값 설정.)
sol.backtracking(color_dots, 1, K, 1001, -1001, 1001, -1001)
print(sol.min_area)
