Coding 공부

import sys
import heapq

def dijkstra(flag=False,*arg):
    distance = [INF for _ in range(N+1)]
    distance[1] = 0
    node_list = []
    if flag:
        remove_node = arg[0]
    heapq.heappush(node_list,(0,1))
    
    while node_list:
        cur_dis,node = heapq.heappop(node_list)
        if cur_dis>distance[node]:
            continue
        for next_node in graph[node]:
            if flag and ((node,next_node) == remove_node or (next_node,node) == remove_node):
                continue 
            temp_distance = cur_dis + graph[node][next_node]
            if distance[next_node] > temp_distance:
                distance[next_node] = temp_distance
                heapq.heappush(node_list,(temp_distance,next_node))
    if not flag:
        stack = [(N,distance[N])]
        while stack:
            node,dis = stack.pop()
            for prev_node in graph[node]:
                if (prev_node,node) not in short_list:
                    if distance[prev_node] + graph[prev_node][node] == dis:
                        short_list.add((prev_node,node))
                        stack.append((prev_node,distance[prev_node]))

    return distance[N]
    

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


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

graph = [{} for _ in range(N+1)]
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y] = pay
    graph[y][x] = pay

INF = float('inf')

short_list = set()
short_time = dijkstra()
short_list = list(short_list)

result = -1
for node in short_list:
    remove_time = dijkstra(True,node)
    result = max(result,remove_time - short_time)

print(result if result != INF else -1)

문제를 푸는 방식은 다음과 같다.

먼저 다익스트라로 최단 거리를 구한다.

그와 동시에 이동경로를 구해야한다.

즉 우리는 다익스트라를 하면서 누적된 이동거리 리스트를 이용해서 역산을 통해 최단 거리의 이동 경로를 구한다.

이렇게 구한 이동경로를 하나씩 검문을 하는 것이다.

그리고 그 검문을 했을때의 다익스트라를 구하고, 이 때의 최대값을 구하고, 지연된 시간을 구하면 된다.

이 문제는 다익스트라를 통해 이동경로를 추적하고, 그 이동경로를 활용해서 풀 수 있는 문제였다.

import sys
from collections import defaultdict
import heapq
def input():
    return sys.stdin.readline().rstrip()
N,M = map(int,input().split())



graph = [defaultdict(list) for _ in range(N+1)]
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y].append((pay,True))
    graph[y][x].append((pay,False))


node_list = []
INF = float('inf')
distance_list = [INF for _ in range(N+1)]
distance_list[1] = 0
heapq.heappush(node_list,(0,1,1,True))
result = []

while node_list:
    cur_dis, cur_node , parent_node , cur_flag = heapq.heappop(node_list)
    if cur_dis > distance_list[cur_node]:
        continue
    if cur_node != parent_node:
        if cur_flag:
            result.append((parent_node, cur_node))
        else:
            result.append((cur_node, parent_node))
    for next_node in graph[cur_node]:


        for pay,flag in graph[cur_node][next_node]:
            if cur_dis + pay < distance_list[next_node]:
                distance_list[next_node] = cur_dis + pay
                heapq.heappush(node_list,(distance_list[next_node], next_node , cur_node , flag))
    
print(len(result))
for row in result:
    print(*row)

처음으로 풀었던 방식이다. 문제의 출력을 입력에 주어진 간선으로 출력해야하는 줄 알고, 좀 복잡하게 풀었다.

이 문제를 처음 본 순간 MST 문제 인줄 알았는데, MST 문제는 아니였다.

1번 조건만 보고 모든 노드들이 연결되는 최소인줄 알고 MST인줄 알았는데,

2번 조건을 찬찬히 읽어보니 다익스트라 문제였다.

네트워크를 복구해서 통신이 가능하도록 만드는 것도 중요하지만, 해커에게 공격을 받았을 때 보안 패킷을 전송하는 데 걸리는 시간도 중요한 문제가 된다. 따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다.

그 2번 조건은 다음과 같다.

슈퍼컴퓨터를 기준으로 모든 컴퓨터들은 최소 시간을 보장해야한다.

즉 슈퍼컴퓨터를 기준으로 모든 노드들에 대한 최소 시간의 다익스트라를 구해야하는 문제이다.

이 점만 주의하면 일반적인 다익스트라 풀이와 동일하다.

import sys
from collections import defaultdict
import heapq
def input():
    return sys.stdin.readline().rstrip()
N,M = map(int,input().split())



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

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


node_list = []
INF = float('inf')
distance_list = [INF for _ in range(N+1)]
distance_list[1] = 0
heapq.heappush(node_list,(0,1,1))
result = []

