Coding 공부

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를 활용해서 풀 수 있는 문제였다.

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)의 수 만큼만 해주면 된다.

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

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

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

import math
import sys


def dfs(node):
    stack = [(node,0,0)]
    visited = [True]*(N+1)
    distance = 0
    max_node = -1
    min_time = float('inf')
    visited[node] = False
    while stack:
        node,dis,time = stack.pop()
        if dis > distance:
            distance = dis
            max_node = node
            min_time = time
        elif dis == distance and min_time > time:
            max_node = node
            min_time = time

        for next_node in graph[node]:
            if visited[next_node]:
                new_dis = dis + 1
                new_time = time + graph[node][next_node]
                visited[next_node] = False
                stack.append((next_node,new_dis,new_time))

    return [max_node,distance,min_time]



input = sys.stdin.readline

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


graph = [{} for _ in range(N+1)]


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

far_node_info = dfs(1)

result = dfs(far_node_info[0])


print(math.ceil(result[2]/T))

트리의 지름 이 문제를 풀어보면 해당 문제를 좀 더 쉽게 풀 수 있다.

문제의 조건은 총 2가지이다. 문제를 가장 많이 풀어야하며, 그 푸는데 시간이 가장 짧아야한다.

이 문제는 트리구조이다. 그래서 문제를 가장 많이 푼다는 것은 트리의 지름을 구하는것과 같다.

그러므로 처음 dfs로 아무 노드에서 가장 먼 노드를 찾고, 그 노드에서 가장 먼 노드들을 찾으면 그게 트리의 지름이 된다.

이걸 응용해서, 첫 dfs로 가장 먼 노드 하나를 찾는다.

그리고 두번째 dfs로 찾은 가장 먼 노드를 기준으로, dfs를 돌려서 깊이가 가장 깊은 노드들을 찾는다. 그리고 그 중에서, 시간이 가장 짧은 것을 선택해주면 된다.

이 문제는 1967번 문제의 트리의 지름을 응용한 문제이고, 트리의 특성에 대해 알고 있으면 쉽게 풀 수 있었던 문제였지만,

처음에 트리의 지름에 대한 아이디어를 얻지 못해서 어려웠던 문제이다.

from collections import deque
N, M = map(int,input().split())



lower_dict = {}
upper_dict = {}

for i in range(6):
    lower_dict[chr(ord('a')+i)] = i
    upper_dict[chr(ord('A')+i)] = i

start = []
arr = []
for x in range(N):
    input_list = list(input())
    for y in range(M):
        if input_list[y] == '0':
            start = (x,y)
    arr.append(input_list)


stack = deque()
stack.append((0,start,0))
flag = True
result = []
INF = float('inf')
dx = [-1,1,0,0]
dy = [0,0,-1,1]
visited = [[[INF for _ in range(M)] for _ in range(N)] for _ in range(64)]
visited[0][start[0]][start[1]] = 0
while stack:
    time,cur_node,state = stack.popleft()
    x,y = cur_node
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<N and 0<=ny<M:
            if arr[nx][ny] != '#' and visited[state][nx][ny] == INF:
                if arr[nx][ny] in upper_dict.keys():
                    if state & 1<<upper_dict[arr[nx][ny]]:
                        visited[state][nx][ny] = time + 1
                        stack.append((time+1,(nx,ny),state))
                elif arr[nx][ny] in lower_dict.keys():
                    visited[state][nx][ny] = time + 1
                    new_state = state | 1<< lower_dict[arr[nx][ny]]
                    visited[new_state][nx][ny] = time + 1
                    stack.append((time+1,(nx,ny),new_state))
                else:
                    if arr[nx][ny] == '1':
                        flag = False
                        result.append(time+1)
                        break
                    visited[state][nx][ny] = time + 1
                    stack.append((time+1,(nx,ny),state))
    if not flag:
        break

if flag:
    print(-1)
else:
    print(min(result))

그래프를 활용한 문제이다. 여기서 주의해야 할 점은 열쇠와 문을 열수 있는 상태를 구분하는것이다.

이 상태를 구분하기 위해 비트마스킹을 이용했다.

현재 상태에서 키가 있는 위치에 도착을 하면 OR 연산을 해서 key를 업데이트 해주고,

그리고 문에 도착을 하면 현재상태와 AND 연산을 해서 True가 되면, 현재 문에 대응하는 열쇠를 소유하는 것으로 판별을 해서 지나갈수 있도록 만들어 주었다.

문제에서 문과 열쇠는 A~F,a~f 밖에 없으므로,

2**0 ~ 2**5 까지로 각각 a~f,A~F를 매핑시켜주면 된다.

그리고 이 전체 state의 크기는 64개이므로, visited 배열을 64*(N*M)의 크기로 미리 만들어둔다.

그리고 그 외에는 일반적인 BFS와 동일하게 해주면 된다.

이 문제는 비트 마스킹을 통해 현재 가지고 있는 키의 상태를 업데이트 해주고, 문에 도착했을때, 이 문에 대응하는 키를 소유하고 있는지를 구분해주면 되는 문제였다.

