Coding 공부

import sys
import heapq

input = sys.stdin.readline

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

graph = [{} for i in range(N+1)]
plant = list(map(int,input().split()))
INF = float('inf')
for _ in range(M):
    u,v,w = map(int,input().split())
    graph[u][v] = min(graph[u].get(v,float('inf')),w)
    graph[v][u] = min(graph[v].get(u,float('inf')),w)



MST_DISTANCE = [INF for i in range(N+1)]
visited = [True]*(N+1)

result = 0
node_list = []
for start in plant:
    heapq.heappush(node_list,(0,start))
    MST_DISTANCE[start] = 0

while node_list:
    dis,node = heapq.heappop(node_list)
    if not visited[node]:
        continue
    result += dis
    visited[node] = False
    for next_node in graph[node]:
        if MST_DISTANCE[next_node] >graph[node][next_node]:
            MST_DISTANCE[next_node] = graph[node][next_node]
            heapq.heappush(node_list,(MST_DISTANCE[next_node],next_node))


print(result)

서로 다른 발전소끼리 연결이 되면 안되므로, 프림알고리즘을 하는데, 발전소의 위치를 전부 0으로 초기화 해주고,

전부 heapq에 넣어주고, Prim 알고리즘을 돌려주면 된다.

import sys
input = sys.stdin.readline

def union(a,b):
    A = find_parent(a)
    B = find_parent(b)
    if A != B:
        if rank[A] < rank[B]:
            A,B = B,A
        make_set[B] = A
        if rank[A] == rank[B]:
            rank[A] += 1

def find_parent(ind):
    if make_set[ind] == ind:
        return ind
    else:
        make_set[ind] = find_parent(make_set[ind])
        return make_set[ind]


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


plant = list(map(int,input().split()))
make_set = [i for i in range(N+1)]
rank = [1 for _ in range(N+1)]
edges = []
for _ in range(M):
    u,v,w = map(int,input().split())
    edges.append((u,v,w))

edges.sort(key=lambda x : -x[2])


for k in range(1,K):
    union(plant[k],plant[k-1])

cnt = 1
result = 0
while cnt <(N-K+1):
    x,y,weight = edges.pop()
    if find_parent(x) != find_parent(y):
        union(x,y)
        result += weight
        cnt += 1

print(result)

    두번째 풀이는 크루스칼을 이용해서 풀었다.

발전소가 서로 연결이 되면 안되므로, 처음부터 모든 발전소를 하나의 union으로 merge를 해준다.

그리고 난뒤에 크루스칼 알고리즘을 해주면 된다.

그리고 전체 간선 수는 전체 노드의 수 - 1 이지만, 여기서는 (N-1)-(K-1)의 수 만큼만 해주면 된다.

이 문제를 처음에 어렵게 생각해서 각 플랜트만의 프림알고리즘을 돌려서, 최저값을 갱신하는 식으로 했다.

하지만, 같이 연결이 안되기만 하면 되니깐 프림 알고리즘을 하면서, 처음 스타트 위치를 전부 넣어주기만 하면 됬다.

이 문제에 더 어울리는 알고리즘은 프림보다, 크루스칼 알고리즘인 것 같다.

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에는 짝수 위치에서만 곰팡이가 생길수 있습니다.

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

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

import math
import sys


def dfs(node):
    stack = [(node,0,0)]
    visited = [True]*(N+1)
    distance = 0
    max_node = -1
    min_time = float('inf')
    visited[node] = False
    while stack:
        node,dis,time = stack.pop()
        if dis > distance:
            distance = dis
            max_node = node
            min_time = time
        elif dis == distance and min_time > time:
            max_node = node
            min_time = time

        for next_node in graph[node]:
            if visited[next_node]:
                new_dis = dis + 1
                new_time = time + graph[node][next_node]
                visited[next_node] = False
                stack.append((next_node,new_dis,new_time))

    return [max_node,distance,min_time]



input = sys.stdin.readline

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


graph = [{} for _ in range(N+1)]


for _ in range(N-1):
    x,y,time = map(int,input().split())
    graph[x][y] = time
    graph[y][x] = time

far_node_info = dfs(1)

result = dfs(far_node_info[0])


print(math.ceil(result[2]/T))

트리의 지름 이 문제를 풀어보면 해당 문제를 좀 더 쉽게 풀 수 있다.

문제의 조건은 총 2가지이다. 문제를 가장 많이 풀어야하며, 그 푸는데 시간이 가장 짧아야한다.

이 문제는 트리구조이다. 그래서 문제를 가장 많이 푼다는 것은 트리의 지름을 구하는것과 같다.

그러므로 처음 dfs로 아무 노드에서 가장 먼 노드를 찾고, 그 노드에서 가장 먼 노드들을 찾으면 그게 트리의 지름이 된다.

이걸 응용해서, 첫 dfs로 가장 먼 노드 하나를 찾는다.

그리고 두번째 dfs로 찾은 가장 먼 노드를 기준으로, dfs를 돌려서 깊이가 가장 깊은 노드들을 찾는다. 그리고 그 중에서, 시간이 가장 짧은 것을 선택해주면 된다.

