Coding 공부

import sys
from collections import deque
def input():
    return sys.stdin.readline().rstrip()


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


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

sand_deque = deque()

dx = [-1,0,1,-1,1,-1,0,1]
dy = [-1,-1,-1,0,0,1,1,1]
for x in range(N):
    for y in range(M):
        if not arr[x][y].isdigit():
            sand_deque.append((x,y))
        else:
            arr[x][y] = int(arr[x][y])



time = 0

while True:
    remove_sand = deque()

    while sand_deque:
        x,y = sand_deque.popleft()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if not (0<=nx<N and 0<=ny<M):continue
            if arr[nx][ny] != '.':
                arr[nx][ny] -= 1
                if arr[nx][ny] == 0:
                    remove_sand.append((nx,ny))
                    arr[nx][ny] = '.'
    if remove_sand:
        sand_deque.extend(remove_sand)
        time += 1
    else:
        break

print(time)

처음에 dict을 이용해서 날먹할려다가 시간초과가 났던 문제이다.

문제를 푸는 방식은 다음과 같다. 모든 모래들은 하나의 큐에 넣은 뒤에, 8방향의 모래가 아닌곳의 개수를 -1씩 해준다.

그러면서 0이 되면, remove_sand라는 큐에 넣어준다.

그러면 이 모래성이 더이상 무너지지 않는 경우는 remove_sand가 비어있을때이다.

그래서 remove_sand가 비어있으면 break를 해주고, 있을때에는 sand_deque에 extend 해주고 그 때 time을 1 늘려준다.

import sys
from collections import deque
def input():
    return sys.stdin.readline().rstrip()


def bfs(queue):
    dx = [-1,0,1,-1,1,-1,0,1]
    dy = [-1,-1,-1,0,0,1,1,1]
    while queue:
        x,y,cnt = queue.popleft()

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

    return cnt

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


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


sand_deque = deque()
for x in range(N):
    for y in range(M):
        if arr[x][y].isdigit():
            arr[x][y] = int(arr[x][y])
        else:
            arr[x][y] = 0
            sand_deque.append((x,y,0))



print(bfs(sand_deque))

 이 코드는 좀 더 깔끔한 방식으로 코드를 바꾼 방식이다.

원리 자체는 똑같다.    

import sys

def input():
    return sys.stdin.readline().rstrip()
def find_parents(X):
    if X == make_set[X]:
        return X
    make_set[X] = find_parents(make_set[X])
    return make_set[X]


def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)

    if X !=Y:
        if ranks[X]< ranks[Y]:
            X,Y = Y,X
        make_set[Y] = X
        groups[X].extend(groups[Y])
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
    return False
N,M = map(int,input().split())


edge_list = []
total_pay = 0
for _ in range(M):
    x,y,pay = map(int,input().split())
    if x>y:
        x,y = y,x
    edge_list.append((x,y,pay))
    total_pay += pay
K = 10**9
past_pay = 0
answer = 0
make_set = [i for i in range(N+1)]
ranks = [1 for _ in range(N+1)]
groups = [[k] for k in range(N+1)]
edge_list.sort(key=lambda x : x[2])
while edge_list:
    x,y,pay = edge_list.pop()
    p_x,p_y = find_parents(x),find_parents(y)
    if p_x!= p_y:
        answer = answer + len(groups[p_x])*len(groups[p_y])*(total_pay-past_pay)
        answer = answer%K
        union(x,y)
    past_pay += pay
print(answer)

구사과님의 분리집합 추천 문제에 있어서, 풀었던 문제였는데 푸는데 어려웠던 문제였다. 

이 문제는 분리집합만을 이요해 푸는 문제인데, 푸는 아이디어는 다음과 같다.

모든 간선이 연결이 끊어져 있다고 생각을 하고, 간선의 비용이 가장 많은 비용 순으로 연결을 해주는 것이다.

문제에 주어진 Cost(u,v)는 u,v가 연결이 안될때까지 최소비용의 간선을 제거해주는 것이다.

즉 역으로 생각하면  간선의 비용이 가장 많은 비용 순으로 연결을 해줄때, 처음 u,v가 같은 집합이 되면,

