Coding 공부

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

def cycle_check(node,parent):
    if visited[node]:
        return node
    else:
        visited[node] = True
        for next_node in graph[node]:
            if next_node == parent:continue
            return_node = cycle_check(next_node,node)
            if return_node > 0:
                cycle_check_node[node] = True
                if return_node == node:
                    return 0
                else:
                    return return_node
        cycle_check_node[node] = False
        return 0
def dfs(start):
    stack = [(start,0,0)]
    visited = [True for _ in range(N+1)]
    while stack:
        node,parent,dis = stack.pop()

        if cycle_check_node[node]:
            distance[start] = dis
            return
        visited[node] = False

        for next_node in graph[node]:
            if next_node == parent:continue
            if visited[next_node]:
                stack.append((next_node,node,dis+1))



N = int(input())

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

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


visited = [False for _ in range(N+1)]
cycle_check_node = [False for _ in range(N+1)]
distance = [0 for _ in range(N+1)]

cycle_check(1,0)


for k in range(1,N+1):
    if not cycle_check_node[k]:
        dfs(k)


print(*distance[1:])

  처음 풀이는 생각나는대로 풀었다. 먼저 2가지 함수로 나눠서 했다.

처음은 cycle을 체크하는 함수이다. 어느 노드에서든지 시작을 해서, 한번 방문을 했던 노드가 나올때까지

부모노드를 제외한 자식노드를 탐색해간다. 그러다보면 cycle의 시작지점을 방문하게 되는데 이때,

우리는 해당 node의 번호를 리턴해준다. 그러면 우리는 return 된 값이 0보다 크면

이 노드는 사이클에 포함된 노드임을 알 수 있다. 그러므로 return이 된 값이 0보다 크면 cycle임을 체크해주고,

시작지점에 도착하면, return 된 node와 값이 같으므로, 그걸로 판별뒤, 그 뒤에는 0을 반환해주면 된다.

그러면 우리는 0이 반환이 되면, 해당 노드는 사이클이 아닌것을 알게 된다.

이렇게 cycle을 체크한 뒤에

dfs를 돌려 cycle을 최초로 만나는 지점까지의 거리를 구해서 저장해주면 된다.

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

def cycle_check(node,parent):
    if visited[node]:
        return node
    else:
        visited[node] = True
        for next_node in graph[node]:
            if next_node == parent:continue
            return_node = cycle_check(next_node,node)
            if return_node > 0:
                cycle_check_node[node] = True
                distance[node] = 0
                if return_node == node:
                    return 0
                else:
                    return return_node
        cycle_check_node[node] = False
        return 0
def dfs(start,parent):
    if distance[start] != INF:
        return distance[start]
    for next_node in graph[start]:
        if next_node == parent:continue
        distance[start] = min(dfs(next_node,start)+1,distance[start])

    return distance[start]

    



N = int(input())

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

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


visited = [False for _ in range(N+1)]
cycle_check_node = [False for _ in range(N+1)]
INF = float('inf')
distance = [INF for _ in range(N+1)]

cycle_check(1,0)

for k in range(1,N+1):
    if not cycle_check_node[k] and distance[k] == INF:
        dfs(k,0)

print(*distance[1:])

이 방식은 좀 더 깔끔한 코드이다. 모든 노드들을 dfs를 각각돌리는것이 아닌. cycle인 부분에서부터 1씩 거리를 늘리면서 하나씩 해주는 방식이다.

이 방식이 좀 더 깔끔한 방식이다.

from collections import defaultdict

N = int(input())

arr = list(input())

cnt_dict = defaultdict(int)
result = 0
prev_idx = -1
for idx in range(N):
    alpha = arr[idx]
    cnt_dict[alpha] = idx
    if len(cnt_dict) > N:
        min_idx = 100001
        min_key = -1
        for key in cnt_dict:
            if min_idx > cnt_dict[key]:
                min_idx = cnt_dict[key]
                min_key = key
        prev_idx = min_idx
        del cnt_dict[min_key]
    
    result = max(result,idx-prev_idx)
print(result)

전형적인 두 포인터 문제이고, 그걸 다른 방식으로 푼 것이다. 

defalutdict를 통해, 각 알파벳의 마지막 위치를 저장시켜주고,

그 길이가 N을 넘어서게 되면, 마지막 위치가 가장 작은 알파벳을 삭제해주는 방식으로 해주고

prev_idx를 갱신해준다

위와 같은 방식을 통해 문제를 풀어주면 된다.

   . 

import sys
import heapq

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


N = int(input())

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

node_list = []

INF = float('inf')
distance_list = [INF for _ in range(N)]
visited = [False for _ in range(N)]
heapq.heappush(node_list,(0,0))
distance_list[0] = 0
result = 0
while node_list:
    cur_dis,cur_node = heapq.heappop(node_list)
    if visited[cur_node]:continue
    if cur_dis > distance_list[cur_node]:continue
    result += cur_dis
    visited[cur_node] = True
    for next_node in range(N):
        if next_node == cur_node:continue
        if visited[next_node]:continue
        if distance_list[next_node] > graph[cur_node][next_node]:
            distance_list[next_node] = graph[cur_node][next_node]
            heapq.heappush(node_list,(distance_list[next_node],next_node))

print(result)

 프림 알고리즘

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



N = int(input())
edge_list = []
for x in range(N):
    temp = list(map(int,input().split()))
    for y in range(N):
        if x == y:continue
        edge_list.append((temp[y],x,y))


edge_list.sort(reverse=True)

cnt = 1
make_set = [i for i in range(N)]
ranks = [1 for _ in range(N)]
result = 0
while cnt <N:
    dis,node_a,node_b = edge_list.pop()
    if union(node_a,node_b):
        cnt += 1
        result += dis

print(result)

크루스칼 알고리즘

전형적인 MST 문제이다. MST 문제를 푸는 방식대로 풀면 된다.

import sys
from itertools import combinations
def input():
    return sys.stdin.readline().rstrip()


N = int(input())


arr = [list(map(int,input().split())) for _ in range(N)]
row = [sum(i) for i in arr]
col = [sum(i) for i in zip(*arr)]
new_arr = [i+ j for i, j in zip(row, col)]
total_sum = sum(new_arr)//2
result = float('inf')
for num in range(1,N//2+1):
    for combi in combinations(new_arr,num):
        result = min(result,abs(total_sum-sum(combi)))
        if result == 0:
            break
    if result == 0:
        break
print(result)

이 문제는 과거에 푼 boj.kr/14889 이 있었기 때문에 빨리 풀 수 있었다. 

기본 푼 방식은 원래와 똑같다. 각 col,row의 섬을 미리 구해놓고, 그걸 통해서 문제를 푸는 방식이다.

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 대신 그냥 앞에서부터 차근차근 해주는 방식으로 바꿔준 것이다.

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