Awesome

http://boj.kr/3190 

'뱀'은 머리가 붙었다가 꼬리가 떼졌다가 즉 앞뒤로 데이터를 넣었다가 뺐다가 해야 하는 이유로 deque를 사용했다.

board에서 뱀은 2, 사과는 1, 나머지는 0으로 표시했다.

move 리스트에 담은 L개의 방향 전환 정보는 '게임 시작 후 X초가 지난 후에 방향을 전환한다'는 뜻이다. 

time을 증가시켜가면서 매 초마다 move 안에 담긴 X초와 같은지 비교하고, 같으면 방향을 바꿨다. 

그리고 그렇게 방향을 전환했을 때마다 move 리스트의 인덱스를 가리키는 idx를 1씩 증가시켰다.

방향 전환이 끝나도 뱀은 계속해서 이동하므로 while True: 안에서 이동하도록 해 주었다.

import sys
from collections import deque


def Print(lst):
    for i in lst:
        for j in i:
            print(j, end=' ')
        print("")
    print("")


def get_next_direction(now, rotate):  # (현재 방향, 움직임 명령(L or D))
    if now == 0:
        if rotate == 'L':
            return 2
        else:
            return 3
    elif now == 1:
        if rotate == 'L':
            return 3
        else:
            return 2
    elif now == 2:
        if rotate == 'L':
            return 1
        else:
            return 0
    elif now == 3:
        if rotate == 'L':
            return 0
        else:
            return 1


def solve():
    time = 0
    idx = 0  # move의 인덱스
    direct = 0  # 초기 방향 -> (0)
    while True:
        time += 1
        next_r, next_c = snake[0][R] + dx[direct], snake[0][C] + dy[direct]

        if 0 <= next_r < N and 0 <= next_c < N:
            if board[next_r][next_c] == SNAKE:  # 몸에 부딪힘
                return time
            snake.appendleft([next_r, next_c])  # 새로운 머리
            if board[next_r][next_c] != APPLE:
                tail_r, tail_c = snake.pop()
                board[tail_r][tail_c] = 0
            board[next_r][next_c] = SNAKE
        else:  # 벽에 부딪힘
            return time

        if idx < L:
            if time == move[idx][0]:
                direct = get_next_direction(direct, move[idx][1])  # 현재 방향, 다음 회전 명령
                idx += 1
                

dx = (0, 0, -1, 1)
dy = (1, -1, 0, 0)

R, C = 0, 1
APPLE, SNAKE = 1, 2
input = sys.stdin.readline
N = int(input())

board = [[0 for _ in range(N)] for _ in range(N)]
board[0][0] = 2  # 처음에 뱀은 (0, 0)에 위치하고 있음
K = int(input())
for _ in range(K):
    i, j = map(int, input().split())
    board[i-1][j-1] = APPLE

L = int(input())  # 뱀의 방향 전환 정보

move = []
for _ in range(L):
    i, j = input().split()
    move.append([int(i), j])

snake = deque([[0, 0]])  # row, col
print(solve())

http://boj.kr/17837 

색깔을 저장할 color 배열

체스판 위의 말들을 표시할 board

말들의 상태를 관리할 horse

보통 이런 문제를 풀 때는 board판 위에 움직여야 할 아이템들의 정보를 저장하고 board를 탐색하곤 했는데,

이번에는 보드판 따로, 아이템들의 정보 따로 저장했다.

그 이유는 0번부터 K-1번의 말이 움직일 때 그 이전의 말이 움직임이 그 다음 말에 영향을 주도록 해야 하기 때문이다.

예를 들어 낚시왕 같은 문제의 경우 이전 상어가 움직였을 때의 결과를 다른 곳에 따로 저장해야 했다. 한 사이클 동안 모든 상어가 동시에 움직인다고 했기 때문이다.

하지만 이번 문제는 말들이 순서대로 움직인다고 했기 때문에 board를 그대로 사용하고, 

한 턴마다 0~K-1번의 말들을 움직이기 위해서 horse 리스트에 따로 말들의 정보를 저장했다.

