Coding 공부

import sys
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,M = map(int,input().split())
 
 
dire = {
    "U": [-1,0],
    "L": [0,-1],
    "R" : [0, 1],
    'D': [1,0]
}
 
arr = [list(input()) for _ in range(N)]
make_set = [i for i in range(N*M)]
ranks = [1 for _ in range(N*M)]
 
 
for x in range(N):
    for y in range(M):
        point = x*M+y
        dx,dy = dire[arr[x][y]]
        next_point = (x+dx)*M+y+dy
        union(point,next_point)
 
result = 0
for x in range(N):
    for y in range(M):
        point = x*M+y
        if point == find_parents(point):
            result += 1
print(result)

 이 문제는 union find를 통해 집합이 몇개가 되는지 확인하면 된다.

그 방법은 현재 노드와 부모노드가 동일한 개수를 세주면 된다.

import sys
 
def input():
    return sys.stdin.readline().rstrip()
 
N,M = map(int,input().split())
 
 
dire = {
    "U": [-1,0],
    "L": [0,-1],
    "R" : [0, 1],
    'D': [1,0]
}
arr = [list(input()) for _ in range(N)]
visited = [[-1 for _ in range(M)] for _ in range(N)]
 
result = 0
for x in range(N):
    for y in range(M):
        if visited[x][y] != -1:
            continue
 
        point = x*M+y
        nx,ny = x,y
        while visited[nx][ny] == -1:
            visited[nx][ny] = point
            dx,dy = dire[arr[nx][ny]]
            nx = nx + dx
            ny = ny + dy
        if visited[nx][ny] == point:
            result += 1
print(result)

다르게 푸는 방식은 visited를 만들어놓고 같은 point가 되는 지점에 돌아왔을때 result + 1 해주는 것이다.

안전지대가 된다는 것은 한 지점에서 출발했다가 원래지점으로 돌아온다는것을 뜻하므로, 그 조건을 만족하는 개수를 세주면 된다.

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
input = sys.stdin.readline
 
 
G = int(input())
P = int(input())
result = 0
plane = [int(input()) for _ in range(P)]
 
 
parents_number = [i for i in range(G+1)]
 
visited = [False]*(G+1)
cur_idx = 0
planing = True
 
while cur_idx<P and planing:
 
    cur_plane_number = plane[cur_idx]
    check = [cur_plane_number]
    while visited[cur_plane_number] and cur_plane_number>0:
        cur_plane_number = parents_number[cur_plane_number]
        check.append(cur_plane_number)
    
    
    
    if cur_plane_number == 0:
        break
    else:
        visited[cur_plane_number] = True
        for num in check:
            parents_number[num] = cur_plane_number-1
 
    cur_idx += 1
 
print(cur_idx)
 

이 문제는 프로그래머스의 호텔 방 배정하기하고 동일한 문제라고 볼수 있다.

주어진 위치가 있고, 1~위치 사이에 비행기를 도킹할 수 없으면, 멈추면 되는것이다.

호텔 방 배정하기하고 동일하게, 자신의 다음 도킹 위치를 저장시켜놓으면 된다. 

그러면서 최악의 경우를 방지하기 위해, 그 다음 도킹위치를 새로 갱신해주는 작업을 해주면 된다.

import sys
 
input = sys.stdin.readline
 
def find_parent(idx):
    if idx == make_set[idx]:
        return idx
    else:
        make_set[idx] = find_parent(make_set[idx])
        return make_set[idx]
 
G = int(input())
P = int(input())
 
make_set = [i for i in range(G+1)]
 
 
result = 0
for k in range(P):
    plane_num = int(input())
    gate_num = find_parent(plane_num)
 
    if gate_num < 1:
        break
    else:
        make_set[gate_num] = make_set[gate_num-1]
        result += 1
        
 
print(result)

이거는 좀 더 함수로 만들어놓은 것이다.

위와 똑같은 로직이지만, find_parent 라는 재귀함수를 통해, 자동적으로 갱신이 되게 해주었다.

호텔 방 배정하기 문제를 수월하게 풀었으면 이 문제도 수월하게 풀 수 있을거라 생각한다.

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 union(x,y):
    X = find_parent(x)
    Y = find_parent(y)
    if X == Y:
        return 0
 
    else:
        if child_cnt[X]< child_cnt[Y]:
            make_set[X] = Y
            return_value = child_cnt[X] * child_cnt[Y]
            child_cnt[Y] += child_cnt[X]
        else:
            make_set[Y] = X
            return_value = child_cnt[X] * child_cnt[Y]
            child_cnt[X] += child_cnt[Y]
 
        return return_value
            
        
 
