Coding 공부

n1,n2,n3,n4,n5,n6,n7,n8,n9,n10,n11= map(int,input().split())

arr = [[[[[[[[[[list(map(int,input().split())) for _ in range(n2)] for _ in range(n3)] for _ in range(n4)] for _ in range(n5)] for _ in range(n6)] for _ in range(n7)] for _ in range(n8)] for _ in range(n9)] for _ in range(n10)] for _ in range(n11)]


tomato_cnt = 0
total = n1*n2*n3*n4*n5*n6*n7*n8*n9*n10*n11
tomato = []
for A in range(n11):
    for B in range(n10):
        for C in range(n9):
            for D in range(n8):
                for E in range(n7):
                    for F in range(n6):
                        for G in range(n5):
                            for H in range(n4):
                                for I in range(n3):
                                    for J in range(n2):
                                        for K in range(n1):
                                            if arr[A][B][C][D][E][F][G][H][I][J][K] == 1:
                                                tomato.append((A,B,C,D,E,F,G,H,I,J,K))


dK = [-1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
dJ = [0,0,-1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
dI = [0,0,0,0,-1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
dH = [0,0,0,0,0,0,-1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
dG = [0,0,0,0,0,0,0,0,-1,1,0,0,0,0,0,0,0,0,0,0,0,0]
dF = [0,0,0,0,0,0,0,0,0,0,-1,1,0,0,0,0,0,0,0,0,0,0]
dE = [0,0,0,0,0,0,0,0,0,0,0,0,-1,1,0,0,0,0,0,0,0,0]
dD = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,1,0,0,0,0,0,0]
dC = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,1,0,0,0,0]
dB = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,1,0,0]
dA = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,1]

day = 0
result = 0
while True:
    new_tomato = []
    for A,B,C,D,E,F,G,H,I,J,K in tomato:
        for l in range(22):
            nA = A + dA[l]
            nB = B + dB[l]
            nC = C + dC[l]
            nD = D + dD[l]
            nE = E + dE[l]
            nF = F + dF[l]
            nG = G + dG[l]
            nH = H + dH[l]
            nI = I + dI[l]
            nJ = J + dJ[l]
            nK = K + dK[l]
            if 0<=nA<n11 and 0<=nB<n10 and 0<=nC<n9 and 0<=nD<n8 and 0<=nE<n7 and 0<=nF<n6 and 0<=nG<n5 and 0<=nH<n4 and 0<=nI<n3 and 0<=nJ<n2 and 0<=nK<n1:
                if not arr[nA][nB][nC][nD][nE][nF][nG][nH][nI][nJ][nK]:
                    arr[nA][nB][nC][nD][nE][nF][nG][nH][nI][nJ][nK] = 1
                    new_tomato.append((nA,nB,nC,nD,nE,nF,nG,nH,nI,nJ,nK))

    if len(new_tomato):
        tomato = new_tomato[:]
        day += 1
    else:
        result = day
        for A in range(n11):
            for B in range(n10):
                for C in range(n9):
                    for D in range(n8):
                        for E in range(n7):
                            for F in range(n6):
                                for G in range(n5):
                                    for H in range(n4):
                                        for I in range(n3):
                                            for J in range(n2):
                                                for K in range(n1):
                                                    if arr[A][B][C][D][E][F][G][H][I][J][K] == 0:
                                                        result = -1
        break

print(result)
        

def check(x,y,size):
    for nx in range(x,x+size):
        for ny in range(y,y+size):
            if result[nx][ny] != 0:
                return False
    return True


def divide_and_fill(x,y,size):
    global numbers
    numbers += 1
    next_size = size//2
    input_position = [[x+next_size-1,y+next_size-1],[x+next_size,y+next_size-1],[x+next_size-1,y+next_size],[x+next_size,y+next_size]]
    for ind,val in enumerate([[x,y],[x+next_size,y],[x,y+next_size],[x+next_size,y+next_size]]):
        sx,sy = val
        input_x,input_y = input_position[ind]
        if check(sx,sy,next_size):
            result[input_x][input_y] = numbers

    if size == 2:
        return
    divide_and_fill(x,y,next_size)
    divide_and_fill(x+next_size,y,next_size)
    divide_and_fill(x,y+next_size,next_size)
    divide_and_fill(x+next_size,y+next_size,next_size)




