백준 14204(표 정렬) - 해결

표 정렬

 

문제

영선이는 N행 M열로 이루어진 표를 가지고 있다. 행은 위에서부터 아래로 0번부터 N-1번까지, 열은 왼쪽에서 오른쪽으로 0번부터 M-1번까지 번호가 매겨져 있다.

표의 각 칸에는 양의 정수가 하나 쓰여 있으며, 표에 포함되어 있는 수는 1부터 N*M까지로 이루어진 순열을 이룬다. 즉, 각각의 수는 표에 한 번씩 등장한다.

표가 주어졌을 때, 행 우선 순서를 이용해 만든 수열을 값 수열이라고 한다.

영선이는 두 가지 방법을 표를 수정할 수 있는데, 임의의 두 행을 서로 위치를 바꾸거나, 두 열의 위치를 바꾸는 것이다.

표가 주어졌을 때, 값 수열을 오름차순으로 만들 수 있는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 50)

둘째 줄부터 N개의 줄에 표의 내용이 주어진다.

 

출력

입력으로 주어진 표의 값 수열을 오름차순으로 만들 수 있으면 1을, 없으면 0을 출력한다.

---

처음에는 문제이해를 못해 몇번 틀렸다.

행 우선 순서란?

행을 따라 값이 증가하고 이어서 열까지 쭉 이어져서 값이 증가하는 것.

그러한 수열을 값 수열이라 한다.

그래서 생각한 방법은 행을 신경쓰지 않는 방식.

모든 값이 하나씩 나오고 1 ~ N*M 중 하나를 가지기 때문에 각 행의 값이 1 씩 증가하는 행인지만 확인하면된다.

하지만 그 순서가 모든 행에서 같아야하기 때문에 0행의 순서를 저장하고 모든 행이 같은 순서로 되는지 확인하는 방식을 사용하였다.

import sys
input = sys.stdin.readline

N, M = map(int,input().split())

maps = [list(map(int,input().split())) for _ in range(N)]

# 0행의 인덱스와 값을 저장
sort_row_list = []
for idx, num in enumerate(maps[0][:]):
    sort_row_list.append((idx,num))

# 0행 값순으로 정렬
sort_row_list.sort(key=lambda x:x[1])

# 순서 인덱스를 저장
sort_row_idx = []
for idx, _ in sort_row_list:
    sort_row_idx.append(idx)


def sol():
    for i in range(N):
        for j in range(M-1):
            # 값이 1씩 증가하는지 확인
            if maps[i][sort_row_idx[j]] + 1 == maps[i][sort_row_idx[j+1]]:
                continue
            else:
                return 0
    # 다 이를 만족한다면 값수열 가능
    return 1

print(sol())