N,M,Q = map(int,input().split())
 
 
graph = [{} for i in range(N+1)]
 
make_set = [i for i in range(N+1)]
child_cnt = [1 for i in range(N+1)]
connect_input = [[],]
for _ in range(M):
    x,y = map(int,input().split())
    graph[x][y] = 1
    graph[y][x] = 1
    connect_input.append((x,y))
 
result = 0
disconnet_list = []
 
for _ in range(Q):
    ind = int(input())
    x,y = connect_input[ind]
    graph[x][y] = 0
    graph[y][x] = 0
    disconnet_list.append(ind)
 
 
for i in range(1,M+1):
    if i not in disconnet_list:
        x,y = connect_input[i]
        union(x,y)
 
 
while disconnet_list:
    ind = disconnet_list.pop()
    x,y = connect_input[ind]
    result += union(x,y)
print(result)

이 문제는 역으로 생각하는 편이 제대로 푸는 방식이었다 윗 코드는 첫 풀이이다.

문제를 푸는 방식은 다음과 같다. 문제에서 주어진 끊어진 조건들을 전부 끊어졌다고 가정을 하고

끝에서부터 하나씩 연결을 해가면서 반대로 추적을 하는것이다.

그러므로, 먼저 전체 연결리스트를 들어온 순서에 맞게 index에 알맞게 저장을 해준다.

그리고 난뒤에 끊어진 목록들을 따로 저장을 해두고, 끊어지지 않은 연결들끼리 서로 union find를 해준다.

union_find를 하면서, 각자의 노드 개수를 저장해주는 리스트를 따로 만들어두고,

서로 다른 집합이 합쳐질때 그 두 개의 노드의 개수를 합쳐주는 로직을 해주면 된다.

이렇게 연결이 된 간선들로 union find를 1차적으로 진행을 한다.

그리고 끝에서부터 끊어진 간선들끼리 연결을 해준다. 그러면 그 간선을 끊기전 모습으로 돌아갈 수 있다.

이렇게 하면서 서로의 집합이 같으면 0을 반환하고, 그게 아니면 서로의 집합의 개수를 곱한 수를 반환하도록 했다.

import sys
 
input = sys.stdin.readline
 
 
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 union(x,y):
    X = find_parent(x)
    Y = find_parent(y)
    if X == Y:
        return 0
 
    else:
        if rank[X] < rank[Y]:
            X,Y = Y,X
 
        size_a,size_b = rank[X],rank[Y]
        rank[X] += rank[Y]
        make_set[Y] = X
        return size_a*size_b
            
        
 
N,M,Q = map(int,input().split())
 
 
 
make_set = [i for i in range(N+1)]
rank = [1 for _ in range(N+1)]
connect_input = [[],]
check = [True]*(M+1)
for _ in range(M):
    x,y = map(int,input().split())
    connect_input.append((x,y))
 
result = 0
disconnet_list = []
 
for _ in range(Q):
    ind = int(input())
    disconnet_list.append(ind)
    check[ind] = False
 
 
for i in range(1,M+1):
    if check[i]:
        x,y = connect_input[i]
        union(x,y)
 
 
while disconnet_list:
    ind = disconnet_list.pop()
    x,y = connect_input[ind]
    result += union(x,y)
print(result)

좀 더 깔끔하고 빠른 풀이 방식이다. 첫 풀이 코드같은경우엔 느렸는데

그 이유는 간선이 연결됬는지 안됬는지를 구분하는데 not in 으로 했기 때문에, O(N)의 시간이 걸려서 느려진 문제가 있었다.

그래서 간선들이 연결이 됬는지 안됬는지를 구분하는 리스트를 만들어두고 바로 확인이 가능하도록 했다.

https://www.secmem.org/blog/2021/03/21/Disjoint-Set-Union-find/

설명은 잘 못하므로 위의 링크에 있는 Union_find를 보면 알겠지만, rank compression을 활용해서 시간을 좀 더 줄였다.

Union find는 크루스칼알고리즘에서 처음으로 알게 되었는데, 크루스칼에서만 쓰이는줄 알았는데,

생각외로 단독으로 쓰이는 곳이 많았다. 이걸 짜는데 어색해서 크루스칼 알고리즘을 잘 안쓰는데,

좀 더 숙달되도록 노력해야겠다.

1

import sys
 
input = sys.stdin.readline
 