k= int(input())
N = 2**k
input_x,input_y = map(int,input().split())
x = N-input_y
y = input_x-1
result = [[0 for _ in range(N)] for _ in range(N)]
result[x][y] = -1

numbers = 0
divide_and_fill(0,0,N)
for row in result:
    print(*row)

from collections import deque

def roll(direction,red,blue):
    global arr,visited
    stack = deque()
    red = [*red,True]
    blue = [*blue,True]
    stack.append((red,blue))
    while stack:
        r,b = stack.popleft()

        r_x,r_y,r_state = r
        b_x,b_y,b_state = b
        visited[r_x][r_y] = False
        if r_state:
            nr_x = r_x + dx[direction]
            nr_y = r_y + dy[direction]
            if 0<=nr_x<N and 0<=nr_y<M:
                if nr_x == b_x and nr_y == b_y:
                    if not b_state:
                        r_state = False
                else:
                    if arr[nr_x][nr_y] == '#':
                        r_state = False
                    elif arr[nr_x][nr_y] == 'O':
                        r_state = False
                        r_x = -1
                        r_y = -1
                    else:
                        r_x = nr_x
                        r_y = nr_y
        if b_state:
            nb_x = b_x + dx[direction]
            nb_y = b_y + dy[direction]
            if 0<=nb_x<N and 0<=nb_y<M:
                if nb_x == r_x and nb_y == r_y:
                    if not r_state:
                        b_state = False
                else:
                    if arr[nb_x][nb_y] == '#':
                        b_state = False
                    elif arr[nb_x][nb_y] == 'O':
                        b_state = False
                        b_x = -1
                        b_y = -1
                    else:
                        b_x = nb_x
                        b_y = nb_y
        
        if not r_state and not b_state:
            if b_x == -1:
                return -1
            if r_x == -1:
                return 1
            return [r_x,r_y,b_x,b_y]
        
        stack.append(([r_x,r_y,r_state],[b_x,b_y,b_state]))


def bfs(r,b,g):
    global arr
    stack = deque()
    stack.append((r,b,0))
    visited[r[0]][r[1]] = False
    while stack:
        red,blue,cnt = stack.popleft()
        if cnt >= 10:
            return -1
        for i in range(4):
            nx = red[0] + dx[i]
            ny = red[1] + dy[i]
            if 0<=nx<N and 0<=ny<M:
                result = roll(i,red,blue)
                if type(result) == int:
                    if result == 1:
                        return cnt+1
                else:
                    nr = [result[0],result[1]]
                    nb = [result[2],result[3]]
                    stack.append((nr,nb,cnt+1))
    return -1
dx = [-1,1,0,0]
dy = [0,0,-1,1]


N,M = map(int,input().split())

arr = []
red_ball = []
blue_ball = []
goal = []
visited = [[True]*M for _ in range(N)]
for x in range(N):
    temp = list(input())

    for y in range(M):
        if temp[y] == 'R':
            temp[y] = '.'
            red_ball = [x,y]
        elif temp[y] == 'B':
            temp[y] = '.'
            blue_ball = [x,y]
        elif temp[y] == 'O':
            goal = [x,y]
    arr.append(temp)
print(bfs(red_ball,blue_ball,goal))

string = input()
duck = 'quack'
cnt = 0
result = []
answer = 0
for st in string:
    flag = True
    for ind in range(len(result)):
        if duck[(duck.index(result[ind][-1])+1)%5] == st:
            result[ind].append(st)
            flag = False
            break

    if flag:
        if st != 'q':
            answer = -1
            break
        result.append([st])

if answer == -1:
    print(answer)
else:
    for i in result:
        if len(i)%5 != 0:
            print(-1)
            break
    else:
        print(len(result))

    

S = input()