일단 주의해야 할 점은 파란색이거나 벽으로 막혀서 후진해야 될 때도 그 후진하려는 곳이 빨간색인지 흰색인지 구분하고 그대로 실행해줘야 한다는 것이다.

그리고 양쪽다 파란색이거나 벽으로 막혀서 움직이지 않을 때도 일단 방향은 바꿔주어야 한다.

그렇게 한번 움직임이 막힌 말은 더이상 움직이지 않을거라고 생각했는데,

말이 움직일 때 '그 위에 있는 말들'이 같이 움직이는 경우가 있으므로 왼오로 움직이던 말이 아래쪽 말에 영향을 받아서 상하로 움직일 수가 있다. 사면초가를 벗어날 수 있다는 뜻이다.

import sys


def solve():
    four = False
    for t in range(1001):
        for num_horse in range(K):  # 0~K-1번의 말을 순서대로 이동시키는 것이 한 '턴'
            r, c, direct = horse[num_horse]
            next_r = r + dx[direct]
            next_c = c + dy[direct]
            idx = board[r][c].index(num_horse)  # 체스판에서의 말의 인덱스

            if 0 <= next_r < N and 0 <= next_c < N:
                if color[next_r][next_c] == WHITE:  # h 위에 있는 모든 말이 이동하고 그 위에 쌓는다
                    board[next_r][next_c].extend(board[r][c][idx:])  # 이동하려는 말+그 위에 있는 말들을 이동시킨다
                    for _ in range(idx, len(board[r][c])):  # 말들의 정보 horse 리스트를 업데이트하고, 원래 있던 위치에서 삭제
                        horse[board[r][c][-1]] = [next_r, next_c, horse[board[r][c][-1]][DIRECT]]
                        del board[r][c][-1]
                    if len(board[next_r][next_c]) >= 4:
                        four = True
                        break
                elif color[next_r][next_c] == RED:  # h 위에 있는 말의 순서를 모두 바꾼후 같이 이동하고 그 위에 쌓는다
                    board[next_r][next_c].extend(reversed(board[r][c][idx:]))
                    for _ in range(idx, len(board[r][c])):
                        horse[board[r][c][-1]] = [next_r, next_c, horse[board[r][c][-1]][DIRECT]]
                        del board[r][c][-1]
                    if len(board[next_r][next_c]) >= 4:
                        four = True
                        break
                elif color[next_r][next_c] == BLUE:  # 방향을 반대로 바꾸고 한 칸 이동한다
                    if direct == 1 or direct == 3:
                        next_d = direct + 1
                    elif direct == 2 or direct == 4:
                        next_d = direct - 1
                    next_r, next_c = r + dx[next_d], c + dy[next_d]
                    if 0 <= next_r < N and 0 <= next_c < N:
                        if color[next_r][next_c] != BLUE:
                            if color[next_r][next_c] == WHITE:
                                board[next_r][next_c].extend(board[r][c][idx:])
                            elif color[next_r][next_c] == RED:
                                board[next_r][next_c].extend(reversed(board[r][c][idx:]))

                            for i in range(idx, len(board[r][c])):
                                horse[board[r][c][-1]] = [next_r, next_c, horse[board[r][c][-1]][DIRECT]]
                                del board[r][c][-1]
                            horse[num_horse] = [next_r, next_c, next_d]

                            if len(board[next_r][next_c]) >= 4:
                                four = True
                                break
                    horse[num_horse][DIRECT] = next_d  # 이동했건 안했던 일단 방향은 바뀐다

            else:  # 칸을 벗어나려는 경우 파랑과 같이 처리한다
                if direct == 1 or direct == 3:
                    next_d = direct + 1
                elif direct == 2 or direct == 4:
                    next_d = direct - 1
                next_r, next_c = r + dx[next_d], c + dy[next_d]
                if color[next_r][next_c] != BLUE:
                    if color[next_r][next_c] == WHITE:
                        board[next_r][next_c].extend(board[r][c][idx:])
                    elif color[next_r][next_c] == RED:
                        board[next_r][next_c].extend(reversed(board[r][c][idx:]))

                    for i in range(idx, len(board[r][c])):
                        horse[board[r][c][-1]] = [next_r, next_c, horse[board[r][c][-1]][DIRECT]]
                        del board[r][c][-1]

                    if len(board[next_r][next_c]) >= 4:
                        four = True
                        break
                horse[num_horse][DIRECT] = next_d  # 이동했건 안했던 일단 방향은 바뀐다

        if four:
            return t + 1  # t = 0부터 시작이므로 +1해서 리턴
    return -1


