백준 문제 풀이 - 멀티버스 Ⅰ 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

💡 문제 재정의

우주안에서 모든 행성들의 대소관계가 같다면 같은 우주이고 같은 우주들의 개수를 출력해라.

✏️ 계획 수립

우선 이 문제는 각 우주의 대소 관계를 전부 비교한 뒤 다른 우주들과 대소 관계가 똑같은지 세보면 된다. 일단 대소관계를 비교하기 위한 2차원 행렬을 만들고 행과 열에 대소관계 비교 결과를 작성한다. 예를 들어 planet1이 planet2보다 작다면 i행 j열에 1을 작성하고 비슷하다면 2 크다면 3을 작성해 대소 관계 표현 행렬을 각 우주마다 만든다. 그리고 각 우주별로 같은 행렬을 가지고 있는지 비교한뒤 카운트해주면 된다.

💻 계획 수행

import sys

if __name__ == '__main__':
    M, N = map(int, sys.stdin.readline().split())

    universe_list = []
    count = 0

    for i in range(M):
        planets = list(map(int, sys.stdin.readline().split()))
        planet_matrix = [[0] * N for _ in range(N)]
        for j in range(len(planets)):
            for k in range(j + 1, len(planets)):
                if planets[j] < planets[k]:
                    planet_matrix[j][k] = 1
                elif planets[j] == planets[k]:
                    planet_matrix[j][k] = 2
                elif planets[j] > planets[k]:
                    planet_matrix[j][k] = 3
        universe_list.append(planet_matrix)
        for universe in universe_list[:-1]:
            if universe == universe_list[-1]:
                count += 1

    print(count)

🤔 회고

대소관계를 전부 비교하는건 쉽지만 각 우주별로 비교하는게 까다로운 문제였다. 이런 문제는 행렬을 사용하면 쉽게 풀 수 있다.