[백준] 18868번 멀티버스Ⅰ(파이썬)

18868번: 멀티버스 Ⅰ

 

문제

M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍은 한 번만 센다.

두 우주 A와 B가 있고, 우주 A에 있는 행성의 크기는 A1, A2, ..., AN, 우주 B에 있는 행성의 크기는 B1, B2, ..., BN라고 하자. 두 우주의 행성 크기가 모든 1 ≤ i, j ≤ N에 대해서 아래와 같은 조건을 만족한다면, 두 우주를 균등하다고 한다.

• Ai < Aj → Bi < Bj
• Ai = Aj → Bi = Bj
• Ai > Aj → Bi > Bj

입력

첫째 줄에 우주의 개수 M과 각 우주에 있는 행성의 개수 N이 주어진다. 둘째 줄부터 M개의 줄에 공백으로 구분된 행성의 크기가 한 줄에 하나씩 1번 우주부터 차례대로 주어진다.

출력

첫째 줄에 균등한 우주의 쌍의 개수를 출력한다. 

제한

• 2 ≤ M ≤ 10
• 3 ≤ N ≤ 100
• 1 ≤ 행성의 크기 ≤ 10,000

---

코드

m, n = map(int, input().split())
universe = [list(map(int, input().split())) for _ in range(m)]
cnt = 0

for planet in range(m):
    for i in range(m):
        arr_sort = sorted(universe[i])  # 정렬 먼저 해준 후
        idx = []
        for j in universe[i]:  # 크기 순으로 인덱스 순서 리스트 만들기
            idx.append(arr_sort.index(j) + 1)
        universe[i] = idx

for i in range(m - 1):
    for j in range(i + 1, m):
        if universe[i] == universe[j]:  # 우주끼리 리스트 순서가 같으면 cnt++
            cnt += 1

print(cnt)

 

풀이

이 문제는 요소들을 하나씩 비교하는 것이 아닌, 크기를 비교하는 것이 포인트이다. 

예를 들어, [2 1 3], [4 1 5]  이렇게 두 우주가 있다. 이것을 크기 순으로 나타내면 

→ [2 1 3], [2 1 3]으로 크기 순서가 같다. 이렇게 순서가 같다면 이를 균등한 우주라고 하는 것이다. 

따라서 리스트를 먼저 정렬해준 후, 크기 순으로 인덱스 순서를 넣어준다. 

그러고 우주마다 비교해 리스트 순서가 같으면 개수를 카운트시켜준다.