그 전까지 연결된 비용을 제외한 나머지 비용들이, 이 u,v의 Cost가 될 수 있다.

즉 전체 간선의 연결비용을 구한 상태에서 비용이 높은 순으로 연결을 해주면서 연결이 되었을때 까지의 누적 비용을

뺀 값이 해당 cost(u,v)인 것을 알 수 있게 된다.

그러면 여기서 고민사항은 다음과 같다.

서로 단독집합일때에는 위와 같이 한다고 할때, 만약에 서로 다른 집합에 이미 속해있는 상황에서는 어떻게 해야할지, 

일 것이다.

이 문제는 문제에서 cost(u,v)에서 u<v 이므로, 우리는 한가지 정보를 더 저장을 시켜줘야한다.

그것은 부모에 해당 집합에 속해있는 노드를 저장시켜놓는것이다.

그래서 우리는 각 부모들에 노드를 저장시켜주고, 그 노드의 수를 서로 곱해주면 두 집합에서 나올 수 있는

u,v의 집합의 개수와 동일 하다.

정리하면

(total_pay - past_pay) *len(group[parent_u]) *len(group[parent_v]) 로 나타낼수 있다.

위의 코드를 통해 AC를 받을 수 있었다. 이 문제의 아이디어를 떠오르는데 힘들었고, 구현을 하는데 어려움이 많았다.

아직 분리집합에 대해 잘 모르고, 응용하는법에 대해 잘 몰랐다는 것을 알게 되었다.

import sys

def input():
    return sys.stdin.readline().rstrip()
def find_parents(X):
    if X == make_set[X]:
        return X
    make_set[X] = find_parents(make_set[X])
    return make_set[X]


def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)

    if X !=Y:
        if ranks[X]< ranks[Y]:
            X,Y = Y,X
        make_set[Y] = X
        groups[X] +=groups[Y]
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
    return False
N,M = map(int,input().split())


edge_list = []
total_pay = 0
for _ in range(M):
    x,y,pay = map(int,input().split())
    if x>y:
        x,y = y,x
    edge_list.append((x,y,pay))
    total_pay += pay
K = 10**9
past_pay = 0
answer = 0
make_set = [i for i in range(N+1)]
ranks = [1 for _ in range(N+1)]
groups = [ 1 for _ in range(N+1)]
edge_list.sort(key=lambda x : x[2])
while edge_list:
    x,y,pay = edge_list.pop()
    p_x,p_y = find_parents(x),find_parents(y)
    if p_x!= p_y:
        answer = answer + groups[p_x]*groups[p_y]*(total_pay-past_pay)
        answer = answer%K
        union(p_x,p_y)
    past_pay += pay
print(answer)

이 코드는 노드를 전부 저장하는게 아닌, 노드의 개수를 저장해주는 방식으로 바꾼 코드이다.

import sys

def input():
    return sys.stdin.readline().rstrip()

T = int(input())
dp = [i for i in range(101)]

for i in range(100):
    for coin in [10,25]:
        if i +coin > 100:continue
        dp[i+coin] = min(dp[i+coin],dp[i]+1)
for _ in range(T):
    N = int(input())

    answer = 0
    while N>0:
        answer += dp[N%100]
        N//=100
    print(answer)

이 문제는 100까지의 최소 코인의 개수를 구해준 뒤에, 100단위로 나눠주면서 그 개수를 더해주면 된다.

왜냐하면

이 문제에서 쓰이는 동전은 [1,10,25]로 되어있고

각 100^k 만 곱해진 동전이기 때문이다.

import sys
import heapq
def input():
    return sys.stdin.readline().rstrip()



def find_parents(X):
    if X == make_set[X]:
        return X
    make_set[X] = find_parents(make_set[X])
    return make_set[X]


