[코드트리] [시뮬레이션] 2차원 바람

https://www.codetree.ai/missions/2/problems/The-2D-wind-blows/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제

0이상 9이하의 숫자로만 이루어진 N*M 행렬 모양의 건물에 총 Q번의 바람이 붑니다.

이 바람은 굉장히 특이해서 특정 직사각형 영역의 경계에 있는 숫자들을 시계 방향으로 한 칸씩 shift 하고 해당 직사각형 내 영역에 있는 값들을 각각 자신의 위치를 기준으로 자신과 인접한 원소들과의 평균 값으로 바꿉니다. (평균 계산시에는 항상 버림하여 정수값이 나오도록 합니다.)

예를 들어 바람이 다음과 같은 영역에 영향을 미치게 되는 경우를 생각해봅시다.

 

먼저 직사각형의 경계에 있는 숫자들이 시계 방향으로 한 칸씩 회전을 하게 됩니다.

 

 

그 다음 직사각형 영역 내에 있는 각각의 숫자들의 값이 현재 칸에 적혀있는 숫자 + 인접한 곳에 적혀있는 숫자들의 평균 값으로 바뀌게 됩니다. 이 과정은 순차적으로 일어나는 것이 아니라 동시에 일어납니다.

예를 들어 (2, 2) 위치에 있던 원소는 인접한 4개의 값들과의 평균값을 버림한 값인 3으로 바뀌어야 합니다.

 

(4, 6) 위치에 있던 원소는 인접한 숫자가 2개밖에 없으므로, 그 숫자들과의 평균값을 버림한 값인 6으로 바뀌게 됩니다.

 

예를 들어 다음 직사각형이 평균값이 변화는 과정을 거치면 다음과 같이 값이 변하게 됩니다.

 

한 바람이 분 이후 모든 값 변경이 완료된 이후에 그 다음 바람이 불어 온다고 할 때, 총 Q개의 바람을 거친 이후 건물의 상태를 출력하는 프로그램을 작성해보세요

 

입력 형식

첫째 줄에는 행렬의 크기를 나타내는 N과 M 그리고 총 바람이 불어온 횟수를 의미하는 Q가 공백을 사이에 두고 주어집니다.

두 번째 줄 부터 N개의 줄에 걸쳐 한 줄에 M개 씩 건물의 상태를 나타내는 0이상 9이하의 숫자가 공백을 사이에 두고 주어집니다.

그 다음 줄 부터는 Q개의 줄에 걸쳐 불어오는 바람에 대한 정보 (r1, c1, r2, c2)가 공백을 사이에 두고 주어집니다. (r1, c1)은 바람에 영향을 받는 직사각형의 좌측 상단의 위치이며 (r2, c2)는 바람에 영향을 받는 직사각형의 우측 하단의 위치입니다. 즉, 해당 바람에 의해 r1행 c1열부터 r2행 c2열까지의 직사각형이 영향을 받게 됨을 의미합니다. (1 ≤ r1 < r2 ≤ N, 1 ≤ c1 < c2 ≤ M)

• 2 ≤ N ≤ 100
• 2 ≤ M ≤ 100
• 0 ≤ Q ≤ 100

출력 형식

Q개의 바람을 거친 이후 건물의 상태를 N개의 줄에 걸쳐 출력합니다. 각 줄마다 각각의 행에 해당하는 M개의 값을 공백을 사이에 두고 출력합니다.

 

입출력 예제

예제1

입력:

4 6 1
4 5 2 5 6 6
2 1 6 1 0 5
5 2 2 1 6 5
4 5 2 8 8 6
2 2 4 6

 

출력:

4 5 2 5 6 6 
2 3 2 2 3 3 
5 3 3 4 3 4 
4 4 5 5 6 5

 

---

import sys
sys.stdin=open('input.txt', 'r')

import copy

'''
1. 회전될 직사각형 범위 확인 
2. 한번에 업데이트해야하니깐 복사된 board 필요 
3. 회전뒤 평균값 실제 보드에 업데이트 

'''

dxs=[-1,0,1,0]
dys=[0,1,0,-1] 

def in_range(nx,ny):
    return 0<=nx<N and 0<=ny<M


if __name__=="__main__":
    N,M,Q=map(int, input().split()) #  N*M 행렬, Q번 바람
    board = [list(map(int, input().split())) for _ in range(N)]
    
    new_board = copy.deepcopy(board)    # 한꺼번에 출력하기 위해 
    for _ in range(Q):
        r1,c1,r2,c2=map(int, input().split())
        r1,c1,r2,c2 =  r1-1,c1-1,r2-1,c2-1 
        grid = [[0]*M for _ in range(N)]

         
        for j in range(c1,c2):
            grid[r1][j+1] = board[r1][j]    # 윗변
            grid[r2][j] = board[r2][j+1]    # 아래변
        
        for i in range(r1,r2):
            grid[i+1][c2] = board[i][c2]    # 오른변 
            grid[i][c1] = board[i+1][c1]    # 왼변
            
        # 회전한거 업데이트
        for i in range(r1,r2+1):
            for j in range(c1,c2+1):
                if r1+1<=i<=r2-1 and c1+1<=j<=c2-1:
                    continue
                board[i][j]=grid[i][j]
        
        # 주변값 평균 업데이트 
        new_board = copy.deepcopy(board)    # 한꺼번에 출력하기 위해 
        for i in range(r1,r2+1):
            for j in range(c1,c2+1):
                ans=1
                for k in range(4):
                    ni=i+dxs[k]
                    nj=j+dys[k]
                    if in_range(ni,nj):
                        ans+=1
                        new_board[i][j] += board[ni][nj]
                        
                new_board[i][j] = new_board[i][j]//ans
        
        board = copy.deepcopy(new_board)    # 한꺼번에 출력하기 위해
        
    for b in new_board:
        print(*b)