백준 1090 체커 파이썬 문제풀이 (python 완전탐색)

문제 보러가기

 

백준 체커 파이썬 문제풀이

체커 게임은 익숙하지 않은데, 체스판처럼 흑백 격자판에서 이루어지는 게임이다. 

 

체커 말은 상하좌우로 움직이며 겹치는게 가능하다고 한다.

 

말의 좌표가 하나씩 들어오는데 그 값은 1,000,000 이하라고 한다.

즉 여기서 100배를 더하면 1억 즉 1초가 되는데, 그것보다 적게 연산하라는 뜻이다.

 

출력하는 값으로는 k번째 수가 k개의 체커가 같은 칸에 모일 수 있는 최소 움직임 수라고 한다.

즉 체커가 특정 좌표까지 이동해야하는 수가 있고

1개만 모이는 경우부터 모든 체커말이 모이는 경우 필요한 이동 수를 구하는 문제이다.

 

상당히 난해한데..

 

바로 생각나는 접근 법은 각 체커의 이동횟수를 적어놓는 표를 만들어서 

겹쳐져야 하는 말들의 이동횟수 총합이 가장 작은 값을 찾아내는 방법이다.

 

...?

 

아니다 단순하게 생각해서 체커들이 모인 좌표들이 포함된 직사각형 구역을 찾고

그 안에서 한 칸씩 확인하면서 하는 방법도 있다.

 

전자의 경우 메모리가 필요한데 문제에서 좌표가 1,000,000이기 때문에 2차원으로 하면 너무 크기가 커진다.

 

즉 체커들의 좌표값의 최대 최소 x,y를 찾고 그 범위 안의 각 칸으로부터 체커까지의 거리의 합이 최소인 것을 찾는 방식이 가능할 것이다.

 

N = int(input())
chekerPiece = []
minX = float("inf")
minY = float("inf")
maxX = float("-inf")
maxY = float("-inf")

def distance(x1,y1,x2,y2):
    return abs(x1-x2) + abs(y1-y2)

for i in range(N):
    x,y = map(int,input().split())
    chekerPiece.append((x,y))
    if x < minX:
        minX = x
    if y < minY:
        minY = y
    if maxX < x:
        maxX = x
    if maxY < y:
        maxY = y

for y in range(minY, maxY + 1):
    for x in range(minX, maxX + 1):
        chekerDistance = [0,0,0,0]
        for i in range(N):
            chekerPosX = chekerPiece[i][0]
            chekerPosY = chekerPiece[i][1]
            chekerDistance[i] = distance(chekerPosX, chekerPosY, x, y)
        print(chekerDistance)

일단 여기까지 하고 출력을 해보면

 

4
15 14
15 16
14 15
16 15

output
[1, 3, 1, 3]
[0, 2, 2, 2]
[1, 3, 3, 1]
[2, 2, 0, 2]
[1, 1, 1, 1]
[2, 2, 2, 0]
[3, 1, 1, 3]
[2, 0, 2, 2]
[3, 1, 3, 1]

이렇게 각 좌표에 대한 체커말들의 거리가 저장되었다.

구했다면 이제 여기서 1개~N개까지의 체커말들이 같은 칸에 모였을 때 이동 최소 수를 구하자.

 

어떻게 접근 할까.

1개 라면 output element중 가장 작은 값을 고르면 되고, 2개 라면 2개의 합이 최소인 것, 3개라면 3개의 합

이런 식으로 구해야한다. 

 

일단 k개의 체커말들이 모이는 최소 이동 수 각각을 담을 배열을 만들고 진행하자. 

 

from itertools import combinations
N = int(input())
chekerPiece = []
minX = float("inf")
minY = float("inf")
maxX = float("-inf")
maxY = float("-inf")
assembleBlockDistance = []

def distance(x1,y1,x2,y2):
    return abs(x1-x2) + abs(y1-y2)

for i in range(N):
    x,y = map(int,input().split())
    chekerPiece.append((x,y))
    if x < minX:
        minX = x
    if y < minY:
        minY = y
    if maxX < x:
        maxX = x
    if maxY < y:
        maxY = y
    assembleBlockDistance.append(float("inf")) # 칸 수 채우기

for y in range(minY, maxY + 1):
    for x in range(minX, maxX + 1):
        chekerDistance = [0,0,0,0]
        for i in range(N):
            chekerPosX = chekerPiece[i][0]
            chekerPosY = chekerPiece[i][1]
            chekerDistance[i] = distance(chekerPosX, chekerPosY, x, y)
        
        # 최소 거리 저장하기
        for j in range(N):
            combList = list(combinations(chekerDistance,j + 1))
            for comb in combList:
                if sum(comb) < assembleBlockDistance[j]:
                    assembleBlockDistance[j] = sum(comb)
for i in assembleBlockDistance:
    print(i, end=" ")

이렇게 cheker distance의 조합을 구해서 최소 거리를 저장하는 로직으로 구했다.

조합의 경우 생각이 안나서 찾아보았는데, 혹시 모르니 구현 방법을 외워두면 좋겠다.

 

