Coding 공부

# R,C 행,열
# 같은 클러스터
# 창영 동굴 왼쪽, 상근 오른쪽
from collections import deque
def BreakMineral(height,flag):
    y_list = sorted(list(range(C)),reverse=flag)
    height = R - height
    for y in y_list:
        if cave[height][y] == 'x':
            cave[height][y] = '.'
            return [height,y]
    
    return [-1,-1]

def DownCluster(input_point,flag):
    dx = [0,-1,0,1]
    dy = [1,0,-1,0]
    x,y = input_point
    cluster_entry = []
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<R and 0<=ny<C:
            if cave[nx][ny] == 'x':
                cluster_entry.append((nx,ny))

    
    cluster_list = []
    copy_cave = [row[:] for row in cave]
    for point in cluster_entry:
        if cave[point[0]][point[1]] == 'x':
            visited = set()
            stack = deque()
            stack.append(point)
            visited.add(point)
            while stack:
                x,y = stack.popleft()
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0<=nx<R and 0<=ny<C:
                        if cave[nx][ny] == 'x' and ((nx,ny)) not in visited:
                            visited.add((nx,ny))
                            stack.append((nx,ny))
            visited = list(visited)
            flag = True
            for point in visited:
                if point[0] == (R-1):
                    flag = False
                    break
            if flag:
                for point in visited:
                    cave[point[0]][point[1]] = '.'
                cluster_list.append(visited)
    if cluster_list:
        for cluster in cluster_list:
            origin_cluster = [row[:] for row in cluster]
            while True:
                move_point = []
                flag = False
                for point in cluster:
                    nx = point[0]+1
                    ny = point[1]
                    if 0<=nx<R and cave[nx][ny] == '.':
                        move_point.append((nx,ny))
                    else:
                        flag = True
                        break
                else:
                    cluster = [row[:] for row in move_point]
                if flag:
                    break

            for point in origin_cluster:
                copy_cave[point[0]][point[1]] = '.'
            for point in cluster:
                copy_cave[point[0]][point[1]] = 'x'
    return copy_cave



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

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

N = int(input())
arr = list(map(int,input().split()))
for i in range(N):
    if i%2:
        break_point = BreakMineral(arr[i],True)
        if break_point != [-1,-1]:
            cave = DownCluster(break_point,True)
    else:
        break_point = BreakMineral(arr[i],False)
        if break_point != [-1,-1]:
            cave = DownCluster(break_point,False)


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

시뮬레이션을 해서 푸는 문제였다. 이 문제에서 좌우를 번갈아 가면서 진행이 되기때문에 flag라는 속성을 줘서 구분을 해줬다.

BreakMineral이라는 함수는 막대를 던져 부서진 위치를 찾기 위함이다. 만약 하나도 부셔지지 않았다면 -1,-1을 반환하게 만들어줬다.

여기서 중요한 부분은 DownCluster 함수이다. 부서진 점을 위치로 해서, 상하좌우에 존재하는 미네랄이 있는지 확인을 한다.

그리고 그 미네랄을 너비우선탐색으로 확인하여, 만약에 (R-1) 즉 지면과 맞닿아 있으면, 낙하를 하지 않는 클러스터임을 알 수 있다.

그리고 지표면과 맞닿지 않는 클러스터들은 낙하하게 될  클러스터 이므로, 있던 위치들을 빈공간 '.'으로 만들어준다.

이렇게 모은 클러스터들을 한칸씩 움직이면서, 지표면과 맞닿는지? 아니면 다른 클러스터와 닿는지 x축 값만 증가시키면서 확인해준다.

멈추는 위치를 발견하면 그 위치에 'x'로 표시를 해주었다.

# R,C 행,열
# 같은 클러스터
# 창영 동굴 왼쪽, 상근 오른쪽
from collections import deque
def BreakMineral(height,flag):
    y_list = sorted(list(range(C)),reverse=flag)
    height = R - height
    for y in y_list:
        if cave[height][y] == 'x':
            cave[height][y] = '.'
            return [height,y]
    
    return [-1,-1]

def DownCluster(input_point,flag):
    dx = [0,-1,0,1]
    dy = [1,0,-1,0]
    x,y = input_point
    cluster_entry = []
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<R and 0<=ny<C:
            if cave[nx][ny] == 'x':
                cluster_entry.append((nx,ny))

    
    cluster_list = []
    for point in cluster_entry:
        if cave[point[0]][point[1]] == 'x':
            stack = [point]
            visited = set()
            visited.add(point)
            flag = True
            while stack:
                x,y = stack.pop(0)
                if x == (R-1):
                    flag = False
                    break
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0<=nx<R and 0<=ny<C:
                        if cave[nx][ny] == 'x' and ((nx,ny)) not in visited:
                            visited.add((nx,ny))
                            stack.append((nx,ny))
            if flag:
                visited = list(visited)
                for point in visited:
                    cave[point[0]][point[1]] = '.'
                cluster_list.append(visited)

    for cluster in cluster_list:
        move = 1
        flag = True
        while flag:
            for x,y in cluster:
                if x+move+1<R and cave[x+move+1][y] == '.':
                    continue
                else:
                    flag = False
                    break
            else:
                move += 1
        for x,y in cluster:
            cave[x+move][y] = 'x'



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

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