while node_list:
    cur_dis, cur_node , parent_node  = heapq.heappop(node_list)
    if cur_dis > distance_list[cur_node]:
        continue
    if cur_node != parent_node:
        result.append((parent_node, cur_node))
    for next_node in graph[cur_node]:


        for pay in graph[cur_node][next_node]:
            if cur_dis + pay < distance_list[next_node]:
                distance_list[next_node] = cur_dis + pay
                heapq.heappush(node_list,(distance_list[next_node], next_node , cur_node ))

print(len(result))

for row in result:
    print(*row)

개선한 풀이이다.

import sys
import heapq
from collections import deque
def input():
    return sys.stdin.readline()

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

arr = [list(input()) for _ in range(N)]

start = [0,0,0]
node_list = []
total_cnt = 0
for x in range(N):
    for y in range(N):
        if arr[x][y] == 'S':
            start = [0,x,y]
            arr[x][y] = '0'



heapq.heappush(node_list,start)
INF = float('inf')
visited = [[True for _ in range(N)] for _ in range(N)]
distance = [[INF for _ in range(N)] for _ in range(N)]
result = 0
dx = [-1,1,0,0]
dy = [0,0,-1,1]
cnt = 0
while node_list:
    cur_dis,x,y, = heapq.heappop(node_list)
    if not visited[x][y]:
        continue
    if cur_dis > distance[x][y]:
        continue
    result += cur_dis
    cnt += 1
    visited[x][y] = False

    temp_visited = [[True for _ in range(N)] for _ in range(N)]
    queue = deque()
    queue.append((x,y,0))
    temp_visited[x][y] = False
    while queue:
        qx,qy,dis = queue.popleft()

        for i in range(4):
            nx = qx + dx[i]
            ny = qy + dy[i]

            if temp_visited[nx][ny] and arr[nx][ny] != '1':
                temp_visited[nx][ny] = False
                queue.append((nx,ny,dis+1))
                if arr[nx][ny] == 'K' and distance[nx][ny] > dis+1:
                    distance[nx][ny] = dis + 1
                    heapq.heappush(node_list,(dis+1,nx,ny))
if cnt<M+1:
    print(-1)
else:
    print(result)

 이 문제는 MST와 너비 우선 탐색을 활용한 문제였다.

일단 경계선은 전부 1로 되어있으므로, 경계체크를 해줄 필요는 없다.

문제를 푸는 아이디어는 다음과 같다. 

프림알고리즘을 이용한다.

그런데 프림 알고리즘을 활용할려면, 각 노드 사이의 간선의 정보를 알아야한다.

이 것은 BFS를 통해 로봇과 K들 사이의 간선들을 구하는 것이다.

즉, heap에 들어온 Node를 기준으로 다른 열쇠들 간의 간선의 정보를 찾으면 된다.

그래서 프림 알고리즘을 해서 나오는 노드를 기준으로 BFS를 돌리고, 열쇠이고, 현재 누적된 거리가 더 짧으면

거리를 갱신하고, 그 때의 위치 정보 및 거리를 heap에 넣어준다.

이런식으로 해서 프림알고리즘을 돌리면서 매번 BFS를 돌려서 해당 노드에서 다음노드로 갈수 있는 간선정보를 찾아

heap에 넣어주는 식으로 해주면 된다.

그리고 여기서 주의해야할 점은 모든 열쇠를 찾지 못하는 경우도 있다.

우리는 총 M + 1개의 노드를 가진 그래프에서 프림 알고리즘을 돌린것과 마찬가지이므로,

프림 알고리즘에서 방문한 노드의 수가 M+1개 보다 적으면 -1을 출력 해주며 된다.

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 count_group(val):
    k = 0
    temp = 0
    for ind in range(N):
        temp += arr[ind]
        if temp>=val:
            k += 1
            temp = 0
    return k


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

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


left = 0
right = sum(arr)+1

while left+1<right:
    mid = (left+right)//2
    K_mid = count_group(mid)
    if K_mid >= K:
        left = mid
    else:
        right = mid
print(left)

 원래 잘 못푸는 이분탐색 문제라서 오래걸렸던 문제였다.

이 문제에서 구해야할 것은 최소의 최대값이다.

즉 여기서 mid의 값이 의미하는 것은 해당 시험 문제지의 최소 점수인것이다.

즉 이 최소 점수가 넘어가면, 그룹을 나누는것이다.

이렇게 나눈 최소 점수를 기준으로 시험지를 나눴을때의 그룹의 수가  K개 미만이 되면 False K개 이상이 되면 True로 하고

우리는 K개 이상의 가장 마지막 값을 구하고 싶은 것이므로, left를 출력해주면 된다.

이 문제 덕분에 이분탐색에 대해서 감을 잡게 되었고,

찾고 싶은 값이 있을때 어떻게 나눠야할지 대략 감을 잡았다.