dx = (0, 0, 0, -1, 1)
dy = (0, 1, -1, 0, 0)
R, C, DIRECT = 0, 1, 2
WHITE, RED, BLUE = 0, 1, 2
input = sys.stdin.readline
N, K = map(int, input().split())  # N=체스판의 크기,K=말의 개수
color = [list(map(int, input().split())) for _ in range(N)]  # 색깔판
board = [[[] for _ in range(N)] for _ in range(N)]  # 체스판 위에 올라가 있는 말들이 저장될 리스트
horse = []  # 0~K-1번의 말들의 정보가 저장되는 리스트. '0'~'K-1'번을 말들의 번호라고 한다.
for k in range(K):
    i, j, d = map(int, input().split())  # row, col, 방향
    board[i-1][j-1] = [k]  # k=말의 번호. 여러 말이 저장될 수 있으므로 리스트로 저장한다
    horse.append([i-1, j-1, d])  # [row, col, 방향 d]
print(solve())

http://boj.kr/17822 

1. 원판을 2차원 배열로 생각해서 같은 원에 있는 숫자들은 같은 행에 속한 숫자들이라고 생각하고, 위아래로 접한 숫자들은 같은 열에 속한 숫자들이라고 생각한다.

2. 문제에서 주어진 일련의 과정을 몇가지로 나눈다.

1) 기저사례를 확인한다. 원판에 수가 남아있는지 확인해서 남아있으면 더 진행하고, 남아있지 않으면 반복문을 종료한다.

원판에 숫자가 남아있는지 추적하기 위해 N * M = remain이라는 변수를 따로 두었다. 

2) 각 행을 회전시킨다. 회전을 쉽게 하기 위해서 각 원판의 자료형을 list가 아닌 deque로 두었다. deque을 시계방향으로 회전하려면 deque.rotate(k), 반시계방향으로 회전하려면 deque.rotate(-k) 하면 된다. 너무 쉽다.

너무 쉬워서 찜찜하면 temp 배열을 하나 새로 만들어서 직접 위치를 계산해서 옮겨주면 된다.

3) 2차원 배열을 순환하면서 각 원소마다 인접한 숫자가 있는지 확인하고, 있으면 그 숫자를 지울 것이라는 표시를 담은 erase 배열에 True라고 체크한다.

문제를 처음 풀었을 때는 지문에서 각 행렬마다 어떻게 비교해야되는지 예외 케이스까지 조건을 친절하게 알려줬으므로 그대로 따라서 if-elif 문으로 비교했다. 물론 그래도 된다. 

하지만 어떤 문제에서는 이 문제처럼 직접 비교 조건을 알려주지 않고 그냥 인접한 숫자끼리 비교하라고만 할 수도 있다. 그럴 때는 지문에서 알려준 것처럼 i=0일 때, i=N-1일 때, 0 < i < N-1, j=0일 때, j=M-1일때, 0 < j < M-1 일때로 나눠서 코딩하기보다는 BFS나 DFS 탐색 문제처럼 동서남북 방향의 원소와 비교해야 한다고 생각하고 코딩하는 편이 빠를 것 같다. 중첩 if문으로 코딩하면 중복된 코드가 많아져서 자료형이라도 수정해야 될 때 긴 시간을 소모해야 할 수도 있다.

나는 미로찾기 문제를 BFS나 DFS로 풀 때처럼 dx와 dy를 미리 선언해주었다. 하지만 동서남북 방향의 네 원소와 모두 비교할 필요는 없고, →방향과 ↓방향의 원소와만 비교해도 된다. 어차피 중복되기 때문이다. 주의해야 할 점이 col은 원형 리스트이므로, col과 아래쪽 방향 next_c를 비교하려고 할 때 next_c가 범위를 벗어나면 0으로 바꿔줘야 한다. 반면 row는 원형 리스트가 아니므로 범위를 벗어나면 무시하면 된다.