def union(A,B):
    X = find_parent(A)
    Y = find_parent(B)
    if X != Y:
        if rank[X] < rank[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if rank[X] == rank[Y]:
            rank[X] += 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 = map(int,input().split())
 
make_set = [i for i in range(N+1)]
rank =  [1 for _ in range(N+1)]
for _ in range(M):
    command, A,B = map(int,input().split())
 
    if command:
        if find_parent(A) == find_parent(B):
            sys.stdout.write('YES\n')
        else:
            sys.stdout.write('NO\n')
    else:
        union(A,B)

import sys
input = sys.stdin.readline
def union_find(x,y):
    a = find_parent(x)
    b = find_parent(y)
    if a != b:
        make_set[b] = a
        friend_cnt[a] += friend_cnt[b]
 
    return a
 
def find_parent(A):
    if make_set[A] == A:
        return A
    make_set[A] = find_parent(make_set[A])
    return make_set[A]
 
 
T = int(input())
 
for tc in range(T):
    F = int(input())
    person_dict = {}
    cnt = 1
    make_set = [k for k in range(F*2+1)]
    friend_cnt = [1 for k in range(F*2+1)]
    for _ in range(F):
        x,y = input().split()
        if x not in person_dict:
            person_dict[x] = cnt
            friend_cnt[person_dict[x]] = 1
            cnt += 1
        if person_dict.get(y) == None:
            person_dict[y] = cnt
            friend_cnt[person_dict[y]] = 1
            cnt += 1
        x_num = person_dict[x]
        y_num = person_dict[y]
        k = union_find(x_num,y_num)
        print(friend_cnt[k])

# 3197번 Fail
 
import sys
def find(number):
    if parents[number] == number:
        return number
    parents[number] = find(parents[number])
    return parents[number]
 
def merge(root,child):
    parents[child] = root
 
def water_merge():
    while water:
        cx,cy = water.pop(0)
        flag = True
        for k in range(4):
            nx = cx + dx[k]
            ny = cy + dy[k]
            if 0<= nx <R and 0<= ny <C:
                if check_map[nx][ny] != -1 and check_map[nx][ny] != check_map[cx][cy]:
                    parentA = find(check_map[cx][cy])
                    parentB = find(check_map[nx][ny])
                    if parentA != parentB:
                        merge(parentA,parentB)
                        check_map[nx][ny] = parentA
                elif check_map[nx][ny] == -1 and flag:
                    melt_water.append((cx,cy))
                    flag = False
 
 
def water_melt():
    while melt_water:
        cx,cy = melt_water.pop(0)
        root = find(check_map[cx][cy])
        for k in range(4):
            nx = cx + dx[k]
            ny = cy + dy[k]
            if 0<= nx <R and 0<= ny <C:
                if check_map[nx][ny] == -1:
                    water.append((nx,ny))
                    check_map[nx][ny] = root        
 
R,C = map(int,input().split())
 
arr = [list(sys.stdin.readline()) for _ in range(R)]
check_map = [[-1]*C for _ in range(R)]
parents = [-1]*(R*C)
cnt = 0
dx = [-1,1,0,0]
dy = [0,0,-1,1]
swan = []
water = []
for x in range(R):
    for y in range(C):
        if arr[x][y] == '.' or arr[x][y] == 'L':
            water.append((x,y))
            parents[cnt] = cnt
            check_map[x][y] = cnt
            cnt += 1
            if arr[x][y] == 'L':
                swan.append((x,y))
 
swan1 = swan[0]
swan2 = swan[1]
time = 0
melt_water = []
while water:
    water_merge()
    if find(check_map[swan1[0]][swan1[1]]) == find(check_map[swan2[0]][swan2[1]]):
        result = time
        break
    water_melt()
    time += 1
 
            
print(result)

처음 시도했던 실패버전이다.

이 방법은 물을 union find로 한 묶음으로 한뒤, 탐색을 해주는 방식으로 했다. 그러나 이 방식의 문제점은 각 time에 대해 전부다 백조가 연결되어있는지 확인해야 하므로, 시간이 초과가 되었다. 

import sys
from collections import deque
import time
def isconnent_swan(start,end,standard_time):
    global R,C
    visited = [[True] * C for _ in range(R)]
    stack = deque()
    stack.append((start[0],start[1]))
    visited[start[0]][start[1]] = False
    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 melt_time[nx][ny] <= standard_time and visited[nx][ny]:
                    visited[nx][ny] = False
                    stack.append((nx,ny))
                    if nx == end[0] and ny == end[1]:
                        return True
 
    return False
 
 
def find_max_spend_time():
    global R,C
    while waters:
        x,y,time = waters.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < R and 0<= ny < C:
                if melt_time[nx][ny] == -1:
                    melt_time[nx][ny] = time + 1
                    waters.append((nx,ny,time+1))
    return time
R,C = map(int,input().split())
origins = [list(sys.stdin.readline()) for _ in range(R)]
melt_time = [[-1]*C for _ in range(R)]
waters = deque()
swans = []
dx = [-1,1,0,0]
dy = [0,0,-1,1]
for x in range(R):
    for y in range(C):
        if origins[x][y] != 'X':
            waters.append((x,y,0))
            melt_time[x][y] = 0
            if origins[x][y] == 'L':
                swans.append((x,y))
 
 
max_time = find_max_spend_time()
min_time = 0
result = 0
while min_time <= max_time:
    mid_time = (min_time + max_time)//2
    if isconnent_swan(swans[0],swans[1],mid_time):
        answer = mid_time
        max_time = mid_time - 1
    else:
        min_time = mid_time + 1
 
print(answer)

두번째로 찾은 방법은 빙하가 녹는 시간을 미리 구해주는 것이다. BFS를 통해 각 빙하들이 녹는 시간들을 찾아주고, 이분탐색으로 시간을 줄여가면서 백조들끼리 연결되어있는지 구하는 것이다.

빙하가 녹는시간을 구해놓고, 기준시간보다 작거나 같을시에는 이동이 가능하다고 판별을 해주었다.

하지만 이 방법도 백조가 연결되어있는지 매번 BFS를 해야하므로, 실행시간이 오래걸리는 편이었다.

from collections import deque
import sys
R,C = map(int,input().split())
 
lake = [list(sys.stdin.readline()) for _ in range(R)]
waters = deque()
swans = []
water_chk = [[True] *C for _ in range(R)]
swan_chk = [[True] *C for _ in range(R)]
for x in range(R):
    for y in range(C):
        if lake[x][y] != 'X':
            waters.append((x,y))
            water_chk[x][y] = False
            if lake[x][y] == 'L':
                swans.append((x,y))
                lake[x][y] = '.'
start_swan,end_swan = swans
swans = deque()
swans.append(start_swan)
swan_chk[start_swan[0]][start_swan[1]] = False
times = 0
new_water = deque()
new_swans = deque()
dx = [-1,1,0,0]
dy = [0,0,-1,1]
while True:
    while waters:
        x,y = waters.popleft()
        lake[x][y] = '.'
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < R and 0<= ny <C:
                if lake[nx][ny] == 'X' and water_chk[nx][ny]:
                    new_water.append((nx,ny))
                    water_chk[nx][ny] = False
    while swans:
        x,y = swans.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx <R and 0<=ny<C:
                if swan_chk[nx][ny]:
                    if lake[nx][ny] == '.':
                        swans.append((nx,ny))
                    elif lake[nx][ny] == 'X':
                        new_swans.append((nx,ny))
                    swan_chk[nx][ny] = False
 
    if not swan_chk[end_swan[0]][end_swan[1]]:
        answer = times
        break
    waters = new_water
    swans = new_swans
    new_swans = deque()
    new_water = deque()
    times += 1
 
print(answer)

마지막 방식은 deque를 4개를 써서, 매번 bfs를 처음부터 하지 않아도, 되는 방식으로 해주었다.

water : 현재가 물인 상태인 것들이 모아져있는 deque

new_water : 다음 시간에 녹아질 예정인 빙하들의 deque

swan : 현재 시간에 swan이 돌아다닐수 있는 deque

new_swan : 다음 시간에 swan이 움직일수 있는 deque

이렇게 기능적으로 나눈뒤에,

먼저 water에서 다음에 녹을 water를 찾아준다. 이때 new_water에 들어가는 것은 호수에 빙하인것과 water_chk 한번도 방문하지 않은 곳이여야 한다.

그리고 여기서 처음 water를 pop할때 lake[x][y]를 . 를 입력해주는 것은 이전 time에 우리가 찾아놓은 new_water가 녹았기 때문에, 이때 값을 변경시켜주는 것이다.

이렇게 한뒤에, swan를 bfs를 돌리면서 물인곳은 계속 swan에 추가해서 bfs를 해주고, 만약 빙하인곳은 다음번에 들릴곳이기 때문에 new_swan에 넣어준다.

그리고 빙하와 물 상관없이 swan 방문을 check해준다.

이렇게 작업을 한뒤에, 우리가 찾는 반대편 swan에 도착했는지 확인을 해주고, 그때의 시간을 출력해주면 된다.

도착하지 않았으면, new_water를 water에 넣어주고, new_swan을 swan에 넣어준뒤 초기화를 시켜준다