duck = {'q':0,'u':1,'a':2,'c':3,'k':4}

queue = []
answer = 0
for sound in S:
    flag = True
    for ind in range(len(queue)):
        if (queue[ind] + 1)%5 == duck[sound]:
            queue[ind] = (queue[ind] + 1)%5
            flag = False
            break
    if flag:
        if duck[sound] != 0:
            answer = -1
            break
        queue.append(0)


if answer == -1:
    print(-1)
else:
    for num in queue:
        if num != 4:
            print(-1)
            break
    else:
        print(len(queue))

from collections import Counter

def move_robot(mad_ro,ro):
    new_robot = []

    for mad_x,mad_y in mad_ro:
        ro_distance = float('inf')
        ro_direction = -1
        for i in range(9):
            mad_nx = mad_x + dx[i]
            mad_ny = mad_y + dy[i]
            if 0<= mad_nx < R and 0<= mad_ny <C:
                distance = abs(mad_nx - ro[0]) + abs(mad_ny-ro[1])
                if ro_distance > distance:
                    ro_distance = distance
                    ro_direction = i

        new_x = mad_x + dx[ro_direction]
        new_y = mad_y + dy[ro_direction]
        new_robot.append((new_x,new_y))

    return new_robot
    
def bomb_robot(mad_ro):
    count_mad_ro = Counter(mad_ro)
    new_mad_ro = set()
    for key,value in count_mad_ro.items():
        if value == 1:
            new_mad_ro.add(key)
    return new_mad_ro




R,C = map(int,input().split())

arr = [list(input()) for _ in range(R)]

mad_robots = set()
robot = (0,0)
for i in range(R):
    for j in range(C):
        if arr[i][j] == 'R':
            mad_robots.add((i,j))
            arr[i][j] = '.'
        elif arr[i][j] == 'I':
            robot = (i,j)
            arr[i][j] = '.'

command = list(map(lambda x : x-1, map(int,list(input()))))
dx = [1,1,1,0,0,0,-1,-1,-1]
dy = [-1,0,1,-1,0,1,-1,0,1]
flag = False
answer = 0
for time in range(len(command)):
    x,y = robot
    nx = x + dx[command[time]]
    ny = y + dy[command[time]]
    if (nx,ny) in mad_robots:
        flag =  True
        answer = time + 1
        break
    robot = (nx,ny)
    mad_robots = move_robot(mad_robots,robot)

    if robot in mad_robots:
        flag = True
        answer = time + 1
        break
    mad_robots = bomb_robot(mad_robots)


if flag:
    print(f'kraj {answer}')
else:
    arr[robot[0]][robot[1]] = 'I'
    for mad in mad_robots:
        arr[mad[0]][mad[1]] = 'R'

    for row in arr:
        print(''.join(row))

def find_brackt():
    for ind,command in enumerate(commands):
        if command == '[':
            bracket.append((ind,1))
        elif command == ']':
            bracket.append((ind,-1))
    brind = 0
    temp = []
    while brind < len(bracket): 
        if bracket[brind][1] == 1:
            temp.append(bracket[brind][0])
        else:
            open_bracket = temp.pop()
            bracket_couple[bracket[brind][0]] = open_bracket
            bracket_couple[open_bracket] = bracket[brind][0]
        brind += 1

def go():
    global command_index,string_index,pointer
    if commands[command_index] == '-':
        arr[pointer] = arr[pointer]-1
        if arr[pointer]<0:
            arr[pointer] = 255
    elif commands[command_index] == '+':
        arr[pointer] = arr[pointer] + 1
        if arr[pointer] > 255:
            arr[pointer] = 0
    elif commands[command_index] == '<':
        pointer -= 1
        if pointer < 0:
            pointer = memorysize -1
    elif commands[command_index] == '>':
        pointer += 1
        if pointer == memorysize:
            pointer = 0
    elif commands[command_index] == '[':
        if arr[pointer] == 0:
            command_index = bracket_couple[command_index]
    elif commands[command_index] == ']':
        if arr[pointer] != 0:
            command_index = bracket_couple[command_index]
    elif commands[command_index] == '.':
        pass
    else:
        if string_index == inputsize:
            arr[pointer] = 255
        else:
            arr[pointer] = ord(strings[string_index])
            string_index += 1
    command_index += 1

