Coding 공부

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
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
 
def connect(r1,r2):
    if (r1['x1'] > r2['x1'] and r1['y1'] > r2['y1']   and r1['x2'] < r2['x2']  and r1['y2'] < r2['y2']):
        return False
    if (r1['x1'] < r2['x1'] and r1['y1'] < r2['y1']   and r1['x2'] > r2['x2']  and r1['y2'] > r2['y2']):
        return False
    if (r2['x1'] > r1['x2'] or r2['x2'] < r1['x1'] or r2['y1'] > r1['y2'] or r2['y2'] < r1['y1']):
        return False
    return True
N = int(input())
 
rect = [{
        'x1' : 0,
        'x2' : 0,
        'y1' : 0,
        'y2' : 0
    }]
for _ in range(N):
    x1,y1,x2,y2 = map(int,input().split())
    rect.append({
        'x1' : x1,
        'x2' : x2,
        'y1' : y1,
        'y2' : y2
    })
make_set = [i for i in range(N+1)]
ranks = [1 for _ in range(N+1)]
 
 
for i in range(N+1):
    for j in range(N+1):
        if i != j and connect(rect[i],rect[j]):
            if find_parents(i) != find_parents(j):
                union(i,j)
 
 
for ind in range(N):
    find_parents(ind)
 
 
print(len(set(make_set))-1)

어려웠던 문제였다. 이 문제를 푸는 방법은 사각형끼리 겹쳐있는지 아닌지를 판별을 해주고, 안 겹친 사각형이 총 몇개인지 세면 되는 문제였다.

단 거북이는 0,0 부터 시작하므로 0,0,0,0 으로 된 사각형이 있다고 가정하에 union find를 진행해주면 되는 문제였다.

import sys
def input():
    return sys.stdin.readline().rstrip()
N,M,R = map(int,input().split())
arr = [0] + list(map(int,input().split()))
 
graph = [{} for _ in range(N+1)]
 
 
INF = float('inf')
distance = [[0 if i == j else INF for j in range(N+1)] for i in range(N+1)]
for _ in range(R):
    x,y,pay = map(int,input().split())
    graph[x][y] = min(graph[x].get(y,float('inf')), pay)
    graph[y][x] = min(graph[y].get(x, float('inf')),pay)
    distance[x][y] = min(distance[x][y],pay)
    distance[y][x] = min(distance[y][x],pay)
 
value = [0 for _ in range(N+1)]
for mid in range(1,N+1):
    for start in range(1,N+1):
        for end in range(1,N+1):
            if distance[start][end] > distance[start][mid] + distance[mid][end]:
                distance[start][end] =  distance[start][mid] + distance[mid][end]
 
 
result = 0
for node in range(1,N+1):
    temp = 0
    for next_node in range(1,N+1):
        if distance[node][next_node] <= M:
            temp += arr[next_node]
    if temp > result:
        result = temp
print(result)

이 문제는 플로이드와샬을 통해 최단거리를 갱신해주고, 

N^2를 탐색하면서, 거리가 M 이하일때 더해줘서 최대값을 갱신해서 출력해주는 문제이다.

import sys
 
 
def input():
    return sys.stdin.readline().rstrip()
 
 
def find_parents(ind):
    if make_set[ind] == ind:
        return ind
    make_set[ind] = find_parents(make_set[ind])
    return make_set[ind]
 
def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)
    if ranks[X] < ranks[Y]:
        X,Y = Y,X
    make_set[Y] = X
    if ranks[X] == ranks[Y]:
        ranks[X] += 1
 
 
N,M = map(int,input().split())
 
arr = [0] + list(input().split())
weight_list = []
for _ in range(M):
    x,y,pay = map(int,input().split())
    if arr[x] != arr[y]:
        weight_list.append((pay,x,y))
 
weight_list.sort(reverse=True)
make_set = [i for i in range(N+1)]
ranks = [1 for _ in range(N+1)]
 
cnt = 0
result = 0
while weight_list:
    pay,x,y = weight_list.pop()
    X,Y = find_parents(x), find_parents(y)
 
    if X != Y:
        union(X,Y)
        cnt += 1
        result += pay
    if cnt == N-1:
        break
 
if cnt != N-1:
    print(-1)
else:
    print(result)

이 문제는 처음부터 간선을 저장할때 두 노드가 남초+여초인 조합인 경우에만 저장을 해서 크루스칼을 해주면 된다.

