Coding 공부

import sys
def input():
    return sys.stdin.readline().rstrip()
N,M,R = map(int,input().split())
arr = [0] + list(map(int,input().split()))

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


INF = float('inf')
distance = [[0 if i == j else INF for j in range(N+1)] for i in range(N+1)]
for _ in range(R):
    x,y,pay = map(int,input().split())
    graph[x][y] = min(graph[x].get(y,float('inf')), pay)
    graph[y][x] = min(graph[y].get(x, float('inf')),pay)
    distance[x][y] = min(distance[x][y],pay)
    distance[y][x] = min(distance[y][x],pay)

value = [0 for _ in range(N+1)]
for mid in range(1,N+1):
    for start in range(1,N+1):
        for end in range(1,N+1):
            if distance[start][end] > distance[start][mid] + distance[mid][end]:
                distance[start][end] =  distance[start][mid] + distance[mid][end]


result = 0
for node in range(1,N+1):
    temp = 0
    for next_node in range(1,N+1):
        if distance[node][next_node] <= M:
            temp += arr[next_node]
    if temp > result:
        result = temp
print(result)

이 문제는 플로이드와샬을 통해 최단거리를 갱신해주고, 

N^2를 탐색하면서, 거리가 M 이하일때 더해줘서 최대값을 갱신해서 출력해주는 문제이다.

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

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



INF = float('inf')
step_trash = [[INF for _ in range(M)] for _ in range(N)]
arround_trash = [[INF for _ in range(M)] for _ in range(N)]

arround_trash_can = [[0 for _ in range(M)] for _ in range(N)]


arr = []
start = []
flower = []
for x in range(N):
    temp = list(input())
    for y in range(M):
        if temp[y] == 'S':
            start = (x,y)
        elif temp[y] == 'F':
            flower = (x,y)
    
    arr.append(temp)
dx = [-1,1,0,0]
dy = [0,0,-1,1]


for x in range(N):
    for y in range(M):
        if arr[x][y] == 'g':
            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] == '.':
                        arround_trash_can[nx][ny] = 1

node_list = []

heapq.heappush(node_list,(0,0,start[0],start[1]))

step_trash[start[0]][start[1]] = 0
arround_trash[start[0]][start[1]] = 0
visited = [[True for _ in range(M)] for _ in range(N)]

while node_list:
    s_t,p_t,x,y = heapq.heappop(node_list)

    if not visited[x][y]:
        continue
    visited[x][y] = False


    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] == 'g':
                if step_trash[nx][ny] > s_t + 1:
                    step_trash[nx][ny] = s_t + 1
                    arround_trash[nx][ny] = p_t + arround_trash_can[nx][ny]
                    heapq.heappush(node_list,(step_trash[nx][ny], arround_trash[nx][ny], nx, ny))
            else:
                if step_trash[nx][ny] > s_t:
                    step_trash[nx][ny] = s_t
                    arround_trash[nx][ny] = p_t + arround_trash_can[nx][ny]
                    heapq.heappush(node_list,(step_trash[nx][ny],arround_trash[nx][ny],nx,ny))
                elif step_trash[nx][ny] == s_t and arround_trash[nx][ny] > p_t + arround_trash_can[nx][ny]:
                    step_trash[nx][ny] = s_t
                    arround_trash[nx][ny] =  p_t + arround_trash_can[nx][ny]
                    heapq.heappush(node_list,(step_trash[nx][ny],arround_trash[nx][ny],nx,ny))






x,y = flower

print(step_trash[x][y] , arround_trash[x][y])

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

문제를 제대로 읽어야하는데 빈 공간을 갈때 주변의 쓰레기 개수와 상관없이 1개이든 4개이든 1번의 불쾌함으로 측정을 해야한다.

그러므로 이 점을 주의해서 우선순위를 설정을 해서 다익스트라를 해줘야한다.

다익스트라를 돌리기전에 사전 작업을 했는데, 쓰레기인 구역을 찾아서

그 주변에 빈공간이 있으면 arround_trash_can라는 배열에 1로 표시를 해줬다.

그래서 arround_trash_can이라는 배열에 0이 아닌 1이 표시된 부분은 쓰레기가 존재하는 옆칸을 지나가는 것이다.

