문제 설명

이번 포스팅은 백준 16926번: 배열 돌리기 1 문제 풀이에 대한 기록입니다.

문제를 간단히 요약하자면, "2차원 배열이 주어졌을 때, 이를 반시계 방향으로 R번 회전시킨 결과를 출력하는 문제" 입니다. 문제는 간단하쥬?

풀이

1. 2차원 배열을 1차원으로 변형한 후 회전시키기

---

이 문제는 2차원 배열 안에 있는 원소들을 회전을 통해 다른 위치로 옮겨야 하는 문제입니다.

그러나 2차원 배열의 형태를 유지하면서 원소들의 위치를 조정하려면 index를 계산하는 것이 아주 까다로울 것 같은 예감이 들었습니다..ㅎㅎ

그래서 제가 사용한 방법은 "1차원으로 늘어뜨리고 회전시킨 다음, 다시 역순을 거쳐 2차원으로 만들자!" 였습니다.

그럼 어떻게 1차원 배열로 바꿔야 "회전" 시키기 가장 편할까요?

문제에서 주어진 회전의 예시를 보면, 가장 바깥쪽을 이루는 첫번째 껍질과 안쪽 두 번째 껍질이 독립적으로 회전 하는 것을 볼 수 있습니다.

따라서 각 껍질별로 1차원으로 나열하는 것이 후에 회전 작업에 용이해보입니다.

왼쪽 상단 원소를 껍질의 시작점이라 가정하고, 시작 상태 배열에서의 각 껍질을 시계방향으로 순서대로 나열하면 다음과 같아집니다.

첫 번째 껍질 : 1 2 3 4 8 6 2 3 4 5 9 5
두 번째 껍질 : 6 7 7 8

이 상태에서 회전시키는 것은 아주아주 쉽습니다.

맨 앞에서부터 R개의 원소를 잘라 맨 뒤에 붙여주기만 하면 됩니다.

첫 번째 껍질 2번 회전 후 : 3 4 8 6 2 3 4 5 9 5 1 2
두 번째 껍질 2번 회전 후 : 7 8 6 7

이렇게 회전이 완료된 배열을 시계방향으로 읽으며 위 예시의 결과와 비교해보면 알맞게 회전된 것을 볼 수 있습니다.

아이디어는 정리가 되었으니, 이제 이를 구현하면 끝입니다!

2. 아이디어 구현하기 (deque의 rotate 사용)

---

위처럼 1차원 배열을 회전시키기 위해 python의 collections 라이브러리에서 제공하는 deque 자료구조를 활용하였습니다.

일반적인 list를 사용할 수도 있겠지만, deque를 사용한 이유는 두 가지 입니다.

1) list에서 맨 앞 원소를 떼어내기 위한 pop(0)는 $O(n)$이 소요되지만, deque의 popleft()는 $O(1)$

2) deque에서는 rotate()라는 편리한 회전 함수를 제공

matrix = []
deq = deque()

for i in range(N):
    matrix.append(list(stdin.readline().split()))

먼저 matrix에 우리가 시작 상태의 2차원 배열을 저장해놓습니다.

loops = min(N, M) // 2
for i in range(loops):
	# 1차원 배열로 변환
    deq.clear()
    deq.extend(matrix[i][i:M-i])	# 위쪽
    deq.extend([row[M-i-1] for row in matrix[i+1:N-i-1]]) 	# 오른쪽
    deq.extend(matrix[N-i-1][i:M-i][::-1]) 		# 아래쪽
    deq.extend([row[i] for row in matrix[i+1:N-i-1]][::-1]) 	# 왼쪽

이후, 각 껍질별로 나누어 작업하기 위해서 배열의 행과 열인 N, M 중 짝수인 쪽의 절반(껍질의 개수가 됨) 만큼 for문을 반복시킵니다.

각 껍질은 위와 같이 네 부분으로 분할하여 시계 방향으로 각각 deque 에 연결해가며 1차원 배열로 변환합니다.

# 회전
deq.rotate(-R)

회전은 rotate() 함수를 사용합니다.

매개변수가 양수이면 그만큼 오른쪽으로, 즉 끝에 있는 원소가 앞으로 오는 형태로 회전하고, 음수일 땐 그 반대입니다.

우리는 앞에 있는 원소가 뒤로 가는 회전을 해야하므로, -R 을 매개변수로 줍니다.

# 다시 2차원 배열로 변환
for j in range(i, M-i):                 # 위쪽
	answer[i][j] = deq.popleft()
for j in range(i+1, N-i-1):             # 오른쪽
	answer[j][M-i-1] = deq.popleft()
for j in range(M-i-1, i-1, -1):           # 아래쪽
	answer[N-i-1][j] = deq.popleft()  
for j in range(N-i-2, i, -1):           # 왼쪽
	answer[j][i] = deq.popleft()

마지막으로 회전된 결과를 저장하는 2차원 배열 answer 에 회전된 각 껍질들을 다시 올바른 위치에 두어 2차원 배열로 변환하면 끝입니다.

for line in answer:
    print(" ".join(line))

answer 배열을 한 줄씩 출력해주면... 문제 해결!!

결과 코드

from sys import stdin
from collections import deque

N, M, R = map(int, stdin.readline().split())

matrix = []
answer = [[0]*M for _ in range(N)]
deq = deque()

for i in range(N):
    matrix.append(list(stdin.readline().split()))

loops = min(N, M) // 2
for i in range(loops):
    deq.clear()
    deq.extend(matrix[i][i:M-i])
    deq.extend([row[M-i-1] for row in matrix[i+1:N-i-1]])
    deq.extend(matrix[N-i-1][i:M-i][::-1])
    deq.extend([row[i] for row in matrix[i+1:N-i-1]][::-1])
    
    deq.rotate(-R)
    
    for j in range(i, M-i):                 # 위쪽
        answer[i][j] = deq.popleft()
    for j in range(i+1, N-i-1):             # 오른쪽
        answer[j][M-i-1] = deq.popleft()
    for j in range(M-i-1, i-1, -1):           # 아래쪽
        answer[N-i-1][j] = deq.popleft()  
    for j in range(N-i-2, i, -1):           # 왼쪽
        answer[j][i] = deq.popleft()    

for line in answer:
    print(" ".join(line))