4) 3번에서 지울 숫자들을 다 표시했으면, 이번에는 그 erase 배열을 순환하면서 True라고 체크된 숫자들을 0으로 지우고, 지웠으면 다시 erase 배열을 반복문에서 사용하기 위해서 False로 돌려놓는다. 5)번을 수행하기 위해서 지운 숫자가 있음을 표시하는 bool 변수 once_erase를 True로 체크한다.

5) 지운 숫자가 있음을 표시하는 bool 변수 once_erase가 False면 평균을 구해서 평균보다 작은 숫자는 +1, 큰 숫자는 -1을 해 주었다.

import sys
from collections import deque


def solve():
    remain = N * M
    for x, direct, k in move:  # x=x의 배수인 원판을 회전,direct=시계(0),반시계(1),k=몇칸 회전하는지
        if remain <= 0:  # 남아 있는 숫자가 없으면 반복문을 빠져나온 후 sum을 리턴
            break

        # x의 배수인 원판(행)을 모두 구해서 회전시킨다.
        if direct == 0:  # 시계방향
            for next_x in range(1, N+1):  # next_x = x의 배수인 원판(=행)
                if next_x % x == 0:
                    circle[next_x-1].rotate(k)
        else:  # 반시계방향
            for next_x in range(1, N+1):
                if next_x % x == 0:
                    circle[next_x-1].rotate(-k)

        # 인접한 것이 있는지 찾고, 있으면 지운다
        for row in range(N):
            for col in range(M):
                if circle[row][col]:  # 이미 지운 숫자는 보지 않는다
                    for i in range(2):  # 오른쪽, 아래쪽과 비교
                        next_r, next_c = row + dx[i], col + dy[i]
                        if next_c > M-1:  # col이 맨 끝에 도달했을 때는 next_c를 0으로 설정한다.
                            next_c = 0

                        if next_r < N:  # r은 범위를 벗어나면 그냥 무시한다
                            if circle[next_r][next_c] == circle[row][col]:
                                erase[next_r][next_c], erase[row][col] = True, True

        once_erased = False  # 지운 숫자가 있음을 체크할 bool 변수
        for row in range(N):
            for col in range(M):
                if erase[row][col]:  # 인접한 숫자가 있는 원소 (erase가 True로 체크된 원소)
                    once_erased = True
                    circle[row][col] = 0
                    remain -= 1  # 숫자를 지웠으니 남은 숫자를 의미하는 remain에서 1을 빼준다
                    erase[row][col] = False  # 다음 반복문에서 재사용하기 위해 다시 False로 돌려놓음

        # 지울 숫자가 없으면 평균을 구하고 평균보다 크면 -1, 작으면 +1
        if not once_erased:
            s = sum([sum(row) for row in circle]) / remain
            for row in range(N):
                for col in range(M):
                    if circle[row][col] > s:
                        circle[row][col] -= 1
                    elif 0 < circle[row][col] < s:
                        circle[row][col] += 1

    # 원판의 합을 리턴
    return sum([sum(row) for row in circle])


dx = (0, 1)
dy = (1, 0)
input = sys.stdin.readline
N, M, T = map(int, input().split())  # N=원판의 갯수,M=원판에 적혀있는 수의 갯수,T=회전수
circle = [deque(map(int, input().split()))for _ in range(N)]
erase = [[False for _ in range(M)] for _ in range(N)]  # 지울 숫자임을 표시하는 bool 배열
move = [list(map(int, input().split())) for _ in range(T)]
print(solve())

http://boj.kr/17140 

import sys
from operator import itemgetter


