Coding 공부

def dfs(cnt):
    if cnt == 81:
        for row in sdoku:
            print(''.join(list(map(str,row))))
        exit()
    else:
        x = cnt//9
        y = cnt%9
        square = (x//3)*3 + y//3
        if sdoku[x][y] == 0:
            for num in range(1,10):
                if not (column_check[y][num] or row_check[x][num] or square_check[square][num]):
                    column_check[y][num] = True
                    row_check[x][num] = True
                    square_check[square][num] = True
                    sdoku[x][y] = num
                    dfs(cnt+1)
                    sdoku[x][y] = 0
                    column_check[y][num] = False
                    row_check[x][num] = False
                    square_check[square][num] = False


        else:
            dfs(cnt+1)



sdoku = []

column_check = [[False for _ in range(10)] for _ in range(9)]
row_check = [[False for _ in range(10)] for _ in range(9)]
square_check =[[False for _ in range(10)] for _ in range(9)]
for x in range(9):
    temp = list(map(int,list(input())))
    for y in range(9):
        if temp[y] != 0:
            square = (x//3)*3 + y//3
            column_check[y][temp[y]] = True
            row_check[x][temp[y]] = True
            square_check[square][temp[y]] = True
    sdoku.append(temp)


dfs(0)

스도쿠의 특성을 활용해서 하면 된다.

먼저 각 열, 각 행, 3*3 사각형의 숫자를 얼만큼 사용했는지를 CHECK 해주는 리스트를 만들어준다.

여기서 square 넘버를 부여하는 방식은 (x//3)*3 + (y//3)으로 해서, 가장 위에서 부터 

0 1 2

3 4 5

6 7 8

로 구분이 가능하게 해줬다.

그리고 dfs를 활용해서, cnt는 전체 칸의 갯수를 뜻하면서, 좌표를 뜻하도록 했다. 해당 좌표에서 비어있으면,

숫자를 하나씩 넣어가면서 백트래킹을 해줬다.

그리고 마지막에 도착하면, 현재 스도쿠를 출력해주고, 함수를 종료시켜줬다.

가장 앞에서부터 하나하나씩 채워나가는 것이기때문에, 가장 먼저 완료되는것이 사전순으로 가장 빠른 스도쿠가 된다.

N = int(input())
arr = [int(input()) for _ in range(N)]
stack = []
result = []
idx = 0
for i in range(1,N+1):
    stack.append(i)
    result.append('+')
    while stack and stack[-1] == arr[idx]:
        stack.pop()
        result.append('-')
        idx += 1

if stack:
    print('NO')
else:
    for i in result:
        print(i)

문제에 주어진대로 1부터 차근차근 숫자가 들어온다. 그리고 문제에 주어진 수열을 만드는 것인데,

스택에 들어간 수 중의 끝부분이 주어진 수열과 동일하면 하나씩 pop을 하면서 수열을 맞춰준다.

이 작업을 전부 했는데도, stack에 수가 남아있는것은 주어진 수열을 못 만드는것이기 때문에,

NO를 출력하고,

stack이 다 비어있으면 만든것이기때문에 push pop을 출력해주면 된다.

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는 크루스칼알고리즘에서 처음으로 알게 되었는데, 크루스칼에서만 쓰이는줄 알았는데,

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

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

import sys

sys.setrecursionlimit(100000)


def dfs(x,y):
    if visited[x][y]:
        return INF
    elif dp[x][y] >0:
        return dp[x][y]
    else:
        visited[x][y] = True
        for i in range(4):
            nx = x + dx[i]*int(arr[x][y])
            ny = y + dy[i]*int(arr[x][y])
            if 0<=nx<N and 0<=ny<M and arr[nx][ny].isdigit():
                dp[x][y] = max(dp[x][y],dfs(nx,ny) + 1)
                if dp[x][y] == INF:
                    return INF
        visited[x][y] = False
    return dp[x][y]

            





dx = [-1,1,0,0]
dy = [0,0,1,-1]
N,M = map(int,input().split())
INF = float('inf')
arr = [list(input()) for _ in range(N)]
visited = [[False for _ in range(M)] for _ in range(N)]
dp = [[0 for _ in range(M)] for _ in range(N)]



result = dfs(0,0)

if result == INF:
    print(-1)
else:
    print(result+1)

 DP와 DFS를 활용한 문제 였다. 이 와 비슷한 문제를 풀어본 경험이 있었기 때문에 수월하게 풀 수 있었다.

여기서 문제에서 동전을 무한번 움직일때 -1을 출력한다는 것은 한번 방문을 했던 곳을 재귀 중에 방문을 하면, 들렸던 

장소에서 현재까지 오는 것이기때문에, 무한번 반복할 수 있다는 생각으로 만들어줬다.

그리고 입력과 똑같은 크기의 DP를 만들어서 해당 값이 초기값인 0이 아닌 다른 값이 있는 것은 해당 위치에서

탐색을 끝낸 것이기 때문에 초기값이 아닐때에는 바로 넘겨주는 것을 구현을 했다.

기본적이 풀이 방식은 다음과 같다.

왼쪽 위에서부터 탐색을 하면서, DFS를 처음 들어갈때 방문을 한곳인지 아닌지를 체크한다. 방문을 안한 곳이면,

방문을 체크해주고, 현재 위치에서 동서남북으로, 움직임이 가능한 경우를 탐색한다.

그리고 가능할때 그 방향으로 DFS를 하면서 한번 움직인 것이기 때문에 + 1을 해준다.

이렇게 재귀를 하면서 현재의 DP값과 최대값을 비교해서 저장을 해준다.

그리고 이 4방향을 다 둘러본것은 전부 탐색을 한 것이기 때문에 방문을 초기화 해준다.

그리고 현재 DP 값을 돌려주면 된다.

이렇듯 방문을 체크하는 리스트와 현재 위치에서의 최대값을 저장해주는 DP를 활용해서 풀 수 있는 문제였다.

arr = list(input())
N = len(arr)
left_bracket = 0
right_bracket = 0
total_bracket = 0
result = 0
for i in range(N):
    if arr[i] == '(':
        left_bracket += 1
        total_bracket += 1
    else:
        right_bracket += 1
        total_bracket -= 1

    if total_bracket <= 1:
        left_bracket = 0

    if total_bracket == -1:
        result = right_bracket
        break


if total_bracket > 0:
    result = left_bracket

print(result)

이 문제는 어려웠던 문제였다. 이 문제는 괄호의 특성을 이해하고, 그것의 패턴을 찾아서 생각을 해줘야했던 문제였다.

이 문제의 조건은 최대 1개의 오타가 존재할 수 있다.

여는 괄호를 +1, 닫는 괄호를 -1로 할씨, 마지막의 최종 괄호의 수가 -2 이거나 2이면 1개의 오타가 존재하는 것이고,

-1이 되는 순간 닫는괄호가 1개가 더 많은 것을 확인할수 있는 순간이다.

이 문제에서 닫는괄호의 갯수가 더 많을 경우에는 닫는 괄호가 더 많아지는 그 순간에서의 닫는 괄호의 갯수만큼을 바꿀수 있다.

그리고, 이 문제에서 어려웠던 것은 왼쪽괄호가 더 많을 경우이다. 왼쪽 괄호가 더 많은 경우에는 왼쪽괄호가 절대 바뀔수 없는 경우들을 생각을 해줘야한다.

만약 여는 괄호의 수가 닫는괄호의 수보다 2개이상 많지 않으면, 그 괄호들은 바꿀수가 없다. 이 문제에서 최외각의 괄호들은 왼쪽은 여는괄호 오른쪽은 닫는괄호 인 것을 상기해보면 풀 수 있다.

이러한 점을 응용해, 전체 브라켓의 갯수가 1개 이하일때에는 왼쪽 괄호의 수를 계속 0으로 초기화를 시켜주는 작업을 하고, 그 이후부터 잉여 왼쪽 브라켓의 개수를 세주는 작업을 하는 방식으로 풀 수 있다.

# 	babygranfa 코드 분석
arr = list(input())
N = len(arr)
left_bracket = 0
right_bracket = 0
total_sum = 0
left_stack = []
right_stack = []
left_list = [0]*N
right_list = [0]*N

for i in range(N):
    if arr[i] == '(':
        left_bracket += 1
        total_sum += 1
        left_stack.append(i)
    else:
        right_bracket += 1
        total_sum -= 1
        if left_stack:
            left_stack.pop()
        else:
            right_stack.append(i)
    
    left_list[i] = left_bracket
    right_list[i] = right_bracket

if total_sum > 0:
    print(left_list[-1] - left_list[left_stack[-1]]+1)
elif total_sum <0:
    print(right_list[right_stack[0]])
else:
    print(0)

이 방식은 다른사람의 풀이를 보고 습득한 방법이다.

이 풀이는 자료구조를 이용해서, 여는 괄호의 위치를 저장해주는 스택과 닫는 괄호를 저장해주는 스택을 해준다.

여기서 쌍을 이루는 스택들은 하나씩 제거를 해주면서, 여는 괄호가 없고, 닫는괄호가 있을때에는 그때의 위치를 저장시켜준다.

이런식으로 하면서, 전체 브라켓의 개수가 양수일때에는 왼쪽괄호가 더 많은 것이므로, 왼쪽괄호의 최종 개수에서 마지막 왼쪽괄호의 스택이 위치가 존재하는 곳의 왼쪽괄호의 개수를 빼주고 1개를 더해준다. 그 위치의 왼쪽괄호도 포함되어야하기 때문이다.

그리고 오른쪽괄호같은경우엔, 최초로 오른쪽괄호가 많아지는 곳의 오른쪽괄호의 수를 출력해주면 된다.

이 문제는 괄호의 특성을 이해하고, 그것을 적용시키는 문제로, 저에게 상당히 어려웠던 문제였다.

import sys

sys.setrecursionlimit(10000)
def roll(x,y,vis,cnt,roll_cnt):
    global result,total_cnt
    if total_cnt == cnt:
        result = min(result,roll_cnt)
        return
    if roll_cnt > result:
        return
    vis[x][y] = True
    dx = [-1,1,0,0]
    dy = [0,0,1,-1]
    for i in range(4):
        move = 1
        nx = x + dx[i]*move
        ny = y + dy[i]*move
        while 0<=nx<N and 0<=ny<M and vis[nx][ny] == False:
            nx = nx + dx[i]
            ny = ny + dy[i]
            move += 1
        if move>1:
            for m in range(1,move):
                nx = x + dx[i]*m
                ny = y + dy[i]*m
                vis[nx][ny] = True
            
            roll(nx,ny,vis,cnt+(move-1),roll_cnt+1)

            for m in range(1,move):
                nx = x + dx[i]*m
                ny = y + dy[i]*m
                vis[nx][ny] = False




tc = 1
while True:
    try:
        N,M = map(int,input().split())
        arr = []
        total_cnt = N*M
        visited = [[False]*M for _ in range(N)]
        for x in range(N):
            temp = list(input())
            for y in range(M):
                if temp[y] == '*':
                    visited[x][y] = True
                    total_cnt -= 1
            
            arr.append(temp)

        result = float('inf')
        for x in range(N):
            for y in range(M):
                if arr[x][y] == '.':
                    copy_visited = [row[:] for row in visited]
                    roll(x,y,copy_visited,1,0)

        if result == float('inf'):
            result = -1
        print(f'Case {tc}: {result}')
        tc += 1
    except:
        break

이 문제는 문제에 주어진 조건대로 굴리면 되는 문제였다.

여기서 주의해야할 점은 최소 이동거리가 1이상이어야하고, 그때에만 움직여주면서 VISITED를 반대 상태로 바꿔줬다가, 탐색이 끝나면 원래 상태로 바꿔주는 것이 필요로 했다.

또한 최소 이동횟수이므로, 이동횟수보다 많은 로직에 대해서는, 탐색을 그만두고 되돌아가는 백트래킹이 필요로 했다.

처음에 최소 이동횟수가 아닌, N*M 보드 완주하는 횟수를 구하는 줄 알고, 잘못 구현하는 실수를 저질렀었다.

그점만 조심하면, DFS를 재귀를 짜는것과 비슷하게 풀면 되는 문제였다.

import sys
import heapq

input = sys.stdin.readline

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

graph = [{} for i in range(N+1)]
plant = list(map(int,input().split()))
INF = float('inf')
for _ in range(M):
    u,v,w = map(int,input().split())
    graph[u][v] = min(graph[u].get(v,float('inf')),w)
    graph[v][u] = min(graph[v].get(u,float('inf')),w)



MST_DISTANCE = [INF for i in range(N+1)]
visited = [True]*(N+1)

result = 0
node_list = []
for start in plant:
    heapq.heappush(node_list,(0,start))
    MST_DISTANCE[start] = 0

while node_list:
    dis,node = heapq.heappop(node_list)
    if not visited[node]:
        continue
    result += dis
    visited[node] = False
    for next_node in graph[node]:
        if MST_DISTANCE[next_node] >graph[node][next_node]:
            MST_DISTANCE[next_node] = graph[node][next_node]
            heapq.heappush(node_list,(MST_DISTANCE[next_node],next_node))


print(result)

서로 다른 발전소끼리 연결이 되면 안되므로, 프림알고리즘을 하는데, 발전소의 위치를 전부 0으로 초기화 해주고,

전부 heapq에 넣어주고, Prim 알고리즘을 돌려주면 된다.

import sys
input = sys.stdin.readline

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

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,K = map(int,input().split())


plant = list(map(int,input().split()))
make_set = [i for i in range(N+1)]
rank = [1 for _ in range(N+1)]
edges = []
for _ in range(M):
    u,v,w = map(int,input().split())
    edges.append((u,v,w))

edges.sort(key=lambda x : -x[2])


for k in range(1,K):
    union(plant[k],plant[k-1])

cnt = 1
result = 0
while cnt <(N-K+1):
    x,y,weight = edges.pop()
    if find_parent(x) != find_parent(y):
        union(x,y)
        result += weight
        cnt += 1

print(result)

    두번째 풀이는 크루스칼을 이용해서 풀었다.

발전소가 서로 연결이 되면 안되므로, 처음부터 모든 발전소를 하나의 union으로 merge를 해준다.

그리고 난뒤에 크루스칼 알고리즘을 해주면 된다.

그리고 전체 간선 수는 전체 노드의 수 - 1 이지만, 여기서는 (N-1)-(K-1)의 수 만큼만 해주면 된다.

이 문제를 처음에 어렵게 생각해서 각 플랜트만의 프림알고리즘을 돌려서, 최저값을 갱신하는 식으로 했다.

하지만, 같이 연결이 안되기만 하면 되니깐 프림 알고리즘을 하면서, 처음 스타트 위치를 전부 넣어주기만 하면 됬다.

이 문제에 더 어울리는 알고리즘은 프림보다, 크루스칼 알고리즘인 것 같다.

arr = list(map(int,input().split()))
check_border = [
    [
        1,2,17,19,
        13,3,4,15,
        5,6,7,8,
        14,16,11,12,
        9,10,18,20,
        21,22,23,24
    ],
    [
        1,2,14,16,
        13,15,9,10,
        11,12,17,19,
        3,4,18,20,
        21,22,23,24,
        5,6,7,8,
    ],
    [1,3,6,8,
    5,7,10,12,
    9,11,21,23,
    22,24,2,4,
    17,18,19,20,
    13,14,15,16], 
    [1,3,21,23,
    5,7,2,4,
    9,11,6,8,
    22,24,10,12,
    13,14,15,16,
    17,18,19,20], 
    [1,2,3,4,
    5,6,15,16,
    9,10,11,12,
    13,14,23,24,
    17,18,7,8,
    21,22,19,20], 
    [1,2,3,4,
    5,6,19,20,
    13,14,7,8,
    9,10,11,12,
    17,18,23,24,
    21,22,15,16]
]

result = 0
for i in range(6):
    check = check_border[i]
    for j in range(6):
        check_face = list(map(lambda x : x-1,check[(4*j):4*(j+1)]))
        if not (arr[check_face[0]] == arr[check_face[1]] == arr[check_face[2]] == arr[check_face[3]]):
            break
    else:
        result = 1
        break

print(result)
            

이 문제에서 주의해야할 건 무조건 1번 움직이는 것이다.

그리고 2 X 2 X 2 의 큐브의 경우, 돌릴때 1번 돌릴때 딱 6가지의 경우의 수 밖에 없으므로,

그 6가지를 전부 구해놓고, 4개 간격으로 같은색인지 확인하는 방식으로 풀면 된다.