4
15 14
15 16
14 15
16 15

output
0 2 3 4

예제 입력의 답은 잘 나온다. 

 

제출해보자.

런타임 에러 

이런.. 런타임 에러라니..

 

어떤게 문제인지 잘 모르겠다. 틀린 것도 아니고 런타임 에러라니..

 

from itertools import combinations

N = int(input())
chekerPiece = []
minX = 0
minY = 0
maxX = 1_000_000
maxY = 1_000_000
assembleBlockDistance = [1_000_000] * N  # 초기화 값 수정

def distance(x1,y1,x2,y2):
    return abs(x1-x2) + abs(y1-y2)

for i in range(N):
    x, y = map(int, input().split())
    chekerPiece.append((x, y))
    if x < minX:
        minX = x
    if y < minY:
        minY = y
    if maxX < x:
        maxX = x
    if maxY < y:
        maxY = y

for y in range(minY, maxY + 1):
    for x in range(minX, maxX + 1):
        chekerDistance = [0] * N  # N개의 체크 거리를 저장할 수 있도록 초기화
        for i in range(N):
            chekerPosX = chekerPiece[i][0]
            chekerPosY = chekerPiece[i][1]
            chekerDistance[i] = distance(chekerPosX, chekerPosY, x, y)

        # 최소 거리 저장하기
        for j in range(N):
            combList = list(combinations(chekerDistance, j + 1))
            for comb in combList:
                if sum(comb) < assembleBlockDistance[j]:
                    assembleBlockDistance[j] = sum(comb)

for i in assembleBlockDistance:
    print(i)

거리를 저장하는 배열의 크기 때문에 out of range가 나는 것이라고 생각해서

위처럼 배열을 초기화해보았다.

 

또 아까보니 cheker distance 배열 크기를 4개로 잡아놓고 있던것도 문제였다. 

이런... 그래도 런타임 에러는 아니다. 

이제는 방법이 고갈되었으니 외부에서 힌트를 얻어보자.

 

힌트

메모리 초과라는 것은 최적화가 부족하다는 뜻이다. 최적화를 위한 방법의 힌트를 얻어보자.

 

여러 체커말들이 모이는 자리는 단순하게 생각하면 좌표의 중간에 보통 있을 것 같다. 어느 말과 어느 말의 사이에 있지 않겠나. 하지만 하나씩 테스트를 해보면 특이한 규칙을 알 수 있다.

 

그 규칙은 여러 말들이 한 곳에서 모인 때 최소가 되는 비용은 신기하게도 말들이 위치한 좌표의 x값 y값을 가진 좌표가 가장 비용이 적은 지점들이라는 점이다. 

이게 무슨 말이냐면 

 

16		O
15	O		O
14		O
x/y	14	15	16

 

이러한 형태로 체커 말이 있다면

말들이 위치한 좌표의 x값은 14,15,16 모두 있고 y값도 14,15,16 모두 있다.

그럼 x가 14,15,16 y가 14,15,16 인 좌표 중 하나가 가장 이동 수가 적은 지점이 된다는 말이다.

 

이러한 규칙을 처음부터 알아낸다는 것은 어렵다. 힌트를 보면서 그제서야 그렇구나! 하게 되었는데.

1차원으로 단순화에서 몇 가지 케이스를 시뮬레이션 해보면서 팁을 찾아보면서 나오게 되는 힌트였다. 

 

힌트 2

 또 다른 힌트를 찾을 수 있었는데, 가만 듣고 있으니 이 방법은 가장 처음에 언급했던

각 체커의 이동횟수를 적어놓는 표를 만들어서 
겹쳐져야 하는 말들의 이동횟수 총합이 가장 작은 값을 찾아내는 방법

 

이었다. 근데 조금 아이디어가 달랐다. 각 체커말이 모든 칸에 대해서 이동횟수를 적어놓고 더하는게 아니라.

 

체커 말 A,B,C,D가 있으면 A가 다른 체커 말의 위치 B,C,D로 각각 이동할 거리를 구하고, 

B,C,D 말에 대해서도 다른 말의 위치로 이동하는 거리들을 각각 구해본다고 가정하자.

 

그러면 이제 A말이 목적지로 이동하는데 필요한 거리는

목적지 A,B,C,D → 이동거리 [0, 1, 2, 3]

이런식으로 나올 것이다.

 

마찬가지로 모든 말에 대해서 각 목적지별 필요 거리를 구한다고 하면,

A말
목적지 A,B,C,D → 이동거리 [0, 1, 2, 3]

B말
목적지 A,B,C,D → 이동거리 [1, 0, 2, 3]

C말
목적지 A,B,C,D → 이동거리 [2, 2, 0, 1]

D말
목적지 A,B,C,D → 이동거리 [2, 2, 2, 0]

예를 들어서 위와 같은 형식으로 나온다는 말이다. (값은 아무거나 넣은 임시 값)

k개의 말이 모여야한다면, 위 값들 중 같은 목적지를 향한 k개를 더했을 때 최소 값이 나오는 경우를 구한다는 말이다. 

 