아직 부족하지만, 어떻게 나눠야할지 알게 되었다.

https://blog.naver.com/jinhan814/222156334908

https://blog.naver.com/jinhan814/222135038870

https://eine.tistory.com/entry/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89binary-search-%EA%B5%AC%ED%98%84%EC%8B%9C-%EA%B3%A0%EB%A0%A4%ED%95%A0-%EA%B2%83%EB%93%A4

https://blog.naver.com/kks227/220777333252

풀면서 참조한 블로그들이다. 이분탐색에 대해 잘 설명을 해놓은 블로그이니 추천을 드린다.

def checkWin(play):
    play_num = players[play]

    for x in range(3):
        if arr[x][0] == arr[x][1] == arr[x][2] == play_num:
            return 2
    
    for y in range(3):
        if arr[0][y] == arr[1][y] == arr[2][y] == play_num:
            return 2

    if arr[0][0] == arr[1][1] == arr[2][2] == play_num:
        return 2

    if arr[0][2] == arr[1][1] == arr[2][0] == play_num:
        return 2

    return 0 


def dfs(rc,play):
    global result
    if checkWin((play+1)%2)>1:
        return -1
    if rc <remain_cnt:
        check_result = 10
        for idx in range(remain_cnt):
            if not visited[idx]:
                visited[idx] = True
                x,y = remain_list[idx]
                arr[x][y] = players[play]
                check_result = min(check_result,dfs(rc+1,(play+1)%2))
                visited[idx] = False
                arr[x][y] = 0
        if check_result == 10 or check_result == 0:
            return 0
        else:
            return -check_result
    return 0 
arr = []

# 1 = X
# 2 = O
# 착수하는 사람 부터
cnt_1 = 0
cnt_2 = 0
remain_cnt = 0
remain_list = []
players = [1,2]
for x in range(3):
    temp = list(map(int,input().split()))

    for y in range(3):
        if temp[y] == 1:
            cnt_1 += 1
        elif temp[y] == 2:
            cnt_2 += 1
        else:
            remain_cnt += 1
            remain_list.append((x,y))

    arr.append(temp)
visited = [False for _ in range(remain_cnt)]

start = 0
if cnt_1 > cnt_2:
    start = 1




result = dfs(0,start)
answer = ['D','W','L']
print(answer[result])

 이 문제는 어려웠던 문제였다.  이 문제는 각각 최선의 수로 둔다는 것은 해당 수를 두고 다음턴에, 지지 않기를 바라는 상황이다.

그래서 상대턴이 시작할때, 이전턴에 뒀던 플레이어의 승리여부를 체크하고 체크를 한뒤에는 음수를 보내준다.

왜냐하면 서로 승패는 반대로 되기 때문이다. 그리고 승부가 나지 않았을 시에는 0을 반환하도록 한다.

def check():
    for x in range(3):
        prev_num = arr[x][0]
        if not prev_num:continue
        for y in range(1,3):
            if prev_num != arr[x][y]:
                break
        else:
            return prev_num
    
    for y in range(3):
        prev_num = arr[0][y]
        if not prev_num: continue
        for x in range(1,3):
            if prev_num != arr[x][y]:
                break
        else:
            return prev_num

    prev_num = arr[0][0]
    if prev_num:
        for k in range(1,3):
            if prev_num != arr[k][k]:
                break
        else:
            return prev_num
    
    prev_num = arr[0][2]
    if prev_num:
        for k in range(1,3):
            if prev_num != arr[k][2-k]:
                break
        else:
            return prev_num

    return 0


def dfs(rc,player):
    check_num = check()
    if check_num != 0:
        return check_num

    if rc == 0: return -1
    response = []
    for x in range(3):
        for y in range(3):
            if arr[x][y]:continue
            arr[x][y] = player
            response.append(dfs(rc-1,3-player))
            arr[x][y] = 0
    if player in response:return player
    if -1 not in response: return (3-player)
    return -1

arr = [list(map(int,input().split())) for _ in range(3)]
cnt_1 = 0
cnt_2 = 0
player = 1
r_cnt = 0
for x in range(3):
    for y in range(3):
        if arr[x][y] == 1:
            cnt_1 += 1
        elif arr[x][y] == 2:
            cnt_2 += 1
        else:
            r_cnt += 1


if cnt_1 > cnt_2:
    player = 2


result = dfs(r_cnt,player)

if result == -1:
    print('D')
elif result == player:
    print('W')
else:
    print('L')

이 풀이가 좀 더 직관적일 수 있다.

모든 결과들을 저장한뒤에 해당 결과 내에서, 해당 플레이어의 번호가 있으면 승리한 것이므로, 해당 플레이어 번호를 보내주고,

