🎇 감시 문제 Code

import copy
n, m = map(int, input().split())
cctv = []
graph = []

# TODO 1. Index 설정 방법 
'''
mode 배열로 만들어서 하나의 Element(List) 안에 방향을 넣음
이를 돌려가면서 회전 시킴
'''

mode = [
    [],
    [[0], [1], [2], [3]],
    [[0, 2], [1, 3]],
    [[0, 1], [1, 2], [2, 3], [0, 3]],
    [[0, 1, 2], [0, 1, 3], [1, 2, 3], [0, 2, 3]],
    [[0, 1, 2, 3]],
]

# 북 - 동 - 남 - 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

for i in range(n):
    data = list(map(int, input().split()))
    graph.append(data)
    for j in range(m):
        if data[j] in [1, 2, 3, 4, 5]:
            cctv.append([data[j], i, j])

'''
While True -> break 걸면서 for 문 1,2,3,4 번 도는 구문
확실히 감이 많이 떨어지긴했다
'''

def fill(board, mm, x, y):
    for i in mm:
        nx = x
        ny = y
        while True:
            nx += dx[i]
            ny += dy[i]
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                break
            if board[nx][ny] == 6:
                break
            elif board[nx][ny] == 0:
                board[nx][ny] = 7

'''
한 번 CCTV 처리할 때 마다, 배열 Copy
'''
def dfs(depth, arr):
    global min_value

    if depth == len(cctv):
        count = sum(arr[i].count(0) for i in range(n))
        min_value = min(min_value, count)
        return
    temp = copy.deepcopy(arr)
    cctv_num, x, y = cctv[depth]
    for i in mode[cctv_num]:
        fill(temp, i, x, y)
        dfs(depth+1, temp)
        # temp가 바뀌기 때문에 다시 setting
        temp = copy.deepcopy(arr)


min_value = int(1e9)
dfs(0, graph)
print(min_value)

깨달은 점

DFS Input 인자에 리스트가 들어갔다가 나올 때 어떻게 복귀 시키나 했는데, copy.deepcopy 활용해서 다시 setting 해주는 식으로 해주는 것 이였다

• 콜바밸 콜바레 개념 공부

https://aalphaca.tistory.com/4 : 블로그 참조

• 무작정 어떤 BFS, DFS 등과 같은 알고리즘을 탐색하는게 아니라, 그것의 근간이 되는 스택과 큐의 개념을 먼저 떠올리기

🎇 드래곤커브 문제 Code

n = int(input())

dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]

# 드래곤 커브들이 모일 배열 1이면 드래곤 커브의 일부
arr = [[0] * 101 for _ in range(101)]

for _ in range(n):
    # x, y : 드래곤 커브 시작점, d : 시작 방향, g : 세대
    x, y, d, g = map(int, input().split())
    arr[x][y] = 1

    move = [d]
    # g 세대 만큼 반복
    for _ in range(g):
        tmp = []
        for i in range(len(move)):
            tmp.append((move[-i - 1] + 1) % 4)
        move.extend(tmp)

    # 드래곤 커브에 해당하는 좌표 arr에 추가
    for i in move:
        nx = x + dx[i]
        ny = y + dy[i]
        arr[nx][ny] = 1
        x, y = nx, ny

# 모든 꼭짓점이 드래곤 커브의 일부인 정사각형 개수 구하기
ans = 0
for i in range(100):
    for j in range(100):
        if arr[i][j] and arr[i + 1][j] and arr[i][j + 1] and arr[i + 1][j + 1]:
            ans += 1

print(ans)

깨달은 점

방향성 규칙 잘 못 찾아서 답을 틀림 -> 규칙성을 찾아야 했는데, 방향 변경에만 신경을 써서 틀림
방향 변경 하면서 이걸로 안되는 걸 알아야 했는데,,음 대충 한 두개 해보니 맞아서 이거인 줄 알았나봄
규칙성 찾기 문제임

핵심 Code

tmp.append((move[-i - 1] + 1) % 4)
move[-i - 1] + 1 -> (뒤집기 ->  규칙성1) + (+1 -> 규칙성2)

방향성에 대해서 드래곤 커브 0, 1, 2 세대 늘렸을 때 어떤지 기록하고,
이에 대해 앞에서부터 또는 뒤에서부터 규칙이 있는지 파악 !!

🎇 미세먼지 안녕 !

import sys

input = sys.stdin.readline

r, c, t = map(int, input().split())

arr = [list(map(int, input().split())) for _ in range(r)]

up = -1
down = -1
# 공기 청정기 위치 찾기
for i in range(r):
    if arr[i][0] == -1:
        up = i
        down = i + 1
        break

# 미세먼지 확산
def spread():
    dx = [-1, 0, 0, 1]
    dy = [0, -1, 1, 0]

    tmp_arr = [[0] * c for _ in range(r)]
    for i in range(r):
        for j in range(c):
            if arr[i][j] != 0 and arr[i][j] != -1:
                tmp = 0
                for k in range(4):
                    nx = dx[k] + i
                    ny = dy[k] + j
                    if 0 <= nx < r and 0 <= ny < c and arr[nx][ny] != -1:
                        tmp_arr[nx][ny] += arr[i][j] // 5
                        tmp += arr[i][j] // 5
                arr[i][j] -= tmp

    for i in range(r):
        for j in range(c):
            arr[i][j] += tmp_arr[i][j]

# 공기청정기 위쪽 이동
def air_up():
    dx = [0, -1, 0, 1]
    dy = [1, 0, -1, 0]
    direct = 0
    before = 0
    x, y = up, 1
    
    while True:
        nx = x + dx[direct]
        ny = y + dy[direct]
        if x == up and y == 0:
            break
        if nx < 0 or nx >= r or ny < 0 or ny >= c:
            direct += 1
            continue
        arr[x][y], before = before, arr[x][y]
        x = nx
        y = ny

# 공기청정기 아래쪽 이동
def air_down():
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    direct = 0
    before = 0
    x, y = down, 1
    
    while True:
        nx = x + dx[direct]
        ny = y + dy[direct]
        # 종료 조건
        if x == down and y == 0:
            break
        # 방향 변환 조건
        if nx < 0 or nx >= r or ny < 0 or ny >= c:
            direct += 1
            continue
        arr[x][y], before = before, arr[x][y]
        x = nx
        y = ny

# 작동 !
for _ in range(t):
    spread()
    air_up()
    air_down()

# 이건 sum 써먹는게 더 효율적
answer = 0
for i in range(r):
    for j in range(c):
        if arr[i][j] > 0:
            answer += arr[i][j]

print(answer)

깨달은 점

1. "공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다." -> 문제 좀 제대로 읽자 ..!
2. 그리고 "확산" -> 이건..음 문제 예시를 보면서 파악했어야 했는데, 놓침..
3. 🌟 이게 핵심 ! 하...이 놈의 회전, 방향 전환 등등 진짜.. 특히 이놈은 만나봤는데 그 당시 제대로 정리 안해서 틀렸다. 이 문제 계기로 진짜 확실히 매번 정리해야겠다 그때 이해한다고 써먹을 수 있는게 아니다!
   < 종료 조건, 방향 전환 조건, while True >
   특정 방향으로 쭈욱 나오면 걍 -> while True 이용 ( 이 패턴 자주나옴 !!)

핵심 CODE

arr[x][y], before = before, arr[x][y]

위 코드가 진짜 중요한 LOGIC
4방향을 한 번에 진행하면서 이전 거를 미리 저장해두고, 이를 다음에 적용하는 방법을 생각못함..