이 문제에서 형택의 여자친구는 쓰레기를 지나가는 것을 가장 싫어하고, 쓰레기 옆을 지나가는 것을 두번째로 싫어한다고 되어있다.

그러므로 heapq에 우선순위를 쓰레기를 지나가는 것 s_t를 가장 앞에 두었고, 쓰레기 옆을 지나가는 개수인 p_t를 두번째 인자로 넣어주었다.

이렇게 한뒤 형택이 상하좌우로 움직이면서 쓰레기인 칸을 밟았을때에는 step_trash의 값과 비교를 해서 더 낮은 값이면, 갱신을 하고 넣어주었다.

그리고 빈공간일때에는 먼저 쓰레기를 밟는 개수가 더 작은 경우인지 확인을 한 뒤, 더 작으면 값을 갱신하고 heapq에 넣어준다.

근데 그게 아니라 쓰레기를 밟는 개수는 동일하다면, 쓰레기 옆을 지나간 횟수를 비교를 해서 heapq에 넣어준다.

이 문제에서 주의해야했던 점은 쓰레기 옆을 지나가는 유무를 구분하는 것이지, 빈공간 옆의 쓰레기의 개수를 세는

것이 아니였던 점이다.

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 heapq

def solution(n, start, end, roads, traps):
    answer = 0
    INF = float('inf')
    dp = [[INF for _ in range(n+1)] for _ in range(1<<len(traps))]
    traps_index ={value:ind  for ind,value in enumerate(traps) }
    node_list = []
    graph =[[] for _ in range(n+1)]

    for road in roads:
        x,y,pay = road
        graph[x].append([y,pay,0])
        graph[y].append([x,pay,1])

    heapq.heappush(node_list,(0,start,0))
    dp[0][start] = 0
    while node_list:
        cur_time,cur_node,state = heapq.heappop(node_list)
        if end == cur_node:
            answer = cur_time
            break
        if dp[state][cur_node] < cur_time:
            continue
        for next_node,pay,flag in graph[cur_node]:
            next_state = state
            if cur_node in traps:
                if next_node in traps:
                    cur_flag = ((1&(state>>traps_index[cur_node])) + 
                    (1&(state>>traps_index[next_node])))%2
                    next_state = state^(1<<traps_index[next_node])
                else:
                    cur_flag = (1&(state>>traps_index[cur_node]))
            else:
                if next_node in traps:
                    cur_flag =  (1&(state>>traps_index[next_node]))
                    next_state = state^(1<<traps_index[next_node])
                else:
                    cur_flag = 0
            
            if cur_flag == flag:
                if dp[next_state][next_node] > cur_time + pay:
                    dp[next_state][next_node] = cur_time + pay
                    if next_node in traps:
                        heapq.heappush(node_list,(dp[next_state][next_node], next_node,next_state ))
                    else:
                        heapq.heappush(node_list,(dp[next_state][next_node],next_node,next_state))

    return answer

이 문제를 핵심은 트랩을 밟았을 때의 상태를 어떻게 저장할 것인가.

저장한 그 상태를 통해 현재 길의 상태를 어떻게 알 수 있을가인가.

이 문제는 총 4가지 경우가 있다고 볼 수 있다.

트랩이 아닌  곳 -> 트랩이 아닌곳

트랩이 아닌 곳 -> 트랩인 곳

트랩인 곳 - > 트랩이 아닌곳

트랩인 곳 -> 트랩인 곳

이렇게 총 4가지 경우가 있을거고, 각각의 상태를 구분해서, 하면 된다.

우리는 먼저 주어진 경로들을 2가지 형태로 저장해놔야한다.

원래 주어진 정방향과, 이게 뒤집혔을때 가는 역방향이다. 이걸 나는 (다음노드, 시간, 상태) 로 넣어놨다.

0이면 정방향

1이면 역방향을 의미하는 식으로 넣어놨다.

트랩은 최대10개 밖에 없고, 트랩의 상태는 비트마스킹을 통해 나타낼수있다.

그렇게 하기 위해 각각의 trap들의 index로 각자의 위치를 매핑시켜줬다.

그러면 인제부터 각위치의 비트가 1이면 해당 위치의 트랩이 활성화 된 상황이고, 비활성화일때는 0이다.

