Coding 공부

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



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

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

stack_list = [[[],set()] for _ in range(N+1)]
card_deck = deque()
result = []
for _ in range(T):
    input_list = list(input().split())
    card_deck.append(input_list)

num_occupy_set = set()
for ind in order_list:
    if len(stack_list[ind][0]) > 0:
        cu_card = stack_list[ind][0][0]
        result.append(cu_card[0])
        if cu_card[2] in num_occupy_set:
            continue
        else:
            stack_list[ind][0].pop(0)
            stack_list[ind][1].add(cu_card[2])
            num_occupy_set.add(cu_card[2])

    else:
        cu_card = card_deck.popleft()
        result.append(cu_card[0])

        if cu_card[1] == 'next':
            continue
        elif cu_card[1] == 'acquire':
            if cu_card[2] in num_occupy_set:
                stack_list[ind][0].append(cu_card)
            else:
                stack_list[ind][1].add(cu_card[2])
                num_occupy_set.add(cu_card[2])
        else:
            stack_list[ind][1].remove(cu_card[2])
            num_occupy_set.remove(cu_card[2])

for i in range(T):
    sys.stdout.write(result[i]+"\n")

문제에 주어진대로 사람 수대로, deck을 만들어준뒤, 순서대로 명령어를 실행해주면 되는 구현 문제였다.

만약에 acquire 카드를 썼지만, 카드더미에 없으면, 자기 덱에 카드를 넣어주고, 그 카드를 다시 실행해주는 구현부분만 제대로 해주면 된다.

 이 코드는 깔끔하지 못해서 대회가 끝나고 난뒤에 고친 코드는 밑에 있다.

import sys
from collections import deque
input = sys.stdin.readline
N,T = map(int,input().split())

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



card_deck = deque()

for _ in range(T):
    temp = input().rstrip().split(' ')
    card_deck.append(temp)

occupy_card = [[] for _ in range(N+2)]
result = []
used_card_num = set()
for i in range(T):
    person = turns[i]

    if len(occupy_card[person])>0:
        card_num,wanted_num = occupy_card[person]
        result.append(card_num)
        if wanted_num in used_card_num:
            continue
        else:
            used_card_num.add(wanted_num)
            occupy_card[person] = []
    else:
        card_num,*rests= card_deck.popleft()
        result.append(card_num)
        if rests[0] == 'next':
            continue
        elif rests[0] == 'acquire':
            if rests[1] in used_card_num:
                occupy_card[person] = (card_num,rests[1])
            else:
                used_card_num.add(rests[1])
        elif rests[0] == 'release':
            used_card_num.remove(rests[1])


for i in range(T):
    sys.stdout.write(result[i]+'\n')

어차피 보유하고 있을수 있는 카드는 한장이므로,  set을 굳이 넣을 필요가 없고, used_card를 통해, 쓴 카드와 안쓴 카드를 구분을 해줬다.

from collections import deque
import sys

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


arr = []
start = []
for x in range(R):
    temp = list(input())

    for y in range(C):
        if temp[y] == 'G':
            start = (x,y)

    arr.append(temp)


stack = []

stack.append((*start,0,set()))
time = 0
result = 0
dx = [-1,1,0,0]
dy = [0,0,1,-1]
while time<T:
    new_stack = []
    for x,y,eat,visited in stack:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx<R and 0<=ny<C:
                if arr[nx][ny] == 'S' and (nx,ny) not in visited:
                    new_visited = set()
                    new_visited.add((nx,ny))
                    new_visited = new_visited | visited
                    new_stack.append((nx,ny,eat+1,new_visited))
                    result = max(eat+1,result)
                elif arr[nx][ny] != '#':
                    new_stack.append((nx,ny,eat,visited))
    stack = [row[:] for row in new_stack]
    time += 1

print(result)
    

대회때 풀었던 풀이는 다음과 같다 BFS를 해주면서, 모든 이동경로를 누적해줬다.

그리고 visited에 없는 경우에만 고구마를 먹도록 해줬다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
def dfs(node,time,eat):
    global T,result,R,C
    if time == T:
        result = max(result,eat)
        return
    else:
        result = max(result,eat)
        for i in range(4):
            nx = node[0] + dx[i]
            ny = node[1] + dy[i]
            if 0<=nx<R and 0<=ny<C and not vistied[nx][ny]:
                vistied[nx][ny] = True
                if arr[nx][ny] == 'S':
                    dfs((nx,ny),time+1,eat+1)
                else:
                    dfs((nx,ny),time+1,eat)
                vistied[nx][ny] = False
            elif 0<=nx<R and 0<=ny<C and vistied[nx][ny] and arr[nx][ny] !='#':
                dfs((nx,ny),time+1,eat)