def solve(A, row_num, col_num):
    for t in range(101):  # t=100까지 반복
        transpose = False  # 행렬 뒤집기
        
        if 0 <= R-1 < row_num and 0 <= C-1 < col_num and A[R-1][C-1] == K:
            return t

        if row_num > 100:  # 100이 넘어가는 경우 앞의 100까지만 본다. 
            row_num = 100  # 이 코드에서는 range를 쓰므로 슬라이싱 없이 row, col의 길이만 손봐주면 된다.
        if col_num > 100:
            col_num = 100

        if row_num < col_num:  # 행 < 열의 경우 행렬을 뒤집어 C 연산을 수행해야 한다.
            transpose = True   # Flag를 설정하고 연산 이후 뒤집은 행렬을 다시 뒤집는다.
            A = list(zip(*A))
            row_num, col_num = col_num, row_num  # 행렬을 뒤집으면 row, col의 숫자도 바뀜

        maxLine = 0  # 가장 긴 줄을 저장하고 여기에 맞춰서 0을 추가하기 위함
        
        for r in range(row_num):
            search = {}
            for c in range(col_num):
                if A[r][c] != 0 and A[r][c] not in search:
                    search[A[r][c]] = A[r].count(A[r][c])
            search = sorted(search.items(), key=itemgetter(1, 0))  # 빈도수, 숫자크기 순으로 정렬
            
            A[r] = []  # sorted로 나온 [(), (), ()]를 한 리스트에 합침
            for key, val in search:
                A[r].extend([key, val])

            maxLine = max(maxLine, len(A[r]))

        for r in range(row_num):  # maxLine만큼 0으로 채우기
            l = len(A[r])
            if l < maxLine:
                A[r].extend([0] * (maxLine-l))

        if transpose:  # C 연산의 경우 다시 행렬을 되돌림
            A = list(zip(*A))
        row_num, col_num = len(A), len(A[0])
        
    return -1


input = sys.stdin.readline
R, C, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(3)]
print(solve(A, 3, 3))

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl&

def calc(dict):
    total = 0
    for rc, val in dict.items():
        total += val[NUM]
    return total


def solve():
    global virus
    for _ in range(M):  # M 시간 뒤의 결과를 구해야 함
        new = {}  # 이동을 마친 바이러스를 넣을 딕셔너리

        # 이동
        for rc, val in virus.items():
            num, direct, _ = val
            next_row = rc[0] + dx[direct-1]
            next_col = rc[1] + dy[direct-1]
            if next_row == 0 or next_row == N-1 or next_col == 0 or next_col == N-1:
                if direct == 1:
                    direct = 2
                elif direct == 2:
                    direct = 1
                elif direct == 3:
                    direct = 4
                elif direct == 4:
                    direct = 3
                num = num // 2
                
                if num == 0:
                    continue

            if (next_row, next_col) not in new:
                new[(next_row, next_col)] = [num, direct, num]
            else:
                if num > new[(next_row, next_col)][MAX]:  # 맥스 num보다 크면 direct를 교체
                    new[(next_row, next_col)][DIRECT] = direct
                    new[(next_row, next_col)][MAX] = num  # max 교체
                new[(next_row, next_col)][NUM] += num

        virus = new
    return calc(virus)


NUM, DIRECT, MAX = 0, 1, 2
T = int(input())
dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)
for i in range(T):
    N, M, K = map(int, input().split())  # 격자의 크기 N, 시간 M, 군집의 갯수 K
    virus = {}
    for _ in range(K):
        x, y, n, d = map(int, input().split())  # 가로, 세로, 군집크기, 방향
        virus[(x, y)] = [n, d, n]  # 군집 크기, 방향, max(같은 셀에 모인 군집 중 가장 큰 크기. 현재는 자기 뿐이므로 자기 자신의 크기 n)

    print("#{} {}".format(i+1, solve()))

http://boj.kr/17144

모든 미세먼지가 '동시에' 확산한다고 해서 BFS인가 했더니만 그냥 배열 크기만큼 돌면서 시뮬레이션해주는 문제였다.

RxC을 돌며 4방향 확산->공기청정기의 순환->RxC을 돌며 4방향 확산->공기청정기의 순환

이 과정을 T만큼 반복해야 한다.

주의해야 할 점은 모든 미세먼지는 동시에 확산된다는 점이다.

즉, 한 번의 로테이션 동안에는 서로 영향을 줘서는 안된다.

주변으로 확산될 미세먼지를 주변에 바로 더하면 안되고 따로 저장해둔 뒤에, 한꺼번에 확산시켜야 된다는 것이다.

(r, c)에서 미세먼지가 확산되버리면 다음 반복문인 (r, c+1)의 미세먼지 양을 계산할 때 영향을 주기 때문이다. 

