Coding 공부

import sys

input = sys.stdin.readline

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


INF = float('inf')
graph = [[0 if x == y else INF for y in range(N+1)] for x in range(N+1)]

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

    graph[x][y] = min(graph[x][y],pay)




for mid in range(1,N+1):
    for end in range(1,N+1):
        for start in range(1,N+1):
            if graph[start][end] > graph[start][mid] + graph[mid][end]:
                graph[start][end] = graph[start][mid] + graph[mid][end]

K = int(input())
friend_list = list(map(int,input().split()))
min_value = INF
min_list = []
for city in range(1,N+1):
    temp_max = 0
    for p_num in friend_list:
        if graph[p_num][city] + graph[city][p_num] > temp_max:
            temp_max = graph[p_num][city] + graph[city][p_num]

    if temp_max < min_value:
        min_value = temp_max
        min_list = [city]
    elif temp_max == min_value:
        min_list.append(city)

print(*min_list)

 이 문제는 플로이드와샬을 이용해 모든 경로에 대해 이동비용을 먼저 계산을 해준다.

그리고 전체 도시들을 for문을 돌리면서, 친구들의 이동비용을 구하고,

각 친구들의 이동비용의 최대값의 최소가 되는 경우를 구해서 출력해주면 된다.

import sys
input = sys.stdin.readline

N = int(input())


problem_dict = {}
re1_dict = {}

for _ in range(N):
    pb_num,l_num = map(int,input().split())
    re1_dict[(l_num,pb_num)] = 1
    problem_dict[pb_num] = l_num


M = int(input())

for _ in range(M):
    command,*arg = input().split()

    if command == 'add':
        pb_num,l_num = map(int,arg)
        problem_dict[pb_num] = l_num
        re1_dict[(l_num,pb_num)] = 1
    elif command == 'recommend':
        flag = int(arg[0])
        if flag > 0:
            keys = max(re1_dict.keys())
        else:
            keys = min(re1_dict.keys())
        print(keys[1])
    else:
        pb_num = int(arg[0])
        l_num = problem_dict[pb_num]
        del problem_dict[pb_num]
        del re1_dict[(l_num,pb_num)]

 이 문제를 풀때 사실 boj.kr/21944 번을 먼저 풀었기 때문에 그 때 시도했던 후자 방식을 먼저 적용시켜보았다.

제한 시간내에 동작은 하지만 위 풀이는 추천하지 않는다.

문제를 푸는 아이디어는 다음과 같다. 어차피 우리는 recommend를 해야하고, 그때의 값들을 관리하는 것이다.

그러면 이 문제를 풀때 dictinory를 이용하기로 했다.

(난이도, 문제번호)를 key 값으로 하는 dictionary를 만들어준 뒤 

recommend를 해줄때 1일때에는 최대값

-1일때는 최소값을 구해서 출력해주는 식으로 했다.

max,min이 알아서 앞에서부터 비교를 해주니 가능한 방식이다.

그리고 문제를 풀었을 때에는

problem_dict 이라는 dictionary에 문제번호와 난이도를 매핑시켜준 딕셔너리가 있다.

그러면 problem_dict에서 solved 된 문제번호를 통해 난이도를 가져오고,

re1_dict의 값을 제거해주면 된다.

import sys
import heapq
input = sys.stdin.readline

def recommend(flag,heap):
    flag = -flag
    while heap and (heap[0][1]*flag not in problem_dict.keys() or problem_dict[heap[0][1]*flag] != heap[0][0]*flag):
        heapq.heappop(heap)
    result =heap[0]
    result = result[1]*flag
    return result

N = int(input())
max_heap = []
min_heap = []
problem_dict = {}
for _ in range(N):
    pb_num,l_num = map(int,input().split())
    max_heap.append((-l_num,-pb_num))
    min_heap.append((l_num,pb_num))

    problem_dict[pb_num] = l_num
heapq.heapify(max_heap)
heapq.heapify(min_heap)
M = int(input())