N = int(input())
arr = list(map(int,input().split()))
for i in range(N):
    if i%2:
        break_point = BreakMineral(arr[i],True)
        if break_point != [-1,-1]:
            DownCluster(break_point,True)
    else:
        break_point = BreakMineral(arr[i],False)
        if break_point != [-1,-1]:
            DownCluster(break_point,False)


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

이 부분은 좀 더 나은 풀이이다.

이 문제를 풀면서 크게 2가지 부분에서 실수를 했었다.

먼저 낙하하는 클러스터가 생길수 있는 위치를 던지는 방향의 y축방향과 -x 방향만 생길수 있다고 생각했다.

하지만 그럴경우 

4 4
xxxx
xx.x
x..x
...x 
1
3

와 같은 경우엔 밑에 있는 미네랄이 떨어짐을 알 수 있다. 그래서 그부분을 고쳐주었다.

두번째로 어려웠던 부분은 클러스터들을 낙하시키는것이었다. 클러스터의 복제위치 및 클러스터들이 낙하할때 탐색할 배열을 선정하는데 어려움을 겪었다.

처음 풀었을때는 원본배열을 복사하고, 옮기는 방식으로 했지만,

두번째로 푼 코드는 원본배열에서 그대로 작업을 해주었다.

이 2가지 부분이 이 문제를 푸는데 어려움을 겪었던 부분이었다.

def find_favorite_seat(num,fa_list):
    max_list = [[[] for _ in range(5)] for _ in range(5)]
    for x in range(N):
        for y in range(N):
            if arr[x][y] == 0:
                favorite_cnt = 0
                empty_cnt = 0
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0<=nx<N and 0<=ny<N:
                        if arr[nx][ny] == 0:
                            empty_cnt += 1
                        elif arr[nx][ny] in favorite_students:
                            favorite_cnt += 1
                max_list[favorite_cnt][empty_cnt].append((x,y))

    for fa_c in range(4,-1,-1):
        for em_c in range(4,-1,-1):
            if max_list[fa_c][em_c]:
                max_list[fa_c][em_c].sort()
                arr[max_list[fa_c][em_c][0][0]][max_list[fa_c][em_c][0][1]] = num
                return
                    
            




N = int(input())
# (r행 c열)

arr = [[0 for _ in range(N)] for _ in range(N)]

dx = [-1,1,0,0]
dy = [0,0,-1,1]
student_dict = {}
for _ in range(N**2):
    input_list = list(map(int,input().split()))
    student_number = input_list[0]
    favorite_students = set(input_list[1:])
    student_dict[student_number] = favorite_students
    find_favorite_seat(student_number,favorite_students)

fill_gage = [0,1,10,100,1000]

result = 0
for x in range(N):
    for y in range(N):
        cnt = 0
        num = arr[x][y]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx<N and 0<=ny<N:
                if arr[nx][ny] in student_dict[num]:
                    cnt += 1

        result += fill_gage[cnt]

print(result)

numbers = [0]*500001
N = int(input())
arr = map(int,input().split())
for k in arr:
    numbers[k] += 1
print(max(numbers))

N = int(input())

arr = list(map(int,input().split()))

arr.sort()
min_value = 0
if len(arr)%2:
    min_value = arr.pop()
    lens = len(arr)//2
    for _ in range(lens):
        t = arr.pop() + arr.pop(0)
        min_value = max(min_value,t)
else:
    lens = len(arr)//2
    for _ in range(lens):
        t = arr.pop() + arr.pop(0)
        min_value = max(min_value,t)
print(min_value)

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

arr = list(map(int,input().split()))
dp = [0]*(N+1)
result = 0


left = 0
right = 0
sum_temp = 0
while right <=N:
    if sum_temp >=K:
        while sum_temp >= K:
            dp[right] = max(dp[right],dp[left]+sum_temp-K)
            sum_temp -= arr[left]
            left += 1
    else:
        dp[right] = max(dp[right],dp[right-1])
        if right == N:
            break
        sum_temp += arr[right]
        right += 1
print(dp[N])

import sys

sys.setrecursionlimit(100001)
def find_min_right_over_k(left):
    global K
    low = left -1
    high = N
    while low + 1 < high:
        mid = (low+high)//2
        if prefix_sum[mid] - prefix_sum[left-1] >=K:
            high = mid
        else:
            low = mid
    return high




def solution(left):
    if left > N:
        return 0
    if dp[left] != -1:
        return dp[left]
    pass_hear_value = solution(left+1)
    right = find_min_right_over_k(left)
    eat_left_right = prefix_sum[right]-prefix_sum[left-1]-K+solution(right+1)
    max_value = max(pass_hear_value,eat_left_right)
    dp[left] = max_value
    return dp[left]

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