나는 room[R][C] = [현재 미세먼지, 다음번에 주변으로 확산될 미세먼지] 로 저장했다. 

일단 한번 RxC를 돌면서 현재 미세먼지를 전부 계산한 후에, 다시한번 처음부터 RxC를 돌면서 저장된 미세먼지를 주변으로 확산시켰다.

공기청정기로 인한 미세먼지의 이동은 BFS 때처럼 배열을 만들어놓고 range로 총 4번 방향을 꺾게 하는 방법,

아니면 직접 총 8번의 for문으로 구역을 나누어서 이동시키는 방법이 있다.

나는 전자의 방법으로 처음에 시도했는데 하다보니 헷갈려서 시간을 너무 오래 썼다.

보다 간단하고 디버깅도 구역별로 나눠서 가능한 후자가 더 나을 것 같다.

(코드 내에서 전자의 방법은 air_fresh_upside & air_fresh_downside 함수이고

후자의 방법은 73-83번 줄의 for문이다. 윗부분만 for문으로 했기 때문에 4줄이다.)

전자이든 후자이든, 중요한 것은 공기청정기에 들어온 미세먼지는 사라진다는 것인데,

이것은 바꿔말하면 공기청정기 다음 위치(문제에서 보면 col + 1 한 곳)에 0이 들어온다는 뜻이 된다.

하지만 헷갈려서 공기청정기 이전 위치를 0으로 바꾼다던가 공기청정기를 다시 -1로 돌려놓지 않는다던가 하는 일이 발생하게 된다...

import sys


def Print(lst):
    for i in lst:
        for j in i:
            print(j[0], end=' ')
        print("")
    print("")


def air_fresh_upside(r, c):
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    for d in range(4):
        while True:
            if 0 <= r + dx[d] <= head_loc[0] and 0 <= c + dy[d] < C:
                if room[r+dx[d]][c+dy[d]][0] == -1:
                    room[r][c][0] = 0
                    break
                else:
                    room[r][c][0] = room[r+dx[d]][c+dy[d]][0]
                r += dx[d]
                c += dy[d]
            else:
                break
    room[head_loc[0]][head_loc[1]][0] = -1


def air_fresh_downside(r, c):
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    for d in range(4):
        while True:
            if tail_loc[0] <= r + dx[d] < R and 0 <= c + dy[d] < C:
                if room[r+dx[d]][c+dy[d]][0] == -1:
                    room[r][c][0] = 0
                    break
                else:
                    room[r][c][0] = room[r + dx[d]][c + dy[d]][0]
                r += dx[d]
                c += dy[d]
            else:
                break
    room[tail_loc[0]][tail_loc[1]][0] = -1