for _ in range(M):
    command,*arg = input().split()
    if command == 'add':
        pb_num,l_num = map(int,arg)
        heapq.heappush(max_heap,(-l_num,-pb_num))
        heapq.heappush(min_heap,(l_num,pb_num))
        problem_dict[pb_num] = l_num
    elif command == 'solved':
        pb_num = int(arg[0])
        del problem_dict[pb_num]
    else:
        flag = int(arg[0])
        if flag > 0:
            print(recommend(flag,max_heap))
        else:
            print(recommend(flag,min_heap))

이게 정석적인 풀이이다.

min_heap 과 max_heap을 이용해서 풀었다.

여기서 주의해야할점은 problem_dict을 활용해 사라진 문제들을 찾아서, 제거를 해주어야한다.

while문을 통해 없는 문제들은 전부 없애주고, while문을 탈출했을때 heap[0]에 있는 값을 return 해주면 된다.

import sys
from collections import deque
input = sys.stdin.readline

def bfs(x,y):

    queue = deque()
    queue.append((x,y))
    visited[x][y] = False
    while queue:
        x,y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<M:
                if visited[nx][ny] and arr[nx][ny] >= T:
                    visited[nx][ny] = False
                    queue.append((nx,ny))


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

arr = []

for x in range(N):
    input_list = list(map(int,input().split()))
    temp = []
    for k in range(M):
        temp.append(sum(input_list[3*k:3*(k+1)]))

    arr.append(temp)

T = int(input())

T = 3*T


visited = [[True for _ in range(M)] for _ in range(N)]

dx = [-1,1,0,0]
dy = [0,0,-1,1]

cnt = 0
for x in range(N):
    for y in range(M):
        if arr[x][y] >= T  and visited[x][y]:
            bfs(x,y)
            cnt += 1

print(cnt)

이 문제는 처음들어올때부터 값을 계산해주는 방식으로 했다.

이 문제를 평균값을 구하면 float 값이 나올것 같아서, 어차피 문제에서 경계값이 정수이고,

한 픽셀을 구성하는 것은 3개로 고정적이므로 처음에 들어올때 열을 기준으로 3개씩 짤라주면서 그때의 합을 전부 저장하는 방식으로 했다.

이렇게 변형햔 배열을 가지고 BFS를 하면 되는데

계산의 편의성을 위해 경계값이 들어오자마자 그냥 3배를 해주었다.

그리고 난뒤에는 일반적인 BFS,DFS를 해주면 되는 문제이다.

방문을 하지않고, 경계값을 넘는 위치에 대해 bfs를 해서 인접한 픽셀들을 구하고, 함수가 끝난뒤에 개수를 늘려주었다.

import sys
input = sys.stdin.readline
N,M = map(int,input().split())

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


start = int(input())
stack = [start]
cnt = 0
visited = [True for _ in range(N+1)]
visited[start] = False
while stack:
    x = stack.pop()

    for next_node in graph[x]:
        if visited[next_node]:
            visited[next_node] = False
            cnt += 1
            stack.append(next_node)

print(cnt)

주어진 작업을 시행하기위해서 필요한 작업의 양을 구하는 방법은

처음에 들어온 입력을 자식노드에 부모노드를 기억해놓고,

주어진 노드에서부터, 부모로 가면서 부모의 수를 세어주면 된다.

import sys
input = sys.stdin.readline
def dfs(node):
    global result 
    if not len(graph[node]):
        ball_cnt_list[parent_list[node]] += (ball_cnt_list[node] -1)
        result += abs(ball_cnt_list[node] - 1)
    else:
        for next_node in graph[node]:
            dfs(next_node) 
        if parent_list[node] != -1:
            ball_cnt_list[parent_list[node]] += ball_cnt_list[node] - 1
            result += abs(ball_cnt_list[node] - 1)