그리고 우리는 각 상태에서 다익스트라를 돌리는 것이기 때문에 최대 (2**10) * N개의 distance 테이블을 만들어놓고 탐색을 하면 된다.

원래의 다익스트라와 비슷하게 하지만, 우리는 state를 통해 현재 길을 이용할 수 있는지 없는지 판별을 해줘야한다.

한 그래프에 정방향, 역방향을 전부 넣어놨기 때문에, state를 통해서 해당 길을 이용할 수 있는지 찾아야한다.

먼저 가장 쉬운

현재 노드가 트랩이 아닐때이다.

만약 다음 노드가 트랩이 아니라면, 이 길은 항상 정방향이다. 그러므로 저장해놓길 0으로 저장해놓은 길들만 이용이 가능하다.

만약 다음 노드가 트랩이라면, state를 통해 해당 트랩이 활성화 되어있는지 판별을 하면 된다.

판별하는 방법은 현재 state를 해당 트랩의 index만큼 >> 오른쪽으로 비트 이동을 시킨다. 그리고 1과 & 연산을 하면 된다.

이게 1이면 활성화가 된 상태이고, 아니면 비활성화 상태이다.

다음은 현재노드가 트랩일때이다.

현재노드가 트랩이고, 다음노드가 트랩이 아닐때에는 위와 동일하므로 넘어가겠다.

가장 많이 고민했던, 현재노드와 다음노드가 전부 트랩일때이다.

이때는 총 4가지 경우가 생긴다.

1. 현재노드 비활성화 다음노드 비활성화

2 .현재노드 활성화 다음노드 비활성화

3. 현재노드 비활성화 다음노드 활성화

4. 현재노드 활성화 다음노드 활성화

총 4가지 경우가 생긴다.

1번의 경우는 둘다 활성화가 안되어있기 때문에 정방향인 길들만 가면된다.

2,3번은 동일하고, 한쪽만 활성화 되어있으면, 그 길은 한번 뒤집힌거기 때문에 역방향인 길들만 가면 된다.

4번은 현재노드 다음노드 전부 활성화 되어있을때이다.

이때는 이 길이 2번 뒤집힌거기 때문에, 정방향인 길들만 가면된다.

그래서 나는 

(    ( 1 & (state>>traps_index[cur_node]) ) + ( 1&( state>>traps_index[next_node]) ) )%2

2개의 상태를 더해서 2로 나눈 나머지로 해서 정방향, 역방향을 구분을 해줬다. 이 외에도 xor 연산을 해도 된다.

우리는 이렇게 해서 해당 길이 갈 수 있는 길인지 아닌지 판별을 했다.

나머지는 다익스트라와 동일하게 하면되는데, 

그리고 현재의 상태와 비교하는게 아니라, 다음의 상태와 비교를 해서 판별을 해주었다.

만약 다음 노드가 트랩이라 한다면, 그 트랩은 활성화가 된 상태인거고, 그때 최소값으로 들어가야한다고 생각했다

그래서 각 현재 시간과 다음노드까지 걸리는 시간은 현재 state가 아닌, 만약 다음노드가 트랩이라면, 트랩의 상태에 따라, 변화된 state로 비교를 해서 구현을 했다.

import sys
import heapq
input = sys.stdin.readline
def dijkstra_fox():
    distance = [INF for _ in range(N+1)]

    distance[1] = 0
    node_list = []
    heapq.heappush(node_list,(0,1))

    while node_list:
        dis,cur_node = heapq.heappop(node_list)
        if distance[cur_node] < dis:
            continue

        for next_node in graph[cur_node]:
            
            if distance[next_node] > graph[cur_node][next_node] + dis:
                distance[next_node] = graph[cur_node][next_node] + dis
                heapq.heappush(node_list,(distance[next_node],next_node))
    return distance


def dijkstra_wolf():
    distance = [[INF for _ in range(N+1)] for _ in range(2)]
    distance[1][1] = 0
    node_list = []
    heapq.heappush(node_list,(0,1,1))

    while node_list:
        dis,cur_node,turn = heapq.heappop(node_list)
        turn = turn%2
        next_turn = (turn+1)%2
        if distance[turn][cur_node] < dis:
            continue
        for next_node in graph[cur_node]:
            if turn:
                next_distance = dis + graph[cur_node][next_node]//2
            else:
                next_distance = dis + graph[cur_node][next_node]*2
            
            if distance[next_turn][next_node] > next_distance:
                distance[next_turn][next_node] = next_distance
                heapq.heappush(node_list,(next_distance,next_node,next_turn))
    return distance