T = int(input())
MAX_NUMBER = 50000000
for tc in range(T):
    memorysize,codesize,inputsize = map(int,input().split())
    pointer = 0 # 포인터가 가리키는 index
    arr = [0]*memorysize
    command_cnt = 0  # 명령 횟수
    commands = list(input())
    strings = list(input())
    command_index = 0  # 명령어의 위치
    string_index = 0
    result = 'Terminates'
    bracket = []
    bracket_couple = {}
    find_brackt()
    loop_flag = False
    loop_idx = float('inf')
    while command_cnt <= MAX_NUMBER and command_index < codesize:
        command_cnt += 1
        go()
    if command_index == codesize:
        print('Terminates')
    else:
        while command_cnt >=0:
            command_cnt -= 1
            go()
            loop_idx = min(command_index,loop_idx)
        print(f'Loops {loop_idx-1} {bracket_couple[loop_idx-1]}')

def find_brackt():
    for ind,command in enumerate(commands):
        if command == '[':
            bracket.append((ind,1))
        elif command == ']':
            bracket.append((ind,-1))
    brind = 0
    temp = []
    while brind < len(bracket): 
        if bracket[brind][1] == 1:
            temp.append(bracket[brind][0])
        else:
            open_bracket = temp.pop()
            bracket_couple[bracket[brind][0]] = open_bracket
            bracket_couple[open_bracket] = bracket[brind][0]
        brind += 1



T = int(input())
MAX_NUMBER = 50000000
for tc in range(T):
    memorysize,codesize,inputsize = map(int,input().split())
    pointer = 0 # 포인터가 가리키는 index
    arr = [0]*memorysize
    command_cnt = 0  # 명령 횟수
    commands = list(input())
    strings = list(input())
    command_index = 0  # 명령어의 위치
    string_index = 0
    result = 'Terminates'
    bracket = []
    bracket_couple = {}
    find_brackt()
    loop_flag = False
    loop_idx = float('inf')
    while command_index < codesize:
        if commands[command_index] == '-':
            arr[pointer] = (arr[pointer]-1)%(2**8)
        elif commands[command_index] == '+':
            arr[pointer] = (arr[pointer]+1)%(2**8)
        elif commands[command_index] == '<':
            pointer -= 1
            if pointer < 0:
                pointer = memorysize -1
        elif commands[command_index] == '>':
            pointer += 1
            if pointer == memorysize:
                pointer = 0
        elif commands[command_index] == '[':
            if arr[pointer] == 0:
                command_index = bracket_couple[command_index]
        elif commands[command_index] == ']':
            if arr[pointer] != 0:
                command_index = bracket_couple[command_index]
        elif commands[command_index] == '.':
            pass
        else:
            if string_index == inputsize:
                arr[pointer] = 255
            else:
                arr[pointer] = ord(strings[string_index])
                string_index += 1
        command_index += 1
        command_cnt += 1
        if command_cnt > MAX_NUMBER:
            loop_idx = min(loop_idx,command_index)
        if command_cnt > MAX_NUMBER*2:
            loop_flag = True
            break
    
    if loop_flag:
        print(f'Loops {loop_idx-1} {bracket_couple[loop_idx-1]}')
    else:
        print('Terminates')

from collections import deque
import sys
input = sys.stdin.readline

N,M,K = map(int,input().split())


AppendList = [list(map(int,input().split())) for _ in range(N)]
tree_info = [[[] for _ in range(N)] for _ in range(N)]
result = 0
forest = [[5]*N for _ in range(N)]

for _ in range(M):
    X,Y,age = map(int,input().split())
    tree_info[X-1][Y-1].append(age)
    result += 1