처음에 생각했던 방법은 모든 칸에 대해서 이동거리 표를 만들고 k개 말이 이동하는데 최소 거리가 나오는 칸을 찾는거였다면, "힌트: 기존 체커 말이 위치한 x 좌표와 y 좌표들이 최소 거리 칸의 후보군이다"를 이용해서 구할 범위를 줄이는 것이다.

 

힌트를 생각하기가 사람에 따라 쉽지 않은데, 힌트까지 봤으니 구현으로 넘어가보자. 

 

구현하기

최소 거리 칸의 후보군을 체크하는 코드를 기존 코드에다 추가하자.

반복문을 수정해서, 이미 체커 말이 위치한 좌표만 탐색하는 쪽으로 변경한다. 

 

min, max를 없애고 좌표 리스트를 만들자.

set 자료형을 이용해서 좌표 리스트 x list와 y list 를 만들어서 리스트를 순회하도록 했다.

from itertools import combinations
N = int(input())
chekerPiece = []
listX = set()
listY = set()
assembleBlockDistance = [1_000_000] * N

def distance(x1,y1,x2,y2):
    return abs(x1-x2) + abs(y1-y2)

for i in range(N):
    x,y = map(int,input().split())
    chekerPiece.append((x,y))
    listX.add(x)
    listY.add(y)

for y in listY:
    for x in listX:
        chekerDistance = [0] * N
        for i in range(N):
            chekerPosX = chekerPiece[i][0]
            chekerPosY = chekerPiece[i][1]
            chekerDistance[i] = distance(chekerPosX, chekerPosY, x, y)
        
        # 최소 거리 저장하기
        for j in range(N):
            combList = list(combinations(chekerDistance,j + 1))
            for comb in combList:
                if sum(comb) < assembleBlockDistance[j]:
                    assembleBlockDistance[j] = sum(comb)
for i in assembleBlockDistance:
    print(i)

컴파일 에러..

잉? python으로 바꾸고 다시

아.. 

 

여기서 메모리를 더 줄이려면..

찾아보니 combination이 원인일 수 있다고 한다.

 

아 생각해보니 조합을 사용하지 않고 오름차순으로 정렬하기만 해도,

체커 말 몇 개가 모이면 되는 구조니까 충분히 해결할 수 있을 것이다. 

어떤 말을 사용하는지는 상관없이 몇 개가 모이는지가 중요하기 때문이다.

 

N = int(input())
chekerPiece = []
listX = set()
listY = set()
assembleBlockDistance = [1_000_000] * N

def distance(x1,y1,x2,y2):
    return abs(x1-x2) + abs(y1-y2)

for i in range(N):
    x,y = map(int,input().split())
    chekerPiece.append((x,y))
    listX.add(x)
    listY.add(y)

for y in listY:
    for x in listX:
        chekerDistance = [0] * N
        for i in range(N):
            chekerPosX = chekerPiece[i][0]
            chekerPosY = chekerPiece[i][1]
            chekerDistance[i] = distance(chekerPosX, chekerPosY, x, y)
        chekerDistance.sort()
        
        # 최소 거리 저장하기
        for j in range(N):
            if sum(chekerDistance[0:j+1]) < assembleBlockDistance[j]:
                assembleBlockDistance[j] = sum(chekerDistance[0:j+1])
for i in assembleBlockDistance:
    print(i)

이렇게 sort 방법으로 변경해서 제출했는데

뭐가 틀렸지.

 

assembleBlockDistance[j]

이걸 초기화 하는게 문제였나 싶다. 

 

발견했다. 문제는 

assembleBlockDistance = [1_000_000] * N

이 부분이었다.

assembleBlockDistance = [float('inf')] * N

이렇게 수정하니까 

정상 통과가 되었는데

생각해보니 범위가 백만이라고 해서 이동 최대 값이 백만이지는 않다는 걸 알았다.

(0,0)에서 (1000000,1000000)로 이동하면 2,000,000 이다. 

 

로직은 틀리지 않았는데 초기화 값에서 잘못 생각했다.

 

오답정리

정리하자면 메모리 초과의 사유는 itertools combination의 사용이고

틀린 이유는 최댓값 초기화 착오였다.

답안 코드

N = int(input())
chekerPiece = []
listX = set()
listY = set()
assembleBlockDistance = [float('inf')] * N

def distance(x1,y1,x2,y2):
    return abs(x1-x2) + abs(y1-y2)

for i in range(N):
    x,y = map(int,input().split())
    chekerPiece.append((x,y))
    listX.add(x)
    listY.add(y)

for y in listY:
    for x in listX:
        chekerDistance = [0] * N
        for i in range(N):
            chekerPosX = chekerPiece[i][0]
            chekerPosY = chekerPiece[i][1]
            chekerDistance[i] = distance(chekerPosX, chekerPosY, x, y)
        chekerDistance.sort()
        
        # 최소 거리 저장하기
        for j in range(N):
            if sum(chekerDistance[0:j+1]) < assembleBlockDistance[j]:
                assembleBlockDistance[j] = sum(chekerDistance[0:j+1])
for i in assembleBlockDistance:
    print(i)