그리고 크루스칼을 진행하고, 전체 cnt의 개수가 N-1이 안되는 경우에는 전부 연결이 안되는 경우이니 -1을 출력해주고

같을 때에는 result를 출력해주면 된다.

def Innerbound(x,y):
    if 0<=x<N and 0<=y<M:
        return True
    else:
        return False
 
def dfs(idx,bit,total):
    global result
    if bit == 2**(N*M)-1:
        result = max(result,total)
        return
    else:
        if 2**idx&bit:
            dfs(idx+1,bit,total)
        else:
            x,y = idx//M, idx%M
            nx,ny = x,y
            temp_bit = bit
            temp_num = 0
            while Innerbound(nx,ny):
                if visited[nx][ny]:
                    next_idx = nx*M + ny
                    visited[nx][ny] = False
                    temp_bit = temp_bit|(2**next_idx)
                    temp_num = temp_num*10 + arr[nx][ny]
                    nx = nx + 1
                    ny = ny
                else:
                    break
            for rx in range(nx-1,x-1,-1):
                dfs(idx+1,temp_bit,total + temp_num)
                temp_num = temp_num//10
                next_idx = rx*M + y
                temp_bit = temp_bit^(2**next_idx)
                visited[rx][y] = True
            nx,ny = x,y
            temp_bit = bit
            temp_num = 0
            while Innerbound(nx,ny):
                if visited[nx][ny]:
                    next_idx = nx*M + ny
                    visited[nx][ny] = False
                    temp_bit = temp_bit|(2**next_idx)
                    temp_num = temp_num*10 + arr[nx][ny]
                    nx = nx
                    ny = ny + 1
                else:
                    break
            for ry in range(ny-1,y-1,-1):
                dfs(idx+1,temp_bit,total + temp_num)
                temp_num = temp_num//10
                next_idx = x*M + ry
                temp_bit = temp_bit^(2**next_idx)
                visited[x][ry] = True
 
 
N,M = map(int,input().split())
 
arr = [list(map(int,list(input()))) for _ in range(N)]
 
visited = [[True for _ in range(M)] for _ in range(N)]
result = 0
dfs(0,0,0)
print(result)

처음에 모든 경우들을 각각 하나씩 그려보면서 dfs를 해주었다.

가로 혹은 세로로 최대한 세울 수 있는 직사각형을 그려주고 그때부터 dfs를 하고 하나씩 내려주면서 dfs를 해주었다.

이 방식은 오래걸리는 방식이였고, 다른 사람들의 풀이를 보고 다시 푼 방식은 다음과 같다.

N,M = map(int,input().split())
 
arr = [list(map(int,list(input()))) for _ in range(N)]
result = 0
# 0은 가로인걸로 1은 세로인걸로 판별
for bit_shape in range(2**(N*M)):
    total_sum = 0
    for x in range(N):
        sub_sum = 0 # 작은 단위의 SUM
        for y in range(M):
            idx = x*M + y
            if not bit_shape & (1<<idx):
                sub_sum = sub_sum*10 + arr[x][y]
            else:
                total_sum += sub_sum
                sub_sum = 0
        total_sum += sub_sum
    
    for y in range(M):
        sub_sum = 0
        for x in range(N):
            idx = x*M + y
            if bit_shape & (1<<idx):
                sub_sum = sub_sum*10 + arr[x][y]
            else:
                total_sum += sub_sum
                sub_sum = 0
        total_sum += sub_sum
    result = max(result,total_sum)
print(result)

이 방식은 모든 경우를 먼저 구하는 거다. 이 문제는 최대 16개의 칸을 가지는 것이다.

이것을 비트로 표현해서 0이면 가로로 그려진 직사각형 1이면 세로인 직사각형으로 구분을 해주는것이다.

그러면 우리는 2**(N*M)의 경우의 수를 가질수 있다. 최대 65536가지이므로, 빠르게 구할 수 있다.

비트로 현재 종이조각의 상태를 구분하고, 그 상태에 맞게 숫자를 세서 최대값을 구하면 된다.

import sys
 
def input():
    return sys.stdin.readline().rstrip()
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
        return True
    return False
 
def find_parent(ind):
    if make_set[ind] == ind:
        return ind
    else:
        make_set[ind] = find_parent(make_set[ind])
        return make_set[ind]
 
def kruskal():
    value = 0
    for p,x,y, in weight_list:
        if union(x,y):
            value += 1^p
    return value
 
 
N,M = map(int,input().split())
weight_list = []
for _ in range(M+1):
    x,y,p = map(int,input().split())
    weight_list.append((p,x,y))