def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)

    if X !=Y:
        if ranks[X]< ranks[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
    return False
N,M = map(int,input().split())

edge_list = []

for x in range(N):
    temp = list(input())
    for y in range(x+1,N):
        if temp[y] == 'Y':
            heapq.heappush(edge_list,(x,y))
city_cnt = 0
if len(edge_list) >= M:
    result = [0 for _ in range(N)]
    make_set = [i for i in range(N)]
    ranks = [1 for _ in range(N)]
    remain_list = []
    while edge_list:
        node_a,node_b = heapq.heappop(edge_list)
        if union(node_a,node_b):
            city_cnt += 1
            result[node_b] += 1
            result[node_a] += 1
        else:
            heapq.heappush(remain_list,(node_a,node_b))
    if city_cnt != N-1:
        print(-1)
    else:
        remain_cnt = M - city_cnt

        while remain_cnt>0:
            node_a,node_b = heapq.heappop(remain_list)
            result[node_a] += 1
            result[node_b] += 1
            remain_cnt -= 1
        print(*result)
else:
    print(-1)

이 문제는 문제를 이해하는데 힘들었고, 구현을 하는데 어려운 점이 많았었다.

평소에 MST 관련 문제는 프림 알고리즘을 주로 이용해서 풀었지만, 이 문제를 푸는데에는 크루스칼 알고리즘을 이용했다.

문제를 푸는 방식은 다음과 같다. 모든 간선들을 저장을 해주는데, 그 조건은 x,y 에서 y는 무조건 x보다 큰 경우의 간선만 저장을 시켜준다.

그래서 모든 간선을 저장시켰는데 주어진 M보다 적을때에는 -1을 출력을 해준다.

그리고 크루스칼 알고리즘을 이용해서 풀면된다.

그러나, 여기서 다른 점은 우리가 이미 union이 된 간선들을 버리게 되는데, 이걸 따로 저장을 시켜놓는다.

그리고 우리는 모든 크루스칼 알고리즘을 돌린뒤에, 모든 도시가 연결이 안되어있으면 -1을 출력을 해주고,

그리고 우리는 무조건 도로 M개를 무조건 연결을 해야하므로, 우리는 크루스칼 알고리즘을 통해 N-1개를 연결을 해놓은 상태이다.

그러므로 M-(N-1)개의 도로를 추가적으로 연결을 시켜주면 된다.

그래서 우리는 저장시켜놓은 도로들을 우선순위가 높은 것부터 뽑아서 연결을 시켜주면 된다.

import sys
from collections import deque
def input():
    return sys.stdin.readline().rstrip()



def find_parents(X):
    if X == make_set[X]:
        return X
    make_set[X] = find_parents(make_set[X])
    return make_set[X]


def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)

    if X !=Y:
        if ranks[X]< ranks[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
    return False
N,M = map(int,input().split())

edge_list = deque()
result = [0 for _ in range(N)]
make_set = [i for i in range(N)]
ranks = [1 for _ in range(N)]

city_cnt = 0
for x in range(N):
    temp = list(input())
    for y in range(x+1,N):
        if temp[y] == 'Y':
            if union(x,y):
                city_cnt += 1
                result[x] += 1
                result[y] += 1
            else:
                edge_list.append((x,y))


if city_cnt<N-1 or city_cnt+len(edge_list)<M:
    print(-1)
else:
    remain_cnt = M - city_cnt

    while remain_cnt>0:
        x,y = edge_list.popleft()
        result[x] += 1
        result[y] += 1
        remain_cnt -= 1
    print(*result)

이건 코드를 좀 더 개선시킨 버전이다.

달라진것은 heapq 대신 그냥 앞에서부터 차근차근 해주는 방식으로 바꿔준 것이다.

이 문제는 크루스칼을 이용하는 것뿐만 아니라, 문제를 잘 분석해야 풀 수 있었떤 문제였다.

import sys
from collections import defaultdict
def input():
    return sys.stdin.readline().rstrip()


def dfs(cur_idx,parent_idx):
    global cnt
    depth[cur_idx] = depth[parent_idx] + 1


    if tree[cur_idx][0] != -1:
        dfs(tree[cur_idx][0],cur_idx)
    cnt += 1
    width[depth[cur_idx]].append(cnt) 
    if tree[cur_idx][1] != -1:
        dfs(tree[cur_idx][1],cur_idx)

N = int(input())
root_check = [0 for _ in range(N+1)]
tree = [[-1 -1] for _ in range(N+1)]
depth = [0 for _ in range(N+1)]
width = defaultdict(list)
for _ in range(N):
    x,left_node,right_node = map(int,input().split())
    tree[x] = [left_node,right_node]
    if left_node != -1:
        root_check[left_node] += 1
    if right_node != -1:
        root_check[right_node] += 1
root_num = -1
for k in range(1,N+1):
    if root_check[k] == 0:
        root_num = k
        break


cnt = 0
dfs(root_num,0)

max_value = 0
max_depth = -1
for d in range(1,max(depth)+1):
    max_width,min_width = max(width[d]),min(width[d])
    if max_value < max_width - min_width + 1:
        max_value = max_width - min_width + 1
        max_depth = d

print(max_depth,max_value)

이 문제를 풀때 주의할점은 2가지이다.

루트노드가 꼭 1인것은 아니다.

들어오는 순서가 1,2,3,4,5,6,7,8,....N이 아닐수도 있다.

이 2가지를 주의하면 풀면 되는 문제이다.

먼저 트리를 위한 (N+1)*2의 배열을 만들어뒀다.

각 행의 0번인덱스는 왼쪽 자식, 1번인덱스는 오른쪽자식을 의미한다.

이 문제는 중위순회를 구현을 해서, 왼쪽 자식->루트->오른쪽자식 순서로 탐색을 해준다.

그리고 루트일때 현재의 LEVEL에 width를 저장을 해주엇다.

cnt를 0부터 시작했기때문에, append 하기 직전에 +=1 을 해준것이다.

만약 1부터 하신분들은 순서를 바꾸면될것이다.

그리고 전체 레벨 만큼 탐색을하면서 최대 너비를 구해주면 되는 문제이다.

좀 더 깔끔히 하신분들은 level별로 2차원배열을 만든뒤에 둘 중 하나는 최대값 하나는 최소값을 저장을 시켜서 

마지막에 바로 계산이 가능하게 한 분들도 계신다.

import sys
sys.setrecursionlimit(20000)
def input():
    return sys.stdin.readline().rstrip()
def trace(cur_node,prev_check):
    visited[cur_node] = False
    flag = 0
    if not prev_check:
        if dp[cur_node][0] < dp[cur_node][1]:
            result.append(cur_node)
            flag = 1
    for next_node in graph[cur_node]:
        if visited[next_node]:
            trace(next_node,flag)

def dfs(node):
    visited[node] = False
    child_node = []
    for next_node in graph[node]:
        if visited[next_node]:
            child_node.append(next_node)
    if not len(child_node):
        dp[node][1] = arr[node]

        return
    else:
        dp[node][1] += arr[node]
        for child in child_node:
            dfs(child)
            dp[node][0] += max(dp[child][1],dp[child][0])
            dp[node][1] += dp[child][0]



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

# 1이 선택 
# 0이 선택 x
dp = [[0 for _ in range(2)] for _ in range(N+1)]

graph = [[] for _ in range(N+1)]
visited = [True for _ in range(N+1)]
for k in range(N-1):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)