arr = list(map(int,input().split()))

dp = [-1]*(N+1)

prefix_sum = [0]+arr[:]
for k in range(1,N+1):
    prefix_sum[k] += prefix_sum[k-1]


print(solution(1))

from collections import deque
import sys

input = sys.stdin.readline
N, M = map(int,input().split())
recipe_dict = {}
next_node_list = [set() for _ in range(N+1)]
for _ in range(M):
    input_list = list(map(int,input().split()))
    recipe = input_list[1:-1]
    liquid_number = input_list[-1]
    recipe.sort()
    if recipe_dict.get(liquid_number):
        recipe_dict[liquid_number].append([set(recipe),input_list[0]])
    else:
        recipe_dict[liquid_number] = [[set(recipe),input_list[0]]]

    for num in recipe:
        next_node_list[num].add(liquid_number)

L = int(input())
own_liquid = list(map(int,input().split()))
possible_list = [False]*(N+1)
result = set()
for num in own_liquid:
    possible_list[num] = True
    result.add(num)
queue = deque(own_liquid)
while queue:
    cur_num = queue.popleft()

    next_nodes = next_node_list[cur_num]

    for next_node in next_nodes:
        if possible_list[next_node]:
            continue
        for ind in range(len(recipe_dict[next_node])):
            recipe = recipe_dict[next_node][ind][0]
            cnt = recipe_dict[next_node][ind][1]

            if cur_num in recipe:
                cnt -= 1
                recipe.remove(cur_num)
                recipe_dict[next_node][ind][0] = recipe
                recipe_dict[next_node][ind][1] = cnt
                if cnt == 0:
                    possible_list[next_node] = True
                    queue.append(next_node)
                    result.add(next_node)


print(len(result))
result = sorted(list(result))
print(*result)

import sys

input = sys.stdin.readline

N,M = map(int,input().split())
recipe_remain_cnt = []
liquid_number = []
next_recipe_array = [[] for _ in range(N+1)]
for i in range(M):
    k,*recipe,r = map(int,input().split())

    recipe_remain_cnt.append(k)
    liquid_number.append(r)

    for num in recipe:
        next_recipe_array[num].append(i)


L = int(input())
own_liquid = list(map(int,input().split()))
result = set(own_liquid)


while own_liquid:
    cur_num  = own_liquid.pop()
    for recipe_idx in next_recipe_array[cur_num]:
        recipe_remain_cnt[recipe_idx] -= 1
        if recipe_remain_cnt[recipe_idx] == 0 and liquid_number[recipe_idx] not in result:
            own_liquid.append(liquid_number[recipe_idx])
            result.add(liquid_number[recipe_idx])

print(len(result))
result = sorted(list(result))

print(*result)

L,H,W = map(int,input().split())


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


for i in range(L):
    start_y = i*W
    flag = False
    for y in range(start_y,start_y+W):
        for x in range(H):
            if arr[x][y] != '?':
                answer.append(arr[x][y])
                flag = True
                break
        if flag:
            break
    else:
        answer.append('?')
print(''.join(answer))

N = int(input())

def bubble(arr,tc):
    global score
    all_row = set(range(6))
    remove_arr = set()
    empty_arr = set()
    for row in range(5,-1,-1):
        if sum(arr[row]) == 4:
            remove_arr.add(row)
        elif not sum(arr[row]):
            empty_arr.add(row)

    remain_row = sorted(list(all_row - remove_arr - empty_arr))
    temp = []
    while len(remain_row) > 4:
        remain_row.pop()

    for _ in range(6-len(remain_row)):
        temp.append([0]*4)
    for row in remain_row:
        temp.append(arr[row][:])
    score += len(remove_arr)
    return temp





def move(arr,block_type,x,y,tc):
    global score
    if block_type == 1:
        for row in range(6):
            if arr[row][y]:
                arr[row-1][y] = 1
                break
        else:
            arr[row][y] = 1
    elif block_type == 2:
        for row in range(6):
            if arr[row][y] or arr[row][y+1]:
                arr[row-1][y] = 1
                arr[row-1][y+1] = 1
                break
        else:
            arr[row][y] = 1
            arr[row][y+1] = 1
    else:
        for row in range(5):
            if arr[row][y] or arr[row+1][y]:
                arr[row][y] = 1
                arr[row-1][y] = 1
                break
        else:
            arr[row][y] = 1
            arr[row+1][y] = 1
    return bubble(arr,tc)

blue_arr = [[0]*4 for _ in range(6)]
green_arr = [[0]*4 for _ in range(6)]


score = 0
for tc in range(N):
    # 1번 1칸 2번 가로 2칸 3번 세로 2칸
    block_type,x,y = map(int,input().split())
    green_arr = move(green_arr,block_type,x,y,tc)
    if block_type == 2:
        block_type = 3
    elif block_type == 3:
        block_type = 2
    blue_arr = move(blue_arr,block_type,y,x,tc)

print(score)
total_block = sum(map(sum,green_arr)) + sum(map(sum,blue_arr))
print(total_block)