[백준]2887 행성 터널(Python)

https://www.acmicpc.net/problem/2887

2887번: 행성 터널

 

문제 접근

 

행성의 위치 정보를 입력받은 후, 반복문을 통해 행성 간의 거리 정보를 담고 그 후의 로직은 앞서 푼 문제들과 같다고 생각했다. 실제로 코드를 작성한 후에 출력 결과는 동일하지만 메모리 초과가 발생하여 실패하였다.(실패한 코드 첨부)

 

Why..?

load 리스트에 모든 행성 간의 거리 정보를 저장하려고 하기 때문에 발생 

행성의 수가 N개일 때, N^2의 공간이 필요

 

해결방법?

각 행성을 x, y, z 좌표별로 정렬한 후 인접한 행성들만 비교 

 

코드

 

<실패>

import sys

sys.setrecursionlimit(1000000)  # 재귀 깊이 제한 늘리기
input = sys.stdin.readline

# 찾기 연산(같은 집합에 속하는지 확인)
def find_parent(x):
    if parents[x] != x:
        parents[x] = find_parent(parents[x])
    return parents[x]


# 합집합 연산(두 집합을 합치기 위한 함수)
def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parents[b] = a
    else:
        parents[a] = b

# 행성 개수
N = int(input())

# 부모 테이블
parents = [i for i in range(N+1)]

# 길 정보를 담을 리스트와 최소 신장 트리 비용 변수 선언
load = []
planet = []
total_cost = 0

for _ in range(N):
    p = list(map(int, input().split()))
    planet.append(p)

for i in range(N):
    p1 = planet[i]
    for j in range(i+1, N):
        p2 = planet[j]
        cost = min(abs(planet[i][0]-planet[j][0]), abs(planet[i][1]-planet[j][1]),abs(planet[i][2]-planet[j][2]))
        load.append([i, j, cost])

load.sort(key=lambda x:x[2])    # cost를 기준으로 오름차순 정렬
# print(load)

for i in range(len(load)):
    s = load[i][0]
    e = load[i][1]
    w = load[i][2]
    if find_parent(s) != find_parent(e) :
        union_parent(s, e)
        total_cost += w

print(total_cost)

<성공>

import sys

sys.setrecursionlimit(1000000)  # 재귀 깊이 제한 늘리기
input = sys.stdin.readline

# 찾기 연산(같은 집합에 속하는지 확인)
def find_parent(x):
    if parents[x] != x:
        parents[x] = find_parent(parents[x])
    return parents[x]


# 합집합 연산(두 집합을 합치기 위한 함수)
def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parents[b] = a
    else:
        parents[a] = b

# 행성 개수
N = int(input())

# 부모 테이블
parents = [i for i in range(N+1)]

# 길 정보를 담을 리스트와 최소 신장 트리 비용 변수 선언
load = []
# 강 행성의 위치 정보 저장한 리스트
planet = []

# 행성의 최소 비용 저장할 변수
total_cost = 0

for i in range(N):
    x, y, z = map(int, input().split())
    planet.append((x, y, z, i)) # 위치 + 행성번호

planet.sort()   # x를 기준으로 오름차순 정렬
for i in range(1, N):
    load.append((planet[i-1][3], planet[i][3], abs(planet[i-1][0]-planet[i][0])))
print(load)

planet.sort(key=lambda x: x[1])
for i in range(1, N):
    load.append((planet[i-1][3], planet[i][3], abs(planet[i-1][1] - planet[i][1])))
print(load)

planet.sort(key=lambda x: x[2])
for i in range(1, N):
    load.append((planet[i-1][3], planet[i][3], abs(planet[i-1][2] - planet[i][2])))
print(load)

# 거리를 기준으로 오름차순 정렬
load.sort(key=lambda x: x[2])

print(load)

# 최소 신장 트리 비용 계산
total_cost = 0
for s, e, w in load:
    if find_parent(s) != find_parent(e):
        union_parent(s, e)
        total_cost += w

print(total_cost)

문제 회고

 

오답을 하는 과정에서도 이게 x → y →  z 축 순으로 오름차순 정렬하는 것이 왜 효율적인지 이해가 어려웠다.

실패한 코드의 경우 N*(N-1)/2 개의 거리 정보 계산 후 저장

성공한 코드의 경우 인접한 행성의 거리만을 계산하기 때문에 3*(N-1) 개의 거리 정보 계산 후 저장