[코드트리 챌린지] 3주차 - 2차원 바람

· 문제링크

https://www.codetree.ai/cote/13/problems/The-2D-wind-blows?&utm_source=clipboard&utm_medium=text 

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

· 핵심 : 2차원 돌리기

1. 대상이 되는 2차원 좌표들의 집합 모으기

# 2차원 회전 - 좌표집합 밀기로 접근
def get_grids(r1, c1, r2, c2):
    qs = deque([])
    for col in range(c1, c2 + 1):
        qs.append((r1, col))
    for row in range(r1 + 1, r2 + 1):
        qs.append((row,c2))
    for col in range(c2 - 1, c1 - 1, -1):
        qs.append((r2, col))
    for row in range(r2 - 1, r1, -1):
        qs.append((row, c1))
    return qs

---

2 - 1. deque의 rotate를 활용해서 2차원 좌표 집합 돌리기

# deque를 이용한 2차원 회전
def wind_simulate(qs):
    tmps = deque([])
    for r, c in qs:
        tmps.append(board[r][c])
    tmps.rotate(1)
    for idx, (r, c) in enumerate(qs):
        board[r][c] = tmps[idx]

    return board

---

2 - 2. temp를 활용해서 2차원 집합 돌리기

 

# temp 활용
def wind_simulate(qs):
    r, c = qs[-1]
    temp = board[r][c]
    temp_r, temp_c = qs[0]
    for i in range(len(qs) - 1, 0, -1):
        cr, cc = qs[i]
        nr, nc = qs[i - 1]
        board[cr][cc] = board[nr][nc]
    board[temp_r][temp_c] = temp

    return board

---

3. 해당되는 영역 동시에 평균값 만들기 

→ diffusion_board 라는 새로운 배열 도입해서 평균값 기록하기

→ 새로운 배열을 도입한 이유는 기존 보드에 기록해버리면 기록한 것이 다른 좌표의 평균값 계산에 영향을 미치게 된다.

→ 동시에 평균값을 만들기 위해서는 새로운 보드에 영역에 해당하는 값들의 평균값을 따로 적어놔야한다.

→ 기존의 board에서 해당영역만 diffusion_board 값으로 대체한다.

# 확산시키기
def diffusion_simulate(r1, c1, r2, c2):
    diffusion_board = [[0 for _ in range(m)] for _ in range(n)]
    dr = [0, 1, 0, -1]
    dc = [1, 0, -1, 0]
    for r in range(r1, r2 + 1):
        for c in range(c1, c2 + 1):
            sum_val = board[r][c]
            cnt = 1
            for k in range(4):
                nr, nc = r + dr[k], c + dc[k]
                if in_range(nr, nc):
                    cnt += 1
                    sum_val += board[nr][nc]
            sum_val = math.floor(sum_val / cnt)
            diffusion_board[r][c] = sum_val
    return diffusion_board

---

· 코드(Python)

from collections import deque
import math

# 상하좌우 이동을 나타내는 방향 배열
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]

# 격자 내 범위 체크
def in_range(r, c):
    return 0 <= r < n and 0 <= c < m

# 2차원 회전 - 좌표집합 밀기로 접근
def get_grids(r1, c1, r2, c2):
    qs = deque([])
    for col in range(c1, c2 + 1):
        qs.append((r1, col))
    for row in range(r1 + 1, r2 + 1):
        qs.append((row, c2))
    for col in range(c2 - 1, c1 - 1, -1):
        qs.append((r2, col))
    for row in range(r2 - 1, r1, -1):
        qs.append((row, c1))
    return qs

# 격자 회전 및 확산 시뮬레이션
def simulate(r1, c1, r2, c2):
    tmps = deque([])
    for r, c in get_grids(r1, c1, r2, c2):
        tmps.append(board[r][c])
    tmps.rotate(1)
    for idx, (r, c) in enumerate(get_grids(r1, c1, r2, c2)):
        board[r][c] = tmps[idx]

    diffusion_board = [[0 for _ in range(m)] for _ in range(n)]
    for r in range(r1, r2 + 1):
        for c in range(c1, c2 + 1):
            sum_val = board[r][c]
            cnt = 1
            for k in range(4):
                nr, nc = r + dr[k], c + dc[k]
                if in_range(nr, nc):
                    cnt += 1
                    sum_val += board[nr][nc]
            sum_val = math.floor(sum_val / cnt)
            diffusion_board[r][c] = sum_val

    for r in range(r1, r2 + 1):
        for c in range(c1, c2 + 1):
            board[r][c] = diffusion_board[r][c]

n, m, q = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]

for _ in range(q):
    r1, c1, r2, c2 = map(int, input().split())
    r1 -= 1
    c1 -= 1
    r2 -= 1
    c2 -= 1
    simulate(r1, c1, r2, c2)

for row in board:
    print(*row)