from collections import deque
import sys

input = sys.stdin.readline
N, M = map(int,input().split())
recipe_dict = {}
next_node_list = [set() for _ in range(N+1)]
for _ in range(M):
    input_list = list(map(int,input().split()))
    recipe = input_list[1:-1]
    liquid_number = input_list[-1]
    recipe.sort()
    if recipe_dict.get(liquid_number):
        recipe_dict[liquid_number].append([set(recipe),input_list[0]])
    else:
        recipe_dict[liquid_number] = [[set(recipe),input_list[0]]]

    for num in recipe:
        next_node_list[num].add(liquid_number)

L = int(input())
own_liquid = list(map(int,input().split()))
possible_list = [False]*(N+1)
result = set()
for num in own_liquid:
    possible_list[num] = True
    result.add(num)
queue = deque(own_liquid)
while queue:
    cur_num = queue.popleft()

    next_nodes = next_node_list[cur_num]

    for next_node in next_nodes:
        if possible_list[next_node]:
            continue
        for ind in range(len(recipe_dict[next_node])):
            recipe = recipe_dict[next_node][ind][0]
            cnt = recipe_dict[next_node][ind][1]

            if cur_num in recipe:
                cnt -= 1
                recipe.remove(cur_num)
                recipe_dict[next_node][ind][0] = recipe
                recipe_dict[next_node][ind][1] = cnt
                if cnt == 0:
                    possible_list[next_node] = True
                    queue.append(next_node)
                    result.add(next_node)


print(len(result))
result = sorted(list(result))
print(*result)

import sys

input = sys.stdin.readline

N,M = map(int,input().split())
recipe_remain_cnt = []
liquid_number = []
next_recipe_array = [[] for _ in range(N+1)]
for i in range(M):
    k,*recipe,r = map(int,input().split())

    recipe_remain_cnt.append(k)
    liquid_number.append(r)

    for num in recipe:
        next_recipe_array[num].append(i)


L = int(input())
own_liquid = list(map(int,input().split()))
result = set(own_liquid)


while own_liquid:
    cur_num  = own_liquid.pop()
    for recipe_idx in next_recipe_array[cur_num]:
        recipe_remain_cnt[recipe_idx] -= 1
        if recipe_remain_cnt[recipe_idx] == 0 and liquid_number[recipe_idx] not in result:
            own_liquid.append(liquid_number[recipe_idx])
            result.add(liquid_number[recipe_idx])

print(len(result))
result = sorted(list(result))

print(*result)

import sys
import heapq
def check(node):

    path_set = set()
    stack = [(node,distance[node])]

    while stack:
        node,dis = stack.pop()
        for prev_node in graph[node]:
            if (prev_node,node) not in path_set:
                if distance[prev_node] + graph[prev_node][node] == dis:
                    path_set.add((prev_node,node))
                    stack.append((prev_node,distance[prev_node]))
    if (G,H) in path_set or (H,G) in path_set:
        return True
    return False



def dijkstra(node):
    distance[node] = 0
    node_list = []
    heapq.heappush(node_list,(0,node))
    while node_list:
        cur_dis, cur_node = heapq.heappop(node_list)
        if distance[cur_node] > cur_dis:
            continue
        for next_node in graph[cur_node]:
            if distance[next_node] > graph[cur_node][next_node] + cur_dis:
                distance[next_node] = graph[cur_node][next_node] + cur_dis
                heapq.heappush(node_list,(graph[cur_node][next_node] + cur_dis,next_node))

    


input = sys.stdin.readline

for _ in range(int(input())):
    N,M,T = map(int,input().split())
    graph = [{} for _ in range(N+1)]
    start,G,H = map(int,input().split())
    for _ in range(M):
        x,y,pay = map(int,input().split())
        graph[x][y] = pay
        graph[y][x] = pay
    
    candidate_list = [int(input().rstrip()) for _ in range(T)]
    INF = float('inf')
    distance = [INF]*(N+1)
    dijkstra(start)
    result = []
    for check_node in candidate_list:
        if check(check_node):
            result.append(check_node)

    result.sort()
    print(*result)

from collections import deque
def find_passenger(start,K):
    stack = deque()
    stack.append((*start,K))
    visited = [[True]*N for _ in range(N)]
    visited[start[0]][start[1]] = False
    if passenger_arr[start[0]][start[1]] < 0:
        result = [start[0],start[1],K,passenger_arr[start[0]][start[1]]]
        passenger_arr[start[0]][start[1]] = 0
        return result

    candidate = []
    while stack:
        x,y,fuel = stack.popleft()
        if fuel < 0:
            break
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N:
                if passenger_arr[nx][ny] <=0 and visited[nx][ny]:
                    visited[nx][ny] = False
                    stack.append((nx,ny,fuel-1))
                    if passenger_arr[nx][ny] < 0:
                        candidate.append([nx,ny,fuel-1,passenger_arr[nx][ny]])
    if candidate:
        candidate.sort(key=lambda x : (-x[2],x[0],x[1]))
        result = candidate[0]
        passenger_arr[result[0]][result[1]] = 0
        return result
    else:
        return False