R,C,T = map(int,input().split())
result = 0
vistied = [[False for _ in range(C)] for _ in range(R)]


arr = []
start = []
for x in range(R):
    temp = list(input())
    for y in range(C):
        if temp[y] == '#':
            vistied[x][y] = True
        elif temp[y] == 'G':
            start = (x,y)
    arr.append(temp)


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

dfs(start,0,0)
print(result)

대회가 끝나고 난뒤의 풀이이다.

dfs를 해주는데 바문을 최초로 한 경우의 S일때에만 고구마를 먹도록 했다.

그리고, 방문을 했지만, 벽만 아니라면, 지나갈수 있도록 만들어줬다.

def dfs(cnt):
    if cnt == 81:
        for row in sdoku:
            print(''.join(list(map(str,row))))
        exit()
    else:
        x = cnt//9
        y = cnt%9
        square = (x//3)*3 + y//3
        if sdoku[x][y] == 0:
            for num in range(1,10):
                if not (column_check[y][num] or row_check[x][num] or square_check[square][num]):
                    column_check[y][num] = True
                    row_check[x][num] = True
                    square_check[square][num] = True
                    sdoku[x][y] = num
                    dfs(cnt+1)
                    sdoku[x][y] = 0
                    column_check[y][num] = False
                    row_check[x][num] = False
                    square_check[square][num] = False


        else:
            dfs(cnt+1)



sdoku = []

column_check = [[False for _ in range(10)] for _ in range(9)]
row_check = [[False for _ in range(10)] for _ in range(9)]
square_check =[[False for _ in range(10)] for _ in range(9)]
for x in range(9):
    temp = list(map(int,list(input())))
    for y in range(9):
        if temp[y] != 0:
            square = (x//3)*3 + y//3
            column_check[y][temp[y]] = True
            row_check[x][temp[y]] = True
            square_check[square][temp[y]] = True
    sdoku.append(temp)


dfs(0)

스도쿠의 특성을 활용해서 하면 된다.

먼저 각 열, 각 행, 3*3 사각형의 숫자를 얼만큼 사용했는지를 CHECK 해주는 리스트를 만들어준다.

여기서 square 넘버를 부여하는 방식은 (x//3)*3 + (y//3)으로 해서, 가장 위에서 부터 

0 1 2

3 4 5

6 7 8

로 구분이 가능하게 해줬다.

그리고 dfs를 활용해서, cnt는 전체 칸의 갯수를 뜻하면서, 좌표를 뜻하도록 했다. 해당 좌표에서 비어있으면,

숫자를 하나씩 넣어가면서 백트래킹을 해줬다.

그리고 마지막에 도착하면, 현재 스도쿠를 출력해주고, 함수를 종료시켜줬다.

가장 앞에서부터 하나하나씩 채워나가는 것이기때문에, 가장 먼저 완료되는것이 사전순으로 가장 빠른 스도쿠가 된다.

import sys

sys.setrecursionlimit(10000)
def roll(x,y,vis,cnt,roll_cnt):
    global result,total_cnt
    if total_cnt == cnt:
        result = min(result,roll_cnt)
        return
    if roll_cnt > result:
        return
    vis[x][y] = True
    dx = [-1,1,0,0]
    dy = [0,0,1,-1]
    for i in range(4):
        move = 1
        nx = x + dx[i]*move
        ny = y + dy[i]*move
        while 0<=nx<N and 0<=ny<M and vis[nx][ny] == False:
            nx = nx + dx[i]
            ny = ny + dy[i]
            move += 1
        if move>1:
            for m in range(1,move):
                nx = x + dx[i]*m
                ny = y + dy[i]*m
                vis[nx][ny] = True
            
            roll(nx,ny,vis,cnt+(move-1),roll_cnt+1)

            for m in range(1,move):
                nx = x + dx[i]*m
                ny = y + dy[i]*m
                vis[nx][ny] = False




tc = 1
while True:
    try:
        N,M = map(int,input().split())
        arr = []
        total_cnt = N*M
        visited = [[False]*M for _ in range(N)]
        for x in range(N):
            temp = list(input())
            for y in range(M):
                if temp[y] == '*':
                    visited[x][y] = True
                    total_cnt -= 1
            
            arr.append(temp)

        result = float('inf')
        for x in range(N):
            for y in range(M):
                if arr[x][y] == '.':
                    copy_visited = [row[:] for row in visited]
                    roll(x,y,copy_visited,1,0)

        if result == float('inf'):
            result = -1
        print(f'Case {tc}: {result}')
        tc += 1
    except:
        break

이 문제는 문제에 주어진 조건대로 굴리면 되는 문제였다.

여기서 주의해야할 점은 최소 이동거리가 1이상이어야하고, 그때에만 움직여주면서 VISITED를 반대 상태로 바꿔줬다가, 탐색이 끝나면 원래 상태로 바꿔주는 것이 필요로 했다.

또한 최소 이동횟수이므로, 이동횟수보다 많은 로직에 대해서는, 탐색을 그만두고 되돌아가는 백트래킹이 필요로 했다.

처음에 최소 이동횟수가 아닌, N*M 보드 완주하는 횟수를 구하는 줄 알고, 잘못 구현하는 실수를 저질렀었다.

그점만 조심하면, DFS를 재귀를 짜는것과 비슷하게 풀면 되는 문제였다.

arr = list(map(int,input().split()))
check_border = [
    [
        1,2,17,19,
        13,3,4,15,
        5,6,7,8,
        14,16,11,12,
        9,10,18,20,
        21,22,23,24
    ],
    [
        1,2,14,16,
        13,15,9,10,
        11,12,17,19,
        3,4,18,20,
        21,22,23,24,
        5,6,7,8,
    ],
    [1,3,6,8,
    5,7,10,12,
    9,11,21,23,
    22,24,2,4,
    17,18,19,20,
    13,14,15,16], 
    [1,3,21,23,
    5,7,2,4,
    9,11,6,8,
    22,24,10,12,
    13,14,15,16,
    17,18,19,20], 
    [1,2,3,4,
    5,6,15,16,
    9,10,11,12,
    13,14,23,24,
    17,18,7,8,
    21,22,19,20], 
    [1,2,3,4,
    5,6,19,20,
    13,14,7,8,
    9,10,11,12,
    17,18,23,24,
    21,22,15,16]
]

result = 0
for i in range(6):
    check = check_border[i]
    for j in range(6):
        check_face = list(map(lambda x : x-1,check[(4*j):4*(j+1)]))
        if not (arr[check_face[0]] == arr[check_face[1]] == arr[check_face[2]] == arr[check_face[3]]):
            break
    else:
        result = 1
        break

print(result)
            

이 문제에서 주의해야할 건 무조건 1번 움직이는 것이다.

그리고 2 X 2 X 2 의 큐브의 경우, 돌릴때 1번 돌릴때 딱 6가지의 경우의 수 밖에 없으므로,

그 6가지를 전부 구해놓고, 4개 간격으로 같은색인지 확인하는 방식으로 풀면 된다.

# N: 방 크기
# M : 공팡이 개수
# K : 검사하는 개수
# t : 남은 일수
import sys

def input():
    return sys.stdin.readline().rstrip()
N,M,K,T = map(int,input().split())

mold = set()
visited = [[False]*N for _ in range(N)]
for _ in range(M):
    input_list = list(input().split())
    temp = []
    for check in input_list:
        if check.isdigit():
            temp.append(int(check))
    if len(temp)==2:
        mold.add((temp[0]-1,temp[1]-1))
        visited[temp[0]-1][temp[1]-1] = True
cleaning_place = []
for _ in range(K):
    input_list = list(input().split())
    temp = []
    for check in input_list:
        if check.isdigit():
            temp.append(int(check))
    if len(temp) == 2:
        cleaning_place.append((temp[0]-1,temp[1]-1))


dx = [-2,-1,1,2,2,1,-1,-2]
dy = [-1,-2,-2,-1,1,2,2,1]
time = 0
result = 'NO'
flag = False
while time <T:
    new_mold = set()
    for x,y, in mold:
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N:
                visited[nx][ny] = True
                new_mold.add((nx,ny))
    time += 1
    cnt = 0
    for x,y in cleaning_place:
        if (x,y) in new_mold and (T-time)%2 == 0:
            result = 'YES'
            flag= True
            break
        elif (x,y) not in new_mold and visited[x][y]:
            cnt += 1
    else:
        if cnt == len(cleaning_place):
            flag = True
    if len(new_mold) == 0:
        flag = True
    mold = set(list(new_mold))
    if flag:
        break

print(result)

문제 자체는 그렇게 어렵지 않았지만, 문제가 되었던 것은 데이터 오류가 있었던 문제였다.

이 문제를 푸시는 분들은 수정이 되기전까지 청소할 곳이 주어지는 INPUT에 공백이 있으니, 그 점을 주의해서 풀기 바란다.

문제 아이디어 자체는 간단한 편이다.

청소를 해야하는 시간 T가 있으면, 그 시간 T의 짝수번째 시간전에 곰팡이가 존재하면, 시간 T일때에도

곰팡이가 존재한다는 점을 생각하면 된다.

그냥 전체시간 T에 대해서 반복을 하면 시간초과가 날 수 있다. 그렇기 때문에 매 시간마다 판별을 해주면 된다.

판별을 하는 방법은 다음과 같다. 현재 곰팡이가 존재하며, 청소시간 T와 현재시간 time의 차이가 2의배수이면,

해당 지역에는 곰팡이가 있는것이고, 청소를 해야한다. 그러므로 그때 break를 해주면 된다.

그리고 모든 경우에 대해서, 현재 곰팡이가 존재하지 않고, 곰팡이가 생겼던 적이 있는경우라면, 청소시간 T에

곰팡이가 존재하지 않는 것이기 때문에, 청소를 할 필요가 없다. 모든 청소구간에 대해서 이와 같은 경우가 생기면,

그 문제에서는 청소를 할 필요가 없기 때문에 반복문을 탈출시켜주면 된다.

import sys
from collections import deque

def grow(arr,queue):
    dx = [-2,-1,1,2,2,1,-1,-2]
    dy = [-1,-2,-2,-1,1,2,2,1]

    while queue:
        x,y = queue.popleft()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <=nx<N and 0<=ny<N:
                if arr[nx][ny] == -1:
                    arr[nx][ny] = arr[x][y] + 1
                    queue.append((nx,ny))


input = sys.stdin.readline


N,M,K,T = map(int,input().split())
mold_even = deque()
mold_odd = deque()
odd_list =[[-1]*N for _ in range(N)]
even_list = [[-1]*N for _ in range(N)]
for i in range(M):
    x,y = map(lambda x: x-1,map(int,input().split()))
    if (x+y)%2:
        odd_list[x][y] = 0
        mold_odd.append((x,y))
    else:
        even_list[x][y] = 0
        mold_even.append((x,y))



grow(even_list,mold_even)
grow(odd_list,mold_odd)
# 초기값이 홀수이면 odd에 있는데 이 경우, T가 짝수일때에만 ON이 된상태이다.
# odd_list : odd이면 T가 짝수이면 ON
# odd_list : odd이면 T가 홀수이면 off
# even_list : odd이면서 T가 짝수이면 off
# even_list : odd이면서 T가 홀수이면 ON
# 이렇게 되기 때문에 odd이면서 T가 짝수이면 odd_list를 odd이면서 T가 홀수이면 even_list를 탐색해줘야한다.
# even도 똑같이 해주면 된다.
for _ in range(K):
    x,y = map(lambda x: x-1,map(int,input().split()))
    flag = True
    if (x+y)%2 and T%2:
        flag = False
    elif (x+y)%2 == 0 and T%2==0:
        flag = False
    if flag and 0<=odd_list[x][y]<=T:
        print('YES')
        break
    elif not flag and 0<=even_list[x][y]<=T:
        print('YES')
        break
else:
    print('NO')

이 풀이는 jh05013님의 풀이를 분석해서 한 풀이이며, 좀 더 깔끔한 코드이고 배울게 많은 코드라서 공부를 한 풀이입니다.

이 풀이 같은 경우 처음 곰팡이의 위치를 홀수 짝수일때를 구분해서, 두 Array로 나누어서 저장을 시켜줍니다.

그 이유는 다음과 같습니다.

이 문제에서 곰팡이가 퍼지는 방식은 (+-2,+-1) or (+-1,+-2) 입니다.

그렇다보니 현재 위치가 짝수이면, 그 다음 위치는 홀수, 그 다음의 위치는 짝수이게 됩니다. 

그러면 처음위치가 짝수인 것은 0초에는 짝수 1초에는 홀수 2초에는 짝수 3초에는 홀수로 반복합니다.

이와 같이 홀수 인것은 0초에는 홀수 1초에는 짝수 2초에는 홀수가 됩니다.

이렇게 2개의 행렬로 나누고, bfs를 진행시켜줍니다.

인제 판별을 해줘야하는데 크게 4가지로 나뉩니다.

청소 위치가 짝수일때 홀수일때와 청소시간이 짝수 홀수 일때입니다.

표를 나타내면 위와 같습니다. 시간이 짝수이면, EVEN_LIST는 짝수의 위치에 대해서만 곰팡이가 있습니다.

그에 반해 ODD_LIST는 홀수 위치에서 대해서만 곰팡이가 있습니다.

그와 반대로 시간이 홀수 이면 EVEN_LIST는 홀수위치에만 곰팡이가 존재할 수 있고,

ODD_LIST에는 짝수 위치에서만 곰팡이가 생길수 있습니다.

이렇듯 곰팡이가 짝수간격으로 패턴이 있고, 홀수일때와 짝수일때가 서로 반대되는 점을 응용하면

위와 같이 간단하게 구현할 수 있는 문제였습니다.

# 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)