dfs(1)

print(max(dp[1]))


result = []
visited = [True for _ in range(N+1)]
trace(1,0)
result.sort()
print(*result)

어려웠던 문제였다. 트리dp를 활용해서 최적의 경우를 찾는 것은 많았지만, 그 최적을 만족하는 것을 trace를 하는 문제는 처음이라 푸는데 오래걸렸다.

dp라는 테이블을 만들고 (N+1)*2의 배열을 만들어 두었다.

여기서 1은 해당 노드를 선택했을때의 최대값

0은 해당 노드를 선택하지 않았을때의 최대값이다.

만약 리프노드이면 자신을 선택하는 조건이외에는 없을것이다.

그러므로 dp[leef_node][1] = arr[leef_node]를 넣어준다.

리프노드를 제외한 나머지 노드들은 0번 인덱스와 1번인덱스의 최대값을 구해야한다.

현재 노드를 선택했을때 즉 1번인덱스에는

현재 노드를 cur_node라고 했을때 arr[cur_node]를 더해줘야할것이다.

그리고 현재 노드를 선택했으므로, 자식노드들은 선택을 하지 못한다.

그러므로 dp[cur_node][1] += dp[child_node][0] 와 같이

자식 노드들의 선택하지않았을때의 값들을 전부 더해줘야한다.

그리고 현재 노드를 선택하지 않았을때에는