def solve():
    for _ in range(T):
        for r in range(R):
            for c in range(C):
                if room[r][c][0] >= 5:  # 미세먼지가 5 이상이면 확산함
                    dust_num = 0
                    for dr, dc in [[0, 1], [0, -1], [1, 0], [-1, 0]]:  # 상하좌우
                        if 0 <= r + dr < R and 0 <= c + dc < C:  # room 범위 내에서 &
                            if room[r+dr][c+dc][0] != -1:  # 공기청정기 영역이 아니라면 확산
                                dust_num += 1
                                room[r+dr][c+dc][1] += room[r][c][0] // 5
                    room[r][c][0] = room[r][c][0] - (room[r][c][0]//5) * dust_num

        # 확산된 미세먼지(room[r][c][1])를 기존 미세먼지에(room[r][c][0]) 합친다
        for r in range(R):
            for c in range(C):
                room[r][c][0] += room[r][c][1]
                room[r][c][1] = 0

        # 미세먼지의 이동 (방법 1)
        #air_fresh_upside(head_loc[0]-1, head_loc[1])
        air_fresh_downside(tail_loc[0]+1, tail_loc[1])

        # 미세먼지 이동 (방법 2)
        for i in range(0, C-1):
            room[0][i][0] = room[0][i+1][0]
        for i in range(0, head_loc[0]+1):
            room[i][C-1][0] = room[i+1][C-1][0]
        for i in range(0, C-1):
            room[head_loc[0]][C-1-i][0] = room[head_loc[0]][C-2-i][0]
        for i in range(0, head_loc[0]):
            room[head_loc[0]-i][0][0] = room[head_loc[0]-1-i][0][0]
        room[head_loc[0]][head_loc[1]+1][0] = 0
        room[head_loc[0]][head_loc[1]][0] = -1

        #Print(room)

    # sum
    ret = 0
    for r in range(R):
        for c in range(C):
            ret += room[r][c][0]
    return ret + 2


input = sys.stdin.readline
R, C, T = map(int, input().split())
room = [list(map(int, input().split())) for _ in range(R)]
head_loc, tail_loc = [], []  # 공기청정기 윗부분. 아랫부분 위치

for i in range(R):
    for j in range(C):
        if room[i][j] == -1:
            if head_loc:
                tail_loc = [i, j]
            else:
                head_loc = [i, j]
        room[i][j] = [room[i][j], 0]  # [현재 미세먼지, 다음에 확산되서 합쳐질 미세먼지]

print(solve())

http://boj.kr/16235 

각 계절별로 아래와 같은 행위를 정의한 다음 함수로 만들고 k년마다 실행하면 된다.

봄: 각 칸에 있는 나무들이 양분을 섭취하거나 죽은 나무 리스트에 추가된다.

여름: 죽은 나무들이 그 나이의 절반만큼 양분으로 추가된다.

가을: 어떤 나무의 나이가 5의 배수라면, 인접한 8칸에 1의 나이를 가진 나무들이 추가된다.

겨울: 모든 나무들에게 각기 주어진 만큼의 양분을 추가한다.

각 계절별로 따로 함수를 만들어도 되지만 가을, 겨울은 서로 영향을 주지 않기 때문에 하나의 반복문 내에서 실행되도록 했다.

53번줄처럼 밭을 board[N][N]으로,

1x1 크기의 각 칸은 [양분, [그 칸에 있는 나무들의 나이], 죽은 나무 나이/2, 나무의 숫자]로 정해주었고 

각 칸의 인덱스를 0~3으로 접근하면 헷갈리기 때문에 MEAL, TREE, DEAD, NUM = 0, 1, 2, 3으로 define해주었다.

nutrition이 아니라 meal인 이유는 nutrition은 너무 길기 때문에...

위에서 설명한 것처럼 board 배열을 3차원으로 초기화하려면 주의해야할 것이 있다.

보통 2차원 배열을 초기화할 때 [0] * N for _ in range(N) 이라는 방법을 쓴다.

나는 여기서 [0]  ->  [양분, [그 칸에 있는 나무들의 나이], 죽은 나무 나이/2, 나무의 숫자] 라고 생각해서

단순히  [[[양분, [그 칸에 있는 나무들의 나이], 죽은 나무 나이/2, 나무의 숫자]] * N for _ in range(N)] for _ in range(N)]이라고 해주었었다. 문제가 되는 부분은 볼드처리 된 부분으로, 저것은 배열이기 때문에 * N 으로 만들면 안 된다! 저렇게 하면 하나의 배열 객체가 만들어진후에 N 개만큼 자가증식한다. 하나가 바뀌면 N 개의 형제들이 모두 값이 바뀌게 된다. shallow copy인 셈이다.

파이썬은 1.3초의 시간을 주긴 하지만, 기본적으로 0.3초의 시간 밖에 주지 않아서 시간을 최대한 줄이기 위해 deque를 썼다. 작은 나무 먼저 양분을 먹는다고 했으므로, 우선 입력을 받은 후에 나무 배열을 sort()로 정렬한다. 

그 이후에 나무들을 차례대로 보면서 양분을 먹이거나 죽이거나 하는 과정은 

28번줄에서 popleft로 맨 앞에 있는 가장 어린 나무를 꺼낸 후 

31번째줄에서 맨 뒤에 다시 추가시켜 주는 식으로 반복했다. 이것을 나무의 갯수(NUM)만큼 진행하면 된다.

매번 새로 정렬해야했다면 spring()에서만 시간이 2배로 걸렸을 것이다.

import sys
from collections import deque


