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 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
input = sys.stdin.readline
def check(num):
    visited[num] = True
    stack = [num]

    while stack:
        node = stack.pop(0)

        for next_node in tree[node]:
            if tree[node][next_node] == 1:
                if not visited[next_node]:
                    visited[next_node] = True
                    stack.append(next_node)
                    tree[node][next_node] = 0
                    tree[next_node][node] = 0
                else:
                    return False
    return True
            


tc = 1
while True:
    N,M = map(int,input().split())
    if N+M == 0:
        break
    parent_cnt = [0]*(N+1)
    tree = [{} for _ in range(N+1)]
    for _ in range(M):
        x,y = map(int,input().split())
        tree[x][y] = 1
        tree[y][x] = 1
    cnt = 0
    visited = [False]*(N+1)
    for num in range(1,N+1):
        if not visited[num]:
            if check(num):
                cnt += 1
    if cnt == 0:
        print(f'Case {tc}: No trees.')
    elif cnt == 1:
        print(f'Case {tc}: There is one tree.')
    else:
        print(f'Case {tc}: A forest of {cnt} trees.')


    tc += 1

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

import sys

sys.setrecursionlimit(1000)
def dfs(node,cnt):
    for next_node,val in enumerate(arr[node]):
        if val and visited[next_node] == 0:
            visited[next_node] = cnt
            dfs(next_node,cnt)





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

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

visited = [0]*N
cnt = 1
for i in range(N):
    if visited[i] == 0:
        visited[i] = cnt
        dfs(i,cnt)
        cnt += 1

result = 'YES'
init = visited[tour_list[0]-1]
for city in tour_list[1:]:
    if visited[city -1] != init:
        result = 'NO'
print(result)

첫 풀이 방식은 다음과 같았다.

DFS를 통해 모두 연결이 된대를 같은 cnt로 표시를 했다. 그런데 만약에 같은 cnt가 아니라면 tour_list에서 한번에 갈수 없는 곳 이므로 result를 No로 출력했다.

import sys
input = sys.stdin.readline

def union(A,B):
    x = find_parent(A)
    y = find_parent(B)
    if x > y:
        x,y = y,x
    make_set[y] = x
    for i in range(N+1):
        if make_set[i] != i:
            make_set[i] = find_parent(make_set[i])

def find_parent(ind):
    if make_set[ind] == ind:
        return ind
     
    return find_parent(make_set[ind])
N = int(input())
M = int(input())
edges = []
for i in range(N):
    graph_list = list(map(int,input().split()))
    for j in range(N):
        if graph_list[j] == 1:
            edges.append((i+1,j+1))

tour_list = list(map(int,input().split()))
make_set = [i for i in range(N+1)]

for edge in edges:
    node_a,node_b = edge
    if find_parent(node_a) != find_parent(node_b):
        union(node_a,node_b)

init_value = make_set[tour_list[0]]
result = 'YES'
for city in tour_list:
    if init_value != make_set[city]:
        result = 'NO'
        break
print(result)

좀 더 원론적인 union find를 해서 같은 집합인지 아닌지 판별을 했다.

그리고 난뒤에 같은 집합이 아니면 No를 출력하게 했다.