자식 노드를 선택하던지, 선택하지 않는것은 마음대로 할 수 있다.

그러므로 둘중 더 큰 값을 더해주면 된다.

이렇게 dp에 값을 누적시켜서 구하면

우리는 1번노드로 시작했기 때문에

1번노드의 dp에서 최대값을 구할 수 있다.

그러면 우리는 이 dp에서 어떤 노드들이 선택됬는지를 찾아봐야한다.

우리는 이전 노드에서 선택했는지 안했는지에 따라, 현재 노드를 선택할수 있는지 아닌지가 결정이 된다.

그래서 우리는 prev_check를 통해 문제를 해결했다. 위와 동일하게 하기 위해서 0일때에는 부모노드를 선택하지 않았다.

1일때에는 부모노드를 선택했다이다.

만약 부모노드를 선택하지 않았을때에는, 우리는 지금 있는 현재노드를 선택할지 안할지를 결정지을수 있다.

그 결정방법은 dp에 저장된 값을 비교를 해서, 우리가 선택하지 않았을때보다 선택했을때의 값이 더 크면,

그때 현재노드를 선택을 하고, flag를 1로 바꿔준다. 현재노드를 선택을 했으므로, result에 추가 시켜준다.

그리고 재귀를 통해 모든 노드들에 대해 탐색을 해주면 된다.

이 문제는 최대값을 구하는 것 뿐만 아니라, 그 경우의 수가 만들어지는 것을 찾는데 더 어려움을 겪었다.

트리 dp와 관련된 문제들을 좀 더 연습해야겠다.

import sys
import heapq
def convert_Numner(x):
    global total_sum,INF
    if x.islower():
        num = ord(x) - ord('a') + 1
        total_sum += num
    elif x.isupper():
        num = ord(x) - ord('A')+ 27
        total_sum += num
    else:
        num = INF
        total_sum += 0
    return num


def input():
    return sys.stdin.readline().rstrip()


N = int(input())


total_sum = 0
INF = float('inf')
arr = [list(map(convert_Numner,list(input()))) for _ in range(N)]


cnt = 0
mst_dis = 0
distance_list = [INF for _ in range(N)]
visited = [False for _ in range(N)]
node_list = []

heapq.heappush(node_list,(0,0))
distance_list[0] = 0
while node_list:
    cur_dis,cur_node = heapq.heappop(node_list)
    if visited[cur_node]:continue
    cnt += 1
    mst_dis += cur_dis
    visited[cur_node] = True
    for next_node in range(N):
        if visited[next_node]:continue
        min_value = min(arr[cur_node][next_node],arr[next_node][cur_node])
        if distance_list[next_node] > min_value:
            distance_list[next_node] = min_value
            heapq.heappush(node_list,(min_value,next_node))

if cnt == N:
    print(total_sum-mst_dis)
else:
    print(-1)

처음에 프림알고리즘으로 풀었다. MST에서 익숙한 알고리즘이 프림알고리즘이라, 우선적으로 푼 방식이다.

여기서 여러번 틀렸었는데 그 이유는 다음과 같다. 우리가 연결을 하는 통로는 무방향이다.

즉 1번방에서 2번방으로 연결하는 랜선과 2번방에서 1번방으로 연결하는 랜선은 둘중 하나만 선택을 하면, 둘이 연결이 된것으로 본다.

이 문제를 풀때 무조건 0번방부터 시작을 했기때문에

3

zzz

abc

abc

와 같은 입력이 들어왔을때, 오히려 더 짧은 반대편방에서 오는 경우를 체크하지 못했다.

이러한 문제점을 해결하기 위해, 거리를 비교할때, 양방향의 최소값으로 비교를 하고, 그값을 넣어주는 방식으로 했다.

이런식이 아니라, 처음부터 graph라는 딕셔너리를 만들어서 최소값을 저장해주어도 된다.

이 점만 주의하면, 나머지는 일반적인 프림알고리즘을 이용한 MST 문제이다.

cnt개수가 N보다 부족할시에는 모든 노드들이 연결이 된것이 아니므로, -1을 출력해주면 된다.