def fall_and_winter():
    for i in range(N):
        for j in range(N):
            for t in board[i][j][TREE]:
                if t % 5 == 0:
                    for d in range(8):
                        if 0 <= i + dx[d] < N and 0 <= j + dy[d] < N:
                            board[i+dx[d]][j+dy[d]][TREE].appendleft(1)
                            board[i+dx[d]][j+dy[d]][NUM] += 1
            board[i][j][MEAL] += new_meal[i][j]


def summer():
    for i in range(N):
        for j in range(N):
            board[i][j][MEAL] += board[i][j][DEAD]
            board[i][j][DEAD] = 0


def spring():
    for i in range(N):
        for j in range(N):
            for _ in range(board[i][j][NUM]):
                tree_year = board[i][j][TREE].popleft()
                if tree_year <= board[i][j][MEAL]:  # 작거나 같으면 양분 섭취 가능
                    board[i][j][MEAL] -= tree_year  # 나이만큼 양분 빼기
                    board[i][j][TREE].append((tree_year+1))
                else:  # dead
                    board[i][j][DEAD] += tree_year // 2
                    board[i][j][NUM] -= 1


def solve():
    for k in range(K):
        spring()
        summer()
        fall_and_winter()

    ret = 0
    for i in range(N):
        for j in range(N):
            ret += board[i][j][NUM]
    return ret


MEAL, TREE, DEAD, NUM = 0, 1, 2, 3
input = sys.stdin.readline
N, M, K = map(int, input().split())
board = [[[5, [], 0, 0] for _ in range(N)] for _ in range(N)]  # meal, trees(ages), num, dead
new_meal = [list(map(int, input().split())) for _ in range(N)]

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

for _ in range(M):
    x, y, z = map(int, input().split())
    board[x-1][y-1][TREE].append(z)  # tree 추가

for i in range(N):
    for j in range(N):
        board[i][j][TREE] = deque(sorted(board[i][j][TREE]))
        board[i][j][NUM] = len(board[i][j][TREE])

print(solve())

http://boj.kr/15685 

규칙을 찾아내면 되는 문제이다.

(x, y) 증가량으로 규칙을 찾아내려고 하면 눈에 잘 보이지 않는다.

문제에서 제시한 

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

를 사용한다.

0세대에서부터 K세대까지 직접 그려보는데,

새로 생겨난 변의 번호를 직접 써보면 규칙이 보인다.

K세대 드래곤 커브의 각 선분 정보를 담은 리스트를 directions 라고 하면,

K+1세대 드래곤 커브의 것은 directions을 역순으로 하고 (x+1)%4 한 것이다.

import sys


# 네 꼭짓점이 모두 드래곤 커브인 정사각형 갯수 구하기
def calc():
    ret = 0
    for i in range(SZ):
        for j in range(SZ):
            if j < SZ - 1 and i < SZ - 1:
                if board[i][j] and board[i + 1][j] and board[i][j + 1] and board[i + 1][j + 1]:
                    ret += 1
    return ret


def draw(x, y, d, generation):
    # draw 0st dragon
    directions = [d]
    board[x][y] = 1
    x += dx[d]
    y += dy[d]
    board[x][y] = 1

	# draw Kst dragons
    for g in range(1, generation + 1):
        tmp = []  # 이번 세대에 새로 생긴 선분들의 방향
        for d in reversed(directions):  # 역순
            d = (d + 1) % 4
            tmp.extend([d])
            x += dx[d]
            y += dy[d]
            board[x][y] = 1
        directions.extend(tmp)  # directions 업데이트


SZ = 101  # 전체 좌표의 크기. 0 <= x, y <= 100 이므로 크기는 101이 되어야 함
input = sys.stdin.readline
N = int(input())
all_curves = [list(map(int, input().split())) for _ in range(N)]
board = [[0] * SZ for _ in range(SZ)]
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

for x, y, d, g in all_curves:  
    draw(y, x, d, g)  
    # 문제에서의 (x, y) = (col, row)이므로 여기서만 거꾸로 전달하고
    # 나머지 보드 위에서의 움직임은 원래 하던 row, col으로 하면 된다.

print(calc())