make_set = list(range(N+1))
rank = [1]*(N+1)
weight_list.sort()
a = kruskal()
weight_list.sort(reverse=True)
make_set = list(range(N+1))
rank = [1]*(N+1)
b = kruskal()
print(a**2-b**2)

이 문제는 크루스칼을 활용해서 풀면 되는 문제이고, 크루스칼에 사용되는 간선을 오름차순과 내림차순으로 각각 정렬해서 

그때 크루스칼을 해서 값을 구한뒤 제곱값을 빼주면딘다.

import sys
from collections import defaultdict
def input():
    return sys.stdin.readline().rstrip()
def path(s,e):
    if next_node[s][e] == None:
        return [0]
    else:
        result = [s]
        while s != e:
            s = next_node[s][e]
            result.append(s)
        return result
N = int(input())
M = int(input())
INF = float('inf')
distance_list = [[0 if i==j else INF for j in range(N+1)] for i in range(N+1)]
 
next_node = [[None for _ in range(N+1)] for _ in range(N+1)]
graph = [{} for _ in range(N+1)]
for _ in range(M):
    x,y,pay = map(int,input().split())
    if distance_list[x][y] > pay:
        distance_list[x][y] = pay
        next_node[x][y] = y
 
 
for mid in range(1,N+1):
    for start in range(1,N+1):
        for end in range(1,N+1):
            if distance_list[start][end] > distance_list[start][mid] + distance_list[mid][end]:
                distance_list[start][end] = distance_list[start][mid] + distance_list[mid][end]
                next_node[start][end] = next_node[start][mid]
 
 
for i in range(1,N+1):
    print(*[val if val != INF else 0 for val in distance_list[i][1:]])
 
 
for start in range(1,N+1):
    for ends in range(1,N+1):
        if distance_list[start][ends] == INF:
            print(0)
        else:
            answer = path(start,ends)
            if len(answer) == 1:
                print(0)
            else:
                print(len(answer),*answer)

플로이드 와샬을 이용해서 풀어야하는데

여기서 중요한 점은 이동지점을 추적해야한다.

그 방법은 start-> end까지 갈때 들리는 노드를 갱신을 해주는 것이다.

a->b로 갈때 b로 간다고 저장을 해놨을때

중간에 값을 갱신한 mid가 있으면

a->b에 b가 아닌 mid를 저장해준다.

이렇게 함으로서

end_node가 동일한 것이 나올때까지 계속 반복을 해주면 되는 것이다.

플로이드 와샬은 자주 사용했지만, 경로를 구해본적은 처음이여서 힘들었다.

이 부분은 외우고 나중에 사용할 수 있도록 노력해야겠다.

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
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
    return False
 
 
T = int(input())
 
 
for tc in range(1,T+1):
    N = int(input())
    make_set = [i for i in range(N)]
    ranks = [1 for _ in range(N)]
 
    for _ in range(int(input())):
        x,y = map(int,input().split())
        union(x,y)
    print(f'Scenario {tc}:')
    for _ in range(int(input())):
        x,y = map(int,input().split())
        if find_parents(x) != find_parents(y):
            print(0)
        else:
            print(1)
 
    if tc != T:
        print()

전형적인 분리집합 문제였다.

들어오는 입력대로 union을 해주었고, 서로의 부모가 다를시에는 0 같을 시에는 1이 출력되게 했다.

import sys
from collections import deque
def input():
    return sys.stdin.readline().rstrip()
 
def pop(queue,flag):
    if flag:
        return queue.pop()
    else:
        return queue.popleft()
T = int(input())
 
for _ in range(T):
    commands = list(input())
    N = int(input())
    if N:
        arr = deque(input().replace('[','').replace(']','').split(','))
    else:
        input()
        arr = deque()
    # 0 정방향 1 역방향
    flow = 0
    flag = True
    for command in commands:
        if command == 'R':
            flow = (flow+1)%2
        else:
            if arr:
                pop(arr,flow)
            else:
                flag = False
                break
    if flag:
        if flow:
            arr.reverse()
        print(f'[{",".join(arr)}]')
    else:
        print('error')

이 문제는 deque를 통해, 역방향인지 정방향인지에 따라 나눠서 결정을 지으면 되는 문제였다.

정방향인지 역방향인지에 따라 pop을 하는 위치를 바꿔주고, 최종 결과를 출력을 할때에도, 구분을 해줬다.