무승부인 -1이 없으면 상대방이 이긴거기 때문에 상대방의 플레이어 번호를 return 해준다.

그리고 둘다 아닌경우에는 무승부이므로 -1을 반환해준다.

이 문제는 최선의 수가 무엇인지, 어떻게 승패를 판단하는지 어려웠던 문제였다.

import sys
sys.setrecursionlimit(123456)
def dfs(node):
    if not graph[node]:
        if pet_list[node]>0:
            return pet_list[node]
        return 0 
    else:
        temp = 0
        for child_node in graph[node]:
            temp += dfs(child_node)
        temp += pet_list[node]
        if temp <0:
            temp = 0
        return temp

def input():
    return sys.stdin.readline().rstrip()
N = int(input())

graph = [[] for _ in range(N+1)]
pet_list = [0 for _ in range(N+1)]
for i in range(2,N+1):
    pet,*arg = input().split()
    pay,island = map(int,arg)
    if pet == 'S':
        pet_list[i] = pay
        graph[island].append(i)
    else:
        pet_list[i] = -pay
        graph[island].append(i)




print(dfs(1))

이 문제는 기본적인 트리 문제였다. 그래프의 경로와 각 양과 늑대를 양수와 음수로 각각 매칭을 했다.

그리고 재귀를 통해서 리프노드까지 간 뒤에 양수이면 양수를 음수이면 0을 보내줬다.

그리고 그렇게 return 된 값들을 전부 더한뒤에

현재 아일랜드의 값을 더해주고, 그 값이 0미만이 되면 0으로 보내주고 그게 아니면 원래대로 보내주면 풀리는 문제이다.

import sys
from collections import defaultdict,deque
def input():
    return sys.stdin.readline().rstrip()


N = int(input())

graph = defaultdict(list)
pet_list = [0 for _ in range(N+1)]
parents = [0 for _ in range(N+1)]
for next_node in range(2,N+1):
    pet,*arg = input().split()
    pay,island = map(int,arg)
    if pet == 'S':
        pet_list[next_node] = pay
    else:
        pet_list[next_node] = -pay
    graph[island].append(next_node)
    parents[next_node] = island

que = deque()
que.append(1)
stack = []
while que:
    cur_node = que.popleft()
    stack.append(cur_node)
    for next_node in graph[cur_node]:
        que.append(next_node)

while stack:
    cur_node = stack.pop()
    pet_list[parents[cur_node]] += max(0,pet_list[cur_node])

print(pet_list[0])

재귀를 이용하지 않고 푸는 방법이다.

먼저 bfs로 탐색하면서 그 순서를 stack에 넣어주고, 끝에서부터 하나씩 꺼내주면 된다.

import sys

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



N = int(input())
A = list(map(int,input().split()))
dict_A = {}
for k in range(N):
    dict_A[A[k]] = k

B = list(map(int,input().split()))
convert_B = [0]*N
for ind,k in enumerate(B):
    convert_B[ind] = dict_A[k]
LIS = [convert_B[0]]



for ind in range(1,N):
    if convert_B[ind] > LIS[-1]:
        LIS.append(convert_B[ind])
    else:
        left = -1
        right = len(LIS)
        while left + 1 < right:
            mid = (left + right)//2

            if LIS[mid] >= convert_B[ind]:
                right = mid
            else:
                left = mid
        LIS[right] = convert_B[ind]

print(len(LIS))

사실 이 문제는 LCS로 분류되어있지만, LIS 태그도 포함되어 있어야한다고 생각한다.

기존의 LCS로 하면 N^2이 걸리기 때문에, 입력사항을 보면 터질수 밖에 없다.

근데 우리는 여기서 문제의 조건을 잘 봐야한다.

문제의 조건에서 1부터 N까지 정수가 모두 한 번씩 등장하는 두 수열 A와 B가 주어졌을 때 라고 되어있다.

이 말은 각 수열에 있는 값들은 중복되는것은 없고, 하나하나가 유니크 하나는 것이다.

이 최장 부분수열에서는 인덱스가 증가하는 방향으로 부분수열을 구해야한다.

그렇다는 말은 A와 B라는 각 리스트가 있을 때, B의 각 값들이 A에 어디에 있는지 해놓으면,

B의 값은 A에 위치한 인덱스로 대치가 된다.

그런데 우리는 부분수열을 구할때, 인덱스가 증가하는 수선대로 해야한다.

즉 이렇다는 말은 A의 인덱스로 바뀐 B의 수열을 최장 증가 부분 수열의 길이를 구하면,

이것은 곧 A와 B의 최장 부분 수열이 됨을 알 수 있게 된다.

이러한 트릭을 가지고, LIS의 길이를 구하는 이분탐색 기법을 통해서 구해주면 된다.