def find_destination(passenger):
    stack = deque()
    stack.append((passenger[0],passenger[1],passenger[2]))
    destination = destination_dict[passenger[-1]]
    visited = [[True]*N for _ in range(N)]
    visited[passenger[0]][passenger[1]] = False
    init_fuel = passenger[2]
    while stack:
        x,y,fuel = stack.popleft()
        if fuel <= 0:
            return False
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx <N and 0<=ny<N:
                if passenger_arr[nx][ny] <=0 and visited[nx][ny]:
                    visited[nx][ny] = False
                    stack.append((nx,ny,fuel-1))
                    if (nx,ny) == destination:
                        fuel = 2*init_fuel - fuel + 1
                        result = [nx,ny,fuel]
                        return result

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

passenger_arr = [list(map(int,input().split())) for _ in range(N)]
destination_dict = {}
taxi = list(map(lambda x : x-1 ,map(int,input().split())))
ind = 2



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

for _ in range(M):
    start_x,start_y,end_x,end_y = map(lambda x : x-1 ,map(int,input().split()))
    passenger_arr[start_x][start_y] = -ind
    destination_dict[-ind] = (end_x,end_y)
    ind += 1


answer = 0
cnt = 0
while cnt <M:
    passenger = find_passenger(taxi,K)
    if not passenger:
        answer = -1
        break
    destination = find_destination(passenger)
    if not destination:
        answer = -1
        break
    taxi = [destination[0],destination[1]]
    K = destination[-1]
    if K < 0:
        answer = -1
        break
    cnt += 1


if answer == -1:
    print(answer)
else:
    print(K)

경로 중간에 fuel이 0이 되어도 false 반환 안되게 함

n1,n2,n3,n4,n5,n6,n7,n8,n9,n10,n11= map(int,input().split())

arr = [[[[[[[[[[list(map(int,input().split())) for _ in range(n2)] for _ in range(n3)] for _ in range(n4)] for _ in range(n5)] for _ in range(n6)] for _ in range(n7)] for _ in range(n8)] for _ in range(n9)] for _ in range(n10)] for _ in range(n11)]


tomato_cnt = 0
total = n1*n2*n3*n4*n5*n6*n7*n8*n9*n10*n11
tomato = []
for A in range(n11):
    for B in range(n10):
        for C in range(n9):
            for D in range(n8):
                for E in range(n7):
                    for F in range(n6):
                        for G in range(n5):
                            for H in range(n4):
                                for I in range(n3):
                                    for J in range(n2):
                                        for K in range(n1):
                                            if arr[A][B][C][D][E][F][G][H][I][J][K] == 1:
                                                tomato.append((A,B,C,D,E,F,G,H,I,J,K))


dK = [-1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
dJ = [0,0,-1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
dI = [0,0,0,0,-1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
dH = [0,0,0,0,0,0,-1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
dG = [0,0,0,0,0,0,0,0,-1,1,0,0,0,0,0,0,0,0,0,0,0,0]
dF = [0,0,0,0,0,0,0,0,0,0,-1,1,0,0,0,0,0,0,0,0,0,0]
dE = [0,0,0,0,0,0,0,0,0,0,0,0,-1,1,0,0,0,0,0,0,0,0]
dD = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,1,0,0,0,0,0,0]
dC = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,1,0,0,0,0]
dB = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,1,0,0]
dA = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,1]

day = 0
result = 0
while True:
    new_tomato = []
    for A,B,C,D,E,F,G,H,I,J,K in tomato:
        for l in range(22):
            nA = A + dA[l]
            nB = B + dB[l]
            nC = C + dC[l]
            nD = D + dD[l]
            nE = E + dE[l]
            nF = F + dF[l]
            nG = G + dG[l]
            nH = H + dH[l]
            nI = I + dI[l]
            nJ = J + dJ[l]
            nK = K + dK[l]
            if 0<=nA<n11 and 0<=nB<n10 and 0<=nC<n9 and 0<=nD<n8 and 0<=nE<n7 and 0<=nF<n6 and 0<=nG<n5 and 0<=nH<n4 and 0<=nI<n3 and 0<=nJ<n2 and 0<=nK<n1:
                if not arr[nA][nB][nC][nD][nE][nF][nG][nH][nI][nJ][nK]:
                    arr[nA][nB][nC][nD][nE][nF][nG][nH][nI][nJ][nK] = 1
                    new_tomato.append((nA,nB,nC,nD,nE,nF,nG,nH,nI,nJ,nK))

    if len(new_tomato):
        tomato = new_tomato[:]
        day += 1
    else:
        result = day
        for A in range(n11):
            for B in range(n10):
                for C in range(n9):
                    for D in range(n8):
                        for E in range(n7):
                            for F in range(n6):
                                for G in range(n5):
                                    for H in range(n4):
                                        for I in range(n3):
                                            for J in range(n2):
                                                for K in range(n1):
                                                    if arr[A][B][C][D][E][F][G][H][I][J][K] == 0:
                                                        result = -1
        break

print(result)