이 문제는 1967번 문제의 트리의 지름을 응용한 문제이고, 트리의 특성에 대해 알고 있으면 쉽게 풀 수 있었던 문제였지만,

처음에 트리의 지름에 대한 아이디어를 얻지 못해서 어려웠던 문제이다.

N = int(input())

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

arr.sort()


elsa_start = 0
elsa_end = N -1
result = float('inf')

for elsa_start in range(N-3):
    for elsa_end in range(elsa_start+3,N):
        anna_start = elsa_start + 1
        anna_end = elsa_end - 1
        elsa = arr[elsa_start] + arr[elsa_end]
        while anna_start < anna_end:
            anna = arr[anna_start] + arr[anna_end]
            temp = elsa-anna
            if result > abs(temp):
                result = abs(temp)
            
            if temp > 0:
                anna_start += 1
            else:
                anna_end -= 1



print(result)

첫 풀이는 ELSA와 ANNA로 나누는데, ELSA를 작은것을 1~N-3까지 그리고 큰 눈사람을 3~N 사이의 것을 고르고, 그 사이의 값에서 elsa anna의 격차가 작은걸 구했다.

def diffcheck(A,B):
    ss = set()
    ss.update(A)
    ss.update(B)
    if len(ss) == 4:
        return True
    return False
def getDiffHeight(A,B):
    elsa = arr[A[0]] + arr[A[1]]
    anna = arr[B[0]] + arr[B[1]]
    return abs(elsa-anna)
N = int(input())

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

arr.sort()

stack = []

for i in range(N-1):
    for j in range(i+1,N):
        stack.append((i,j))

stack.sort(key=lambda x : arr[x[0]]+arr[x[1]])
result = float('inf')
for i in range(len(stack)-1):
    if diffcheck(stack[i],stack[i+1]):
        result = min(result,getDiffHeight(stack[i],stack[i+1]))


print(result)

두번째 풀이는 다음과 같다. 가능한 좌표의 조합을 다 구하고,

그 좌표의 조합에서 나오는 눈사람의 크기를 기준으로 정렬을 해준다.

그리고 그 4개의 고른 눈사람 좌표가 다르고, 그 격차가 작으면, 최저값으로 갱신해주는 것이다.

from collections import deque
N, M = map(int,input().split())



lower_dict = {}
upper_dict = {}

for i in range(6):
    lower_dict[chr(ord('a')+i)] = i
    upper_dict[chr(ord('A')+i)] = i

start = []
arr = []
for x in range(N):
    input_list = list(input())
    for y in range(M):
        if input_list[y] == '0':
            start = (x,y)
    arr.append(input_list)


stack = deque()
stack.append((0,start,0))
flag = True
result = []
INF = float('inf')
dx = [-1,1,0,0]
dy = [0,0,-1,1]
visited = [[[INF for _ in range(M)] for _ in range(N)] for _ in range(64)]
visited[0][start[0]][start[1]] = 0
while stack:
    time,cur_node,state = stack.popleft()
    x,y = cur_node
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<N and 0<=ny<M:
            if arr[nx][ny] != '#' and visited[state][nx][ny] == INF:
                if arr[nx][ny] in upper_dict.keys():
                    if state & 1<<upper_dict[arr[nx][ny]]:
                        visited[state][nx][ny] = time + 1
                        stack.append((time+1,(nx,ny),state))
                elif arr[nx][ny] in lower_dict.keys():
                    visited[state][nx][ny] = time + 1
                    new_state = state | 1<< lower_dict[arr[nx][ny]]
                    visited[new_state][nx][ny] = time + 1
                    stack.append((time+1,(nx,ny),new_state))
                else:
                    if arr[nx][ny] == '1':
                        flag = False
                        result.append(time+1)
                        break
                    visited[state][nx][ny] = time + 1
                    stack.append((time+1,(nx,ny),state))
    if not flag:
        break

if flag:
    print(-1)
else:
    print(min(result))

그래프를 활용한 문제이다. 여기서 주의해야 할 점은 열쇠와 문을 열수 있는 상태를 구분하는것이다.

이 상태를 구분하기 위해 비트마스킹을 이용했다.

현재 상태에서 키가 있는 위치에 도착을 하면 OR 연산을 해서 key를 업데이트 해주고,

그리고 문에 도착을 하면 현재상태와 AND 연산을 해서 True가 되면, 현재 문에 대응하는 열쇠를 소유하는 것으로 판별을 해서 지나갈수 있도록 만들어 주었다.

문제에서 문과 열쇠는 A~F,a~f 밖에 없으므로,

2**0 ~ 2**5 까지로 각각 a~f,A~F를 매핑시켜주면 된다.

그리고 이 전체 state의 크기는 64개이므로, visited 배열을 64*(N*M)의 크기로 미리 만들어둔다.

그리고 그 외에는 일반적인 BFS와 동일하게 해주면 된다.

이 문제는 비트 마스킹을 통해 현재 가지고 있는 키의 상태를 업데이트 해주고, 문에 도착했을때, 이 문에 대응하는 키를 소유하고 있는지를 구분해주면 되는 문제였다.

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