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

· 문제링크

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

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

· 핵심

1. 오른쪽 바람, 왼쪽 바람 : 격자 안에 밀고 당기기 유형

→ 1) 직접 구현

# 오른쪽 바람
def right_wind(r: int):
    row = board[r]
    temp = row[0]
    for i in range(m - 1):
        row[i] = row[i + 1]
    row[-1] = temp
    return row

→ 2) deque의 rotate 활용

q1 = deque([1, 2, 3, 4, 5)]
q2 = deque([1, 2, 3, 4, 5)]

# 요소를 오른쪽으로 밀기(왼쪽에서 밀기)
print(q1.roate(1)) # 5 1 2 3 4
# 요소를 왼쪽으로 밀기(오른쪽에서 밀기)
print(q2.rotate(-1)) # 2 3 4 5 1

2. 바람의 영향을 받는 행 판단하기

def in_range(cr: int, nr: int):
    if nr < 0 or nr >= n:
        return False

    for i in range(m):
        if board[cr][i] == board[nr][i]:
            return True

    return False

→ 1) 행이 board를 넘어가는지 판단하기

→ 2) 영향을 받는 행이 있는지 판단하기

 

3. 바람의 영향을 받는 경우 바람의 방향이 반대로 

→ R 방향 = 1, L 방향 = 0으로 설정하고 방향 반대 전환시킬 때 XOR 연산 활용하기

→ 1^0 = 1,  0^1 = 1

 

4. du = dd = d 설정

→ r을 기준으로 [up : 0 ~ r - 1] / [down : r + 1 ~ n] 각 행을 for문을 돌면서 영향받는지 확인

→ in_range가 참일 경우 simulate / in_range가 False일 경우 break : 더 이상 영향을 미치지 못하므로

 

→ du =dd = d 설정한 이유 : d로 받아버리면 up 돌고난 이후에 d가 초기값과 달라지는 문제가 발생하므로 초기 방향을 저장해야함.

---

· 코드(Python)

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

# 오른쪽 바람
def right_wind(r: int):
    row = board[r]
    temp = row[0]
    for i in range(m - 1):
        row[i] = row[i + 1]
    row[-1] = temp
    return row

# 왼쪽 바람
def left_wind(r: int):
    row = board[r]
    temp = row[-1]
    for i in range(m - 1, 0, -1):
        row[i] = row[i - 1]
    row[0] = temp
    return row

# in_range(현재행, 다음행)
def in_range(cr: int, nr: int):
    if nr < 0 or nr >= n:
        return False

    for i in range(m):
        if board[cr][i] == board[nr][i]:
            return True

    return False

# 바람에 따른 이동  
def simulate(r:int, d: int):
    if d == 0:
        board[r] = left_wind(r)
    else:
        board[r] = right_wind(r)
        
# 시뮬레이션
for _ in range(q):
    r, d = list(input().split())
    # 1base
    r = int(r) - 1
    # right_wind = R = 1 / left_wind = L = 0
    d = 1 if d == 'R' else 0
    du = dd = d
    # 처음 명령 수행
    simulate(r, d)
    # 위 방향 영향 확인
    # up : index : r - 1 ~ 0
    for cr in range(r, 0, -1):
        du ^= 1
        if in_range(cr, cr - 1):
            simulate(cr - 1, du)
        else:
            break
    # 아래 방향 영향 확인
    # down : index : r + 1 ~ n - 1
    for cr in range(r, n - 1):
        dd ^= 1
        if in_range(cr, cr + 1):
            simulate(cr + 1, dd)
        else:
            break

for row in board:
    print(*row)