while True:
    N = int(input())

    if N == 0:
        break
    graph = [[] for _ in range(N+1)]
    parent_list = [-1 for _ in range(N+1)]
    ball_cnt_list = [0 for _ in range(N+1)]
    indegree = [0 for _ in range(N+1)]
    for _ in range(N):
        node_num,ball_cnt,*arg = map(int,input().split())
        if arg[0]>0:
            for child_node in arg[1:]:
                graph[node_num].append(child_node)
                parent_list[child_node] = node_num
                indegree[child_node] += 1
        ball_cnt_list[node_num] = ball_cnt

    result = 0
    for k in range(1,N+1):
        if indegree[k] == 0:
            dfs(k)
    print(result)

 이 문제를 해결하는데 어려움을 겪었다.

이 문제를 해결하는 방식은 가장 끝 리프노드부터 1씩 무조건 맞춰주는 것이다.

그리고 그때의 절대값들을 전부 더해주는 방식을 해주면 된다.

현재 노드에서 1와의 차이를 부모노드로 옮겨주고,

그때 차이의 절대값을 결과에 계속 더해주면 된다.

# dotorya님 풀이

import sys
input = sys.stdin.readline
def dfs(node):
    global result 
    cnt = ball_cnt_list[node] -1

    for next_node in graph[node]:
        cnt += dfs(next_node)

    result += abs(cnt)
    return cnt



while True:
    N = int(input())

    if N == 0:
        break
    graph = [[] for _ in range(N+1)]
    ball_cnt_list = [0 for _ in range(N+1)]
    indegree = [0 for _ in range(N+1)]
    for _ in range(N):
        node_num,ball_cnt,*arg = map(int,input().split())
        if arg[0]>0:
            for child_node in arg[1:]:
                graph[node_num].append(child_node)
                indegree[child_node] += 1
        ball_cnt_list[node_num] = ball_cnt

    result = 0
    for k in range(1,N+1):
        if indegree[k] == 0:
            dfs(k)
    print(result)

두 번째 풀이는 dotorya님 풀이를 복기한 것이다.

끝노드부터 하는 것은 동일하다.

그리고 현재의 격차를 상위노드로 전달해주고, 결과에는 그 절대값을 계속 누적해서 더해주면 되는 것이다.

from collections import deque
def func(x):
    return x[0]
T = int(input())

for _ in range(T):
    N,M = map(int,input().split())

    arr = list(map(int,input().split()))
    queue = deque()
    for ind,val in enumerate(arr):
        queue.append((val,ind))

    cnt = 0
    while queue:
        val, ind = queue.popleft()
        if not queue or val >= max(queue,key=func)[0]:
            cnt += 1
            if ind == M:
                break
        else:
            queue.append((val,ind))

    print(cnt)

문제에 주어진대로 구현을 하면 되는 문제이다.

단 다른점은 queue에 초기에 현재의 값과 idx의 값을 동시에 넣어주고,

원하는 ind에 도착하면 멈춰주는식으로 했다.

import sys

input = sys.stdin.readline

def dfs(state,order_cnt):
    global result
    if order_cnt >= P:
        result = min(result,dp[state])
        return
    else:
        if dp[state] > result:
            return

        else:
            for cu_node in range(N):
                if state & 1<<cu_node:
                    for next_node in range(N):
                        if not state & 1<<next_node and dp[state|1<<next_node] > dp[state] + arr[cu_node][next_node]:
                            dp[state|1<<next_node] = dp[state] + arr[cu_node][next_node]
                            dfs(state|1<<next_node,order_cnt+1)



N = int(input())


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


state_string = input()
state = 0
P = int(input())
order_cnt = 0
stack = []
result = float('inf')
for i in range(N):
    if state_string[i] == 'Y':
        state += 1<<i
        order_cnt += 1
        stack.append(i)
dp = [float('inf') for _ in range(2**N+1)]
dp[state] = 0
if order_cnt == P:
    print(0)
else:
    dfs(state,order_cnt)
    if result == float('inf'):
        print(-1)
    else:
        print(result)

재귀를 이용해서 문제를 풀었다.

먼저 비트로 각 발전소의 상태를 구분해주었다.

발전소의 위치와 비트의 위치를 동일시해서, 0번째 비트가 1이면, 0번 발전소가 켜져있는것이다.

그러므로 우리는 마지막으로 들어온 입력을 이용해 현재 발전소의 상태를 비트로 표현을 해준다.