N,M = map(int,input().split())

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

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

INF= float('inf')




distance_fox = dijkstra_fox()
distance_wolf = dijkstra_wolf()
result = 0
for i in range(2,N+1):
    if distance_fox[i] < distance_wolf[0][i] and distance_fox[i] < distance_wolf[1][i]:
        result += 1

print(result)

어려웠던 문제였다.

 이 문제는 다음과 같이 풀면된다. wolf일때 2개의 turn으로 나누어서 distance에 저장을 시켜준다.

현재 turn의 distance에 저장하는 것이 아닌 next_turn에 저장을 하고 그 값을 비교하는 것에 조심해주면 된다.

그리고 제일 주의해야할 것은 가장 처음 시작하는 노드를 0으로 초기화할때 가장 첫턴 1턴 1번 노드만 0으로

초기화 시켜야 한다

이를 지키지 않고 둘다 초기화 시키면,, 틀렸습닏를 볼 수 있을 것이다.

import sys
import heapq
input = sys.stdin.readline

N = int(input())
M = int(input())

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

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

INF = float('inf')
distance = [INF]*(N+1)

start_city,end_city = map(int,input().split())

distance[start_city] = 0
node_list = []
heapq.heappush(node_list,(0,start_city))

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] > cur_dis + graph[cur_node][next_node]:
            distance[next_node] = cur_dis + graph[cur_node][next_node]
            heapq.heappush(node_list,(distance[next_node],next_node))


print(distance[end_city])
result = [end_city]
stack = [(distance[end_city],end_city)]
while stack:
    dis,cur_node = stack.pop()
    if cur_node == start_city:
        break
    for prev_node in parent_node[cur_node]:
        if graph[prev_node][cur_node] + distance[prev_node] == dis:
            stack.append((distance[prev_node],prev_node))
            result.append(prev_node)
            break

print(len(result))
result.reverse()
print(*result)
    

다익스트라를 이용해 푸는 문제이고, 경로를 추적해주면 되는 문제였다.

백준 5719번 문제 거의 최단경로에서 다익스트라 경로를 추적을 해본적이 있어서, 쉽게 풀수 있었다.

처음에 틀렸습니다를 받았는데, 경로를 추적하면서 출발점에 도착했을때, 반복문을 종료를 안시켜줘서 그렇다.

그 이유는 문제 조건 중에 pay가 0인경우가 있기때문에, 출발점을 넘어서 다른경로를 더 추적한 것 같다.

import sys
import heapq
input = sys.stdin.readline

N = int(input())
M = int(input())

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

path = [-1 for _ in range(N+1)]
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y] = min(graph[x].get(y,float('inf')),pay)

INF = float('inf')
distance = [INF]*(N+1)

start_city,end_city = map(int,input().split())

distance[start_city] = 0
node_list = []
heapq.heappush(node_list,(0,start_city))

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] > cur_dis + graph[cur_node][next_node]:
            distance[next_node] = cur_dis + graph[cur_node][next_node]
            heapq.heappush(node_list,(distance[next_node],next_node))
            path[next_node] = cur_node


print(distance[end_city])
result = []
city = end_city

while True:
    if city == start_city:
        result.append(city)
        break
    result.append(city)
    city = path[city]
print(len(result))
result.reverse()
print(*result)
    

 두번째 풀이는 위의 풀이보다 좀 더 깔끔한 풀이이다.  그 방식은 다익스트라를 하면서, 부모노드를 기록해주는 것이다.

최저 경로를 갱신해준 부모노드를 기록해주면, 최저의 비용으로 움직이는 하나의 경로를 저장할 수 있을것이다.

이걸 이용해서, start_city가 올때까지 반복문을 돌리는 방식으로 구현할 수 있다.

첫번째 풀이는, 모든 이동경로를 찾을때 쓰면 괜찮을 방법인것 같다.

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)