BOJ 25966 - 배찬우는 배열을 좋아해 (Python3)

이건 얼마 전 출제된 2022 Goricon B번 문제였다. A번 문제는 무난무난한 브론즈 3 ~ 브론즈 4 문제니 추후 업로드할 것이다.

간단한 2차원 배열 문제이다. 그렇다고 하더라도 무지성으로 구현하면 시간초과가 날 수 있으니 조심하자.

내 코드도 거의 5초를 잡아먹었다. 파이썬이 특히 느린 것은 맞지만 다른 언어군인 C++나 C에서도 툭하면은 시간초과가 튀어나오더라.

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

찬우는 오늘 프로그래밍 기초 강의에서 2차원 배열에 대해 배웠다. 너무 재미있던 찬우는 2차원 배열에다 연산을 진행하기로 결심했다.

아래와 같은 두 가지 종류의 연산이 쿼리로 주어진다.

 

• 0 i j k : i번 행의 j번 열의 값을 k로 바꾼다.
• 1 i j : i번 행과 j번 행을 swap한다.

swap 이란 i번 행의 모든 원소와 j번 행의 모든 원소를 바꾸는 연산이다. q개의 쿼리를 수행한 후 바뀐 배열의 최종 결과를 출력하시오.

 

입력

첫째 줄에 행의 개수 N과 열의 개수 M, 쿼리의 개수 q가 주어진다. (1 ≤ N, M ≤ 3000, 1 ≤ q ≤ \(10^6\)) 

2번째 줄부터 N개의 줄에 걸쳐 N행 M열의 2차원 배열이 입력으로 주어진다. 배열의 각 원소의 값은 1 이상 10000 이하의 정수이다.

이후 q개 줄에 걸쳐 쿼리가 입력으로 주어진다.

쿼리는 0 i j k 혹은 1 i j의 형태로 주어지며, 쿼리의 첫 번째 값이 0이면 첫 번째 쿼리를, 1이면 두 번째 쿼리를 수행한다.

첫 번째 쿼리의 경우 i, j, k의 범위는 (0 ≤ i ≤ N-1, 0 ≤ j ≤ M-1, 1 ≤ k ≤ 10000)이며 k는 정수이다.

두 번째 쿼리의 경우 i, j의 범위는 (0 ≤ i, j ≤ N-1)이다.

 

예제 입력)

4 3 4
10 3 8
2 10 4
1 8 4
1 4 2
1 2 2
0 1 0 9
1 2 1
1 3 0

 

출력

q개의 쿼리를 전부 수행한 후의 2차원 배열을 출력한다.

 

예제 출력)

1 4 2
1 8 4
9 10 4
10 3 8

 

---

내 코드

from sys import stdin
input = stdin.readline

N, M, q = map(int, input().split())
matrix = [[0]*M]*N
for i in range(N):
    matrix[i] = list(map(int, input().split()))
for _ in range(q):
    query = list(map(int, input().split()))
    if query[0] == 0:
        matrix[query[1]][query[2]] = query[3]
    elif query[0] == 1:
        matrix[query[1]], matrix[query[2]] = matrix[query[2]], matrix[query[1]]
for i in range(N):
    row = map(str, matrix[i])
    print(" ".join(row))

 

일단 입력받는 수가 굉장히 많다. 최악의 경우 2차원 배열만 해도 3000줄, 쿼리는 1백만 줄이 들어온다.

그러니까 그냥 input으로 집어넣게 된다면 십중팔구 시간초과로 인한 오답 처리가 될 것이다.

그러니 시작하기 전에 input을 stdin.readline인 조금 더 빠른 인풋 코드로 미리 바꿔쳐놔야 한다.

매번 stdin.readline을 치는 것보다는 더 빠르고 빠트릴 염려도 없다.

 

우선 첫 번째 for문에서는 matrix에 2차원 배열을 집어넣는 역할을 수행한다.

공백으로 구분된 것을 전부 흩뿌려서 list로 만든 후 matrix의 i번째 가로줄에 넣어주는 것이 첫 번째 반복문의 역할. 이 쪽에 대해서는 더 설명할 여지가 없다.

 

두 번째 for문에서는 입력된 쿼리를 순서대로 수행하여 줄 것이다.

0형 쿼리는 첫 원소가 0이고, 1형 쿼리는 첫 원소가 1이 되니, 첫 원소에 따라서 쿼리를 어떤 식으로 처리할지 나눌 것이다.

0형 쿼리에서는 matrix의 (query[1], query[2]) 원소를 query[3]으로 바꿀 것이니 그렇게 처리를 하고,

1형 쿼리에서는 matrix[query[1]], matrix[query[2]]를 바꾸는 것을 처리해 주면 된다.

모든 쿼리의 처리가 끝나면 그 때 세 번째 for문으로 모든 행을 차례차례 인쇄하면 끝.

 

이로서 25966번의 풀이를 마친다.

그럼, 오늘도 당신의 코딩 실력이 상승하기를.