import sys
def convert_Numner(x):
    global total_sum,INF
    if x.islower():
        num = ord(x) - ord('a') + 1
        total_sum += num
    elif x.isupper():
        num = ord(x) - ord('A')+ 27
        total_sum += num
    else:
        num = INF
        total_sum += 0
    return num


def find_parents(X):
    if X == make_set[X]:
        return X
    make_set[X] = find_parents(make_set[X])
    return make_set[X]


def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)

    if X !=Y:
        if ranks[X]< ranks[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
    return False

def input():
    return sys.stdin.readline().rstrip()

N = int(input())


total_sum = 0
INF = float('inf')


edge_list = []
for x in range(N):
    input_string = input()
    temp = []
    for y in range(N):
        num = convert_Numner(input_string[y])
        if x == y:continue
        if num == INF:continue
        edge_list.append((num,x,y))
edge_list.sort(reverse=True)
cnt = 1
result = 0
make_set = [i for i in range(N)]
ranks = [1 for _ in range(N)]
while cnt <N and edge_list:
    pay,node_a,node_b = edge_list.pop()
    if union(node_a,node_b):
        cnt += 1
        result += pay


if cnt == N:
    print(total_sum-result)
else:
    print(-1)

크루스칼을 이용한 풀이이다. 푸는 방법은 위와 동일하다 대신 edge_list에 x와 y가 같은경우와 연결이 되지않는 경우는 제외시켰다.

import sys

def input():
    return sys.stdin.readline().rstrip()

def check_pick(pick_list,point):
    x,y = point
    for nx,ny in pick_list:
        if abs(nx-x) == abs(ny-y):
            return False
    return True

def dfs(problem_list,start,pick_list,color):
    global result
    if len(problem_list) == start:
        result[color] = max(result[color],len(pick_list))
        return
    else:

        for idx in range(start,len(problem_list)):
            x,y = problem_list[idx]
            if check_pick(pick_list,(x,y)):
                dfs(problem_list,idx+1,pick_list+[(x,y)],color)


N = int(input())


arr = [list(map(int,input().split())) for _ in range(N)]

result = 0
black_set = []
white_set = []
for x in range(N):
    for y in range(N):
        if arr[x][y]:
            if (x+y)%2:
                white_set.append((x,y))
            else:
                black_set.append((x,y))

result = [0,0]
dfs(black_set,0,[],0)
dfs(white_set,0,[],1)

print(sum(result))

문제를 푼 아이디어는 다음과 같다. 체스판은 흰색판과 검은색판으로 나뉘어져있다. 그리고 비숍이 잡아 먹을수 있는 위치는 같은 색깔에 있는 위치의 비숍일 뿐이다. 그러므로, 흰색과 검은색으로, 좌표를 나눠서, 각각 놓을 수 있는 최대 위치를 찾아주면 된다.

# chw0501님 코드 복기

import sys

def input():
    return sys.stdin.readline()

def dfs(left_slash_num):
    if visited[left_slash_num]:
        return 0 
    visited[left_slash_num] = True

    for right_slash_num in slash_dict[left_slash_num]:
        if right_slash[right_slash_num] == -1 or dfs(right_slash[right_slash_num]):
            left_slash[left_slash_num] = right_slash_num
            right_slash[right_slash_num] = left_slash_num
            return 1
    return 0

N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
right_slash = [-1 for _ in range(2*N+1)]
left_slash = [-1 for _ in range(2*N+1)]
slash_dict = [[] for _ in range(2*N+1)]
for x in range(N):
    for y in range(N):
        if arr[x][y]:
            slash_dict[x+y].append(x-y+N)


result = 0
for left_slash_num in range(2*N):
    visited = [False for _ in range(2*N)]
    if dfs(left_slash_num):
        result += 1
print(result)

더 빨리 풀 수 있는 코드는 대각선으로 나눠서 하는 방법인데 거기서 깔끔한 코드였던 chw0501님의 코드를 복기한 코드이다.

이 문제를 푸는방법은 다음과 같다. 한 위치에 비숍이 위치하면, 이 비숍의 X자 대각선으로는 다른 비숍들을 둘수 없다.

그렇다면, 흰색, 검은색으로만 나누지 말고, 대각선 위치를 기준으로 나눠 보는건 어떨까 라는 아이디어에서 출발된 것이다.

대각선을 (2*N-1)개씩 두 종류로 나뉠수 있다.

먼저 right_slash라고 부를, 오른쪽 아래로 향하는 대각선 모양은 다음과 같이 총 2*N-1개가 있다.

그러면 같은 대각선에 있는지 확인하는 방법은 행을 X 열을 Y로 했을때 (X-Y+N)으로 표현할 수 있다.

그리고 이렇게 좌측 아래로 향하는 슬래쉬를 left_slash라고 하겠다 이것도 위와 동일하게 2*N-1개가 생성되면

같은 집단인지 판별하는 방법은 (X+Y)이다.

그러면 우리는 해당 칸이 놓을수 있는 자리이면, left_slash를 구하고, 그 left_slash내에 해당 좌표의 right_slash 정보를 같이 집어넣어준다.

즉 slash_dict의 key 값은 left_slash의 좌표값이 되고, right_slash가 value가 되도록 넣어주면 된다.

이렇게 사전작업을 해놓은 상태에서 우리는 2개의 slash_list를 만들어놓는다.

각각 left_slash 와 right_slash로

해당의 index는 slash의 몇번째 위치에 있는지를 나타내며, 그 안의 value 값은 서로 반대편의 슬래쉬의 위치를 표시를 해주는 용도이다.

즉 left_slash의 3번째 위치에 5라는 값이 있으면,

3번째 left_slash에 있는 어떠한 점 중 하나를 골랐고, 그 점은 right_slash를 5를가지고 있다.를 의미한다.

즉 특정한 점을 만들 수 있는 것이다.

그러면 우리는 left_slah의 좌측아래로 향하는 슬래쉬를 기준으로 dfs를 진행을 해주면 된다.

def dfs(left_slash_num):
    if visited[left_slash_num]:
        return 0 
    visited[left_slash_num] = True

    for right_slash_num in slash_dict[left_slash_num]:
        if right_slash[right_slash_num] == -1 or dfs(right_slash[right_slash_num]):
            left_slash[left_slash_num] = right_slash_num
            right_slash[right_slash_num] = left_slash_num
            return 1
    return 0

이 dfs가 중요한데 이 dfs에서는 기본적으로 다음과 같다.

우리가 입력받은 left_slash_num에 저장된 right_slash_num들을 하나씩 가져온다.

right_slash라는 list에서 초기값으로 있으면 그 자리에 비숍을 놓을 수 있는 것이니,

left_slash에는 right_slash_num을 저장해주고, right_slash에는 left_slash_num을 저장을 해준다.

그러나 만약 해당 right_slash에 특정한 left_slash_num이 저장이 되어있다면,

우리는 위치를 조정해서 다시 놓을 수 있는지 확인을 해주는 것이다.

우리가 A_right라는 right_slash를 찾아볼려고 했더니 right_slash[A_right]의 값이 -1이 아니였고, B_left라는 값이 있었으면,

우리는 DFS를 통해 B_left를 다시 들어가서 B_left안에 있는 다른 right_slash들을 검사를 해서 놓을 수 있는지 확인을 해주는 것이다.

B_left 안에 [A_right,B_right,C_right] 등이 있다고하면,

이 중에 아직 right_slash가 -1인 값이 있으면, 우리는 그 위치를 조정해서 다시 비숍을 놓을 수 있을것이다.

그러나 이러한 경우가 하나도 없다면 비숍을 놓을 수 없기 때문에 0을 반환을 해주고,

한번 방문했던 곳을 다시 방문을 했다는 것은 사이클이 발생하고, 더 비숍을 놓을 곳이 없는것을 의미하기 때문에 0을 반환을 해주면된다.

위와 같은 dfs를 실행을 하면서 1을 반환이 되면, result의 값을 1씩 늘려주고,

최종적으로 result를 출력을 해주면 된다.

말로서 설명하기에는 어렵지만 디버깅도구를 통해 따라가보면 금방 이해할 수 있었다.

두번째 풀이는 이해하기 어려웠지만, 다른 사람의 코드를 보고 이런 방식으로도 할 수 있는걸 알았다.

좀 더 효율적인 방법이 있다는 걸 알고, 다음번에는 이런 코드를 짤 수 있도록 노력해야겠다.