그리고 dp라는 테이블에 발전소를 고치는 최소값을 갱신해주기 위해, 만들어두었다.

그 크기는 state의 크기이므로 2**N까지가 필요하다. 

미리 만들어놓은 상태에서 dfs 함수를 통해 재귀를 하면서 문제를 푸는데 접근을 했다.

2중 포문을 돌면서 dfs에 들어온 state를 통해, 현재 켜져있는 발전소를 구분을 해준다.

그리고 발전소가 켜져있으면 두번째 for문을 통해, 켜지지 않은 발전소를 구하고, 현재 state에서 발전소를 켰을때 비용이 더 작은 경우에

추가적으로 dfs를 하는 작업을 해주었다.

그리고 문제에 주어진 P보다 크거나 같으면 종료되도록 함수를 짰다.

import sys

input = sys.stdin.readline

def dfs(state,order_cnt):
    if dp[state] != -1:
        return dp[state]
    if order_cnt >= P:
        dp[state] = 0
        return 0
    else:
        min_value = float('inf')
        for cu_node in range(N):
            if state & 1<<cu_node:
                for next_node in range(N):
                    if not state & 1<<next_node:
                        min_value = min(min_value,dfs(state|1<<next_node,order_cnt+1) + arr[cu_node][next_node])
        dp[state] = min_value
        return dp[state]

N = int(input())


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


state_string = input()
state = 0
P = int(input())
order_cnt = 0
for i in range(N):
    if state_string[i] == 'Y':
        state += 1<<i
        order_cnt += 1
dp = [-1 for _ in range(2**N+1)]
if order_cnt >= P:
    print(0)
elif order_cnt == 0:
    if P:
        print(-1)
    else:
        print(0)
else:
    result = dfs(state,order_cnt)
    if result == float('inf'):
        print(-1)
    else:
        print(result)

좀 더 깔끔한 풀이는 다음과 같다.

return 되는 값을 이용해 바로 출력이 가능하게 하는것이다.

기본 적인 원리는 같으며, 반환되는 값을 비교를 해서 최저값을 갱신을 해주는 것이다.

그리고 조건을 만족했을때에는 0을리턴하는식으로 해주는 것이다.

이 풀이가 dp라는 테이블을 좀더 생산적으로 쓰면서 풀 수 있는 방식이다.

import sys

def check(idx,cnt):
    global result
    if idx == N:
        result = max(result,cnt)
        print(result)
        exit()
        return
    else:
        for next_idx in range(idx+1,N,2):
            if dp[idx][next_idx]:
                check(next_idx+1,cnt+1)
input = sys.stdin.readline

N = int(input())

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

dp = [[ True  if i == j else False for j in range (N)]  for i in range(N)]
for i in range(N-1):
    if arr[i] == arr[i+1]:
        dp[i][i+1] = True

for i in range(2,N):
    for j in range(N-i):
        if arr[j] == arr[j+i] and dp[j+1][j+i-1]:
            dp[j][j+i] = True

max_num = N//2
result = -1
check(0,0)
print(result)

이 문제는 boj.kr/10942에서 풀었던 전체 배열에 대한 팰린드롬의 dp를 구해놓은 상태로 풀었다.

먼저 전체 배열의 대한 팰린드롬 상태를 dp에 저장시켜놓는다.

그리고 우리는 check를 해주면 된다.

우리는 짝수개 만큼 나눌수 있다.

그러면 우리는 현재 위치에서 짝수번째 떨어진 위치의 dp 상태값을 통해 팰린드롬이면 재귀를 통해

N번째 index에 도착할때까지 계속해준다.

그리고 최초로 도착을 했을때가 가장 최대 짝수팰린드롬이므로, 그때 값을 출력해주면 된다.

왜냐하면, 우리는 2칸단위부터 자르기 때문에,

가장 먼저 도착하는 것이, 가장 많이 자른것이기 때문이다.

이 문제는 이렇게 dp로 푸는 방식말고도 그리디방식으로도 푸는 방식이 있다하지만, 배움이 부족해,

그 풀이는 정확히 이해하지 못했다.