dx = [-1,-1,-1,0,0,1,1,1]
dy = [-1,0,1,-1,1,-1,0,1]
for year in range(K):

    for x in range(N):
        for y in range(N):
            if len(tree_info[x][y])>0:
                temp = []
                summer_forest = 0
                cnt = 0
                limited = len(tree_info[x][y])
                while cnt < limited:
                    age = tree_info[x][y].pop()

                    if forest[x][y] >= age:
                        forest[x][y] -= age
                        temp.append(age+1)
                    else:
                        summer_forest += (age//2)
                        result -= 1
                    cnt += 1
                temp.sort(reverse=True)
                tree_info[x][y].extend(temp)
                forest[x][y] += summer_forest
            forest[x][y] += AppendList[x][y]
    for x in range(N):
        for y in range(N):
            spread_cnt = 0
            if tree_info[x][y]:
                for val in tree_info[x][y]:
                    if val%5 == 0:
                        spread_cnt += 1

            if spread_cnt:
                for i in range(8):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0<=nx<N and 0<=ny<N:
                        result += spread_cnt
                        tree_info[nx][ny].extend([1]*spread_cnt)
print(result)

 구현을 하는 문제인데, 문제에 주어진 조건대로 면 된다. 문제는 시간초과의 벽이 너무 컸다. 시간초과가 나지 않도록 최대한 문제에 주어진 조건을 한번에 구현할수 있도록 하는게 중요했다.

import sys
input = sys.stdin.readline
N,M,K  = map(int,input().split())
store = [list(map(int,input().split())) for _ in range(N)]
tree_info = [[{} for _ in range(N)] for _ in range(N)]
forest = [[5]*N for _ in range(N)]

tree_cnt = 0
for _ in range(M):
    x,y,age = map(int,input().split())
    tree_info[x-1][y-1][age] = 1
    tree_cnt += 1

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

for _ in range(K):
    for x in range(N):
        for y in range(N):
            if tree_info[x][y]:
                summer_forest = 0
                new_dict = {}

                for age in sorted(tree_info[x][y].keys()):
                    if forest[x][y] >= age * tree_info[x][y][age]:
                        forest[x][y] -= age * tree_info[x][y][age]
                        new_dict[age+1] = tree_info[x][y][age]
                    else:
                        if forest[x][y] // age:
                            new_dict[age+1] = forest[x][y]//age
                            forest[x][y] -=  age*new_dict[age+1]
                            if tree_info[x][y][age] - new_dict[age+1]:
                                summer_forest += (age//2) * (tree_info[x][y][age] - new_dict[age+1])
                                tree_cnt -= (tree_info[x][y][age] - new_dict[age+1])
                        else:
                            summer_forest += (age//2)*tree_info[x][y][age]
                            tree_cnt -= tree_info[x][y][age]
                tree_info[x][y] = new_dict
                forest[x][y] += summer_forest
            forest[x][y] += store[x][y]
    for x in range(N):
        for y in range(N):
            spread_cnt = 0
            for age in tree_info[x][y]:
                if not age%5:
                    spread_cnt += tree_info[x][y][age]
            if spread_cnt:
                for i in range(8):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0 <= nx <N and 0<=ny<N:
                        if tree_info[nx][ny].get(1):
                            tree_info[nx][ny][1] += spread_cnt
                        else:
                            tree_info[nx][ny][1] = spread_cnt
                        tree_cnt += spread_cnt
print(tree_cnt)

import sys


input = sys.stdin.readline
def roll(A,B):
    if A[0] >= B[0] and A[1] < B[1]:
        dx = A[0]-B[0]
        dy = B[1]-A[1]
        return (B[0]+dy,B[1]+dx)
    elif A[0] >= B[0] and A[1] >= B[1]:
        dx = A[0] - B[0]
        dy = A[1] - B[1]
        return (B[0]-dy,B[1]+dx)
    elif A[0] < B[0] and A[1] < B[1]:
        dx = B[0]-A[0]
        dy = B[1]-A[1]
        return (B[0]+dy,B[1]-dx)
    else:
        dx = B[0]-A[0]
        dy = A[1]-B[1]
        return (B[0]-dy,B[1]-dx)



def dragon(cur_gener,total_gener):
    global dragon_list
    if cur_gener == total_gener:
        return

    tail_position = dragon_list[-1]
    dragon_length = len(dragon_list)
    for ind in range(dragon_length-2,-1,-1):
        dragon_list.append(roll(dragon_list[ind],tail_position))
    dragon(cur_gener+1,total_gener)




N = int(input())
# x,y 시작점 d는 시작 방향 g는 세대 

dx = [1,0,-1,0]
dy = [0,-1,0,1]
arr = [[0]*101 for i in range(101)]
for _ in range(N):
    x,y,dire,gener = map(int,input().split())
    dragon_list = [(x,y),(x+dx[dire],y+dy[dire])]
    if gener:
        dragon(0,gener)
    for position in dragon_list:
        arr[position[1]][position[0]] = 1

result = 0



for y in range(100):
    for x in range(100):
        if arr[x][y] + arr[x+1][y] + arr[x+1][y+1] + arr[x][y+1] == 4:
            result += 1

print(result)

이 드래곤 커브는 끝에 있는 점을 기준으로 현재까지 온 경로들을 전부 시계 방향으로 90도 회전을 해주는 것을 계속 반복한다.

처음 풀었던 방식은 어렵게 생각해서 푼 문제이다.

드래곤 커브의 각 점들의 위치를 한 리스트에 넣어준다. 그러면 끝점을 찾아주고, 그 끝점을 기준으로 끝점을 제외한 나머지 점들의 위치를 파악해서, 옮겨주는 작업을 해주었다. 

좌표계로 그려보면 알겠지만, 끝점을 원점으로 생각해서, 그 점을 기준으로 1,2,3,4 사분면에 있을때 회전하는 위치를 계산해주었다.

1사분면에 있으면 1사분면의 y축 값은 x축값이 되고, x축의 값은 +y축값이 된다. 

2사분면에 있으면 2사분면의 x축값은 +y축값이 되고, y축값은 -x축 값이 된다.

이런식으로 구분을 해서, 각 끝점을 기준으로 움직인 위치를 찾아서 드래곤 커브 리스트에 넣어준다.

여기서 주의 해야할 점은 두가지인데, 문제에 주어진 xy좌표축은 수직방향으로 위로 올라갈수록 y축 값이 줄어드는 것이다.

그리고 두번째는 끝점을 기준으로 뒤에서부터 판별을해야 한다는 것이다.

이렇게 모든 세대를 돌리고 난뒤에 101*101 행렬에 점을 찍어주면 된다. 그리고 마지막으로 네 귀퉁이에 전부 1인 경우에를 세어서 결과로 출력하면 된다.

import sys

input = sys.stdin.readline

N = int(input())

arr = [[0]*101 for _ in range(101)]
dx = [1,0,-1,0]
dy = [0,-1,0,1]
for _ in range(N):
    x,y,dire,gener = map(int,input().split())
    # dire 0 ->1
    # 1->2
    # 2->3
    # 3->0
    move_list = [dire]
    arr[y][x] = 1
    for _ in range(gener):
        temp = []
        for i in range(len(move_list)-1,-1,-1):
            temp.append((move_list[i]+1)%4)
        move_list.extend(temp)
    for i in move_list:
        nx = x + dx[i]
        ny = y + dy[i]
        arr[ny][nx] = 1
        x,y  = nx,ny
result = 0
for y in range(100):
    for x in range(100):
        if arr[y][x] + arr[y+1][x] + arr[y][x+1] + arr[y+1][x+1] == 4:
            result += 1
print(result)

좀 더 쉬운 풀이는 다음과 같다.

진행방향만 넣어주는 것이다.

90도 시계방향을 회전하면 다음 진행반향은 현재 진행방향의 +1 의 modulo 4 연산을 해주면 된다.

이렇게 move_list에 넣어주고, 위에서처럼 끝점부터 해서 넣어주면 된다.

그리고 모든 세대를 지난뒤에, 처음시작점에서 진행방향에 맞춰서 점을 찍어주면 된다.