Coding 공부

import sys
input = sys.stdin.readline
sys.setrecursionlimit(500000)
def root_dfs(node):
    if visited[node]:
        return
    visited[node] = True
    child_list = []
    for next_node in tree[node]:
        if not visited[next_node]:
            child_list.append(next_node)

    if len(child_list)==2:
        return [node,0]
    elif len(child_list) == 1:
        return_value = root_dfs(child_list[0])
        return_value[1] += tree[node][child_list[0]]
        return return_value
    else:
        return [node,0]

def leef_dfs(node):
    if visited[node]:
        return
    visited[node] = True
    child_list = []
    for next_node in tree[node]:
        if not visited[next_node]:
            child_list.append(next_node)
    
    if len(child_list)==0:
        return 0
    else:
        result = 0
        for child_node in child_list:
            result = max(result,leef_dfs(child_node)+tree[node][child_node])
        return result
N,R = map(int,input().split())
tree = [{} for _ in range(N+1)]
for _ in range(N-1):
    x,y,b = map(int,input().split())
    tree[x][y] = b
    tree[y][x] = b


visited = [False for _ in range(N+1)]

root_node_info = root_dfs(R)
visited[root_node_info[0]] = False
leef_dis = leef_dfs(root_node_info[0])
print(root_node_info[1],leef_dis)

2개의 DFS로 나눠서 최초엔 풀었다.

첫번째 풀이는 두개로 나뉘어서 DFS를 했다.

첫 DFS는 기가노드를 찾는것이다. 기가노드를 찾으면 그때의 길이를 저장해놓는다.

그리고 기가노드에서 부터 리프노드까지 최대 길이를 찾아내는 방식으로 해서 구했다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(300000)
def root_dfs(node,dis):
    if visited[node]:
        return
    visited[node] = True
    count = 0
    nexts = -1
    distance = 0
    for next_node in tree[node]:
        if not visited[next_node]:
            count += 1
            nexts = next_node
            distance += tree[node][next_node]
    if count == 1:
        return root_dfs(nexts,dis+distance)
    else:
        return [node,dis]

def leaf_dfs(node,dis):
    global leef_dis
    visited[node] = True
    count = 0
    for next_node in tree[node]:
        if not visited[next_node]:
            leaf_dfs(next_node,dis+tree[node][next_node])
            count += 1
    if not count:
        leef_dis = max(leef_dis,dis)


N,R = map(int,input().split())
tree = [{} for _ in range(N+1)]
for _ in range(N-1):
    x,y,b = map(int,input().split())
    tree[x][y] = b
    tree[y][x] = b


visited = [False for _ in range(N+1)]
root_dis = root_dfs(R,0)
leef_dis = 0
leaf_dfs(root_dis[0],0)
print(root_dis[1],leef_dis)

두번째 풀이는 좀더 깔끔한 풀이이다.

count를 별도로 세주어서 기가노드인지 리프노드인지 구분을 해주었다.

기가노드가 아닐때에는 재귀를 해주면서 distance를 더해주고, 만약 기가노드일때는 재귀를 머추고, 기가노드의 위치와

지금까지 누적된 거리를 반환해준다.

leaf_dfs도 비슷한 과정을 겪는다.

leaf_dfs를 계속 재귀를 통해 가면서 leaf_node에 도착하면 현재까지 누적된 값과 최대값과 비교를 해서 더 큰 값을 넣어주면 된다.

import sys

input = sys.stdin.readline
def dfs(node,flag,*args):
    stack = [(node,0)]
    distance_list = [0 for _ in range(N+1)]
    visited = [False for _ in range(N+1)]
    visited[node] = True
    if not flag:
        visited[args[0]] = True
    while stack:
        node,distance = stack.pop()
        distance_list[node] = distance

        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node] = True
                stack.append((next_node,distance+graph[node][next_node]))
    
    temp = []

    for i in range(1,N+1):
        temp.append((distance_list[i],i))
    temp.sort(key=lambda x :-x[0])
    if flag:
        return_value = temp[0][1]
    else:
        return_value = temp[0][0]
    return return_value


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

first_point = dfs(1,True)
second_point = dfs(first_point,True)

first_value = dfs(first_point,False,second_point)
second_value = dfs(second_point,False,first_point)

print(max(first_value,second_value))

 이 문제는 트리의 지름을 구하는 방법을 응요한 문제이다.

총 4번의 dfs를 통해 두번째 트리의 지름을 알 수 있다.

첫번째 dfs를 통해 아무지점에서 가장 먼 지점을 구한다.

이 지점은 지름을 구성하는 한 점이 될것이다.

두번째 dfs를 통해 첫번째 dfs에서 구한 점에서 가장 먼 점을 구한다.

그러면 이 점은 트리의 지름을 구성하는 가장 먼 점이 될것이다.

이렇게 2번의 dfs를 통해 우리는 가장 먼 점 2개를 구했다.

그러면 이 2점을 각각 dfs를 돌려, 가장 먼 점에서 2번째인 것을 찾아낸다.

그리고 이렇게 두 거리를 구한 뒤 그 중에 더 큰 점을 선택하면 되는 문제이다.

import sys

input = sys.stdin.readline
def dfs(node):
    distance_list = [0 for _ in range(N+1)]
    visited = [False for _ in range(N+1)]
    visited[node] = True
    stack = [(node,0)]
    while stack:
        node,distance = stack.pop()
        distance_list[node] = distance
        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node] = True
                stack.append((next_node,graph[node][next_node]+distance))
    return distance_list

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

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


distance1 = dfs(1)
far_point1 = distance1.index(max(distance1))
distance2 = dfs(far_point1)
far_point2 = distance2.index(max(distance2))
distance3 = dfs(far_point2)
result = sorted(distance2+distance3)[-3]
print(result)

단 3번의 dfs를 통해 구하는 방법도 있다.

이 방법은 지름을 구성하는 2점의 전체길이를 한 리스트로 정하고 뒤에서 3번째를 출력해주는 것이다.

왜냐하면 한 리스트당 한 지점에서 가장 먼 지점은 서로 자신들이기 때문에, 그 2점을 제외하고 그 다음번으로 큰 것이

두번째 트리의 지름의 답이된다.

from collections import deque
def bfs(red,blue):
    stack = deque()

    stack.append((*red,*blue,0,''))
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    direction = ['U','D','L','R']
    while stack:
        rx,ry,bx,by,dis,route = stack.popleft()

        if dis >= 10:
            return (-1,'-')

        for i in range(4):
            nrx,nry = rx,ry
            r_p = 0
            while 0<=nrx<N and 0<=nry<M and arr[nrx][nry] != '#' and arr[nrx][nry] != 'O':
                nrx += dx[i]
                nry += dy[i]
                r_p += 1
            nbx,nby = bx,by
            b_p = 0
            while 0<=nbx<N and 0<=nby<M and arr[nbx][nby] != '#' and arr[nbx][nby] != 'O':
                nbx += dx[i]
                nby += dy[i]
                b_p += 1

            if (nbx,nby) == (nrx,nry):
                if arr[nbx][nby] == 'O':
                    continue
                if r_p > b_p:
                    nrx -= dx[i]
                    nry -= dy[i]
                else:
                    nbx -= dx[i]
                    nby -= dy[i]

            elif arr[nbx][nby] == 'O':
                continue
            elif arr[nrx][nry] == 'O':
                return (dis+1,route + direction[i])
            nrx -= dx[i]
            nry -= dy[i]
            nbx -= dx[i]
            nby -= dy[i]
            if not visited[nrx][nry][nbx][nby]:continue
            visited[nrx][nry][nbx][nby] = False
            stack.append((nrx,nry,nbx,nby,dis+1,route+direction[i]))
    return (-1,'-')

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


arr = []
blue = []
red = []
for x in range(N):
    temp = list(input())
    for y in range(M):
        if temp[y] == 'B':
            blue = (x,y)
        elif temp[y] == 'R':
            red = (x,y)
    arr.append(temp)


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


result = bfs(red,blue)
if result[0] != -1:
    print(result[0])
    print(result[1])
else:
    print(result[0])

 이 문제는 사실상 구슬탈출 2와 동일한 문제이다.

구슬 탈출2와 달라진점은 이동방향을 저장시키는 것외에는 없다.

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

먼저 방문배열을 4차원 배열로 만들어준다.

그 이유는, 빨간색공이 안 움직이지만, 파란공만 움직이는 경우도 있고,

파란공만 움직이고, 빨간공이 움직이지 않을때가 있으므로, 구분을 하기위해 4차원 배열을 선언을 해주었다.

그리고 BFS를 하는 과정은 다음과 같다. 한 방향으로 정하고 각가 red ball과 blue ball을

구멍 혹은 벽을 만나기전까지 계속 굴려준다.

그러면 최종적으로 위치하곳은 벽 혹은 구멍일 것이다. 이 과정에서 각각의 움직이는 횟수도 세어주었다.

먼저 구멍에 빠졌는지 확인을 해주자.

파란공과 빨간공이 전부 빠졌다면, 이것은 패배한것이므로, 제외를 해주자.

그리고 파란공만 들어간거면 그것 또한 패배한 것이므로, 제외를 하자.

그리고 빨간공만 들어갔을때에는 그때는 이긴것이므로, 지금까지 누적된 이동경로를 반환을 해주면 된다.

그리고 두 공의 위치가 최종적으로 같다면, 둘중 먼저 해당지점에 먼저와있는지가 중요하다.

우리는 위에서 반복횟수를 세어주었다.

반복 횟수가 적다는것은 더 빨리 도착한 것이므로, 반복횟수가 많은 볼을 한칸 뒤로 빼준다.

이러한 작업을 다 마치고 나면 위에서 우리는 벽이나 구멍외에는 멈추지 않았다.

그러면 현재 볼들이 있는 위치는 벽일테니, 뒤로 한칸씩 동일하게 이동해준다.

이렇게 한뒤에, 우리가 방문하지 않은 곳이면 방문표시를하고 stack에 넣어주면 된다.

이 문제는 방문을 어떻게 할것인가, 그리고 공을 굴릴때 어떻게 한번에 끝까지 굴릴것인가. 그리고 같은 위치에

중첩됬을때 어떻게 해결하는지 중요한 문제였다.

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
from collections import deque,defaultdict
input = sys.stdin.readline
# 강의 근원 노드의 순서는 1이다.

T = int(input())

for _ in range(T):
    K,M,P = map(int,input().split())
    # K case의 번호
    # M은 노드의 수
    # P는 간선의 수

    strahelr_dict = [defaultdict(int) for _ in range(M+1)]
    strahelr_list = [-1 for _ in range(M+1)]
    graph = [[] for _ in range(M+1)]
    indegree_list = [0 for _ in range(M+1)]
    for _ in range(P):
        x,y = map(int,input().split())
        graph[x].append(y)
        indegree_list[y] += 1
    stack = deque()
    for i in range(1,M+1):
        if not indegree_list[i]:
            stack.append(i)
            strahelr_list[i] = 1
    
    while stack:

        node = stack.popleft()
        cur_strahler = strahelr_list[node]
        for next_node in graph[node]:
            indegree_list[next_node] -= 1
            strahelr_dict[next_node][cur_strahler] += 1
            if not indegree_list[next_node]:
                stack.append(next_node)
                next_strahelr = max(strahelr_dict[next_node].keys())
                if strahelr_dict[next_node][next_strahelr] > 1:
                    strahelr_list[next_node] = next_strahelr + 1
                else:
                    strahelr_list[next_node] = next_strahelr



    print(K,strahelr_list[M])

 이 문제에서 주의해야할 점은,  마지막에 출력해야할 TEST CASE의 값이 T가 아니라, K인걸 주의해야한다.

처음은 위상정렬을 해주는 것과 동일하게 indegree와 graph를 그려준다.

가장 처음에 출발하는 node들의 strahler의 값을 1로 초기화를 해준다.

위상정렬을 해주면서, 방문하는 노드들에 해당 cur_strahler의 개수를 세줍니다.

그러면서 indegree가 0이 되었을때, 최대값을 찾고, 그 개수가 2개 이상이면, 최대값보다 1을 더해서 저장시켜줬습니다.

위와 같이 한뒤에 나머지는 일반적인 위상정렬을 구하면 되는 문제였습니다.

# 42_jakang님 풀이
import sys
input = sys.stdin.readline


def tree_dp(cur_node):

    if not len(graph[cur_node]):
        strahler_list[cur_node] = 1
        return
    else:
        max_st_cnt = 0
        for parent_node in graph[cur_node]:
            tree_dp(parent_node)

            if strahler_list[cur_node] < strahler_list[parent_node]:
                strahler_list[cur_node] = strahler_list[parent_node]
                max_st_cnt = 1
            elif strahler_list[cur_node] == strahler_list[parent_node]:
                max_st_cnt += 1
        if max_st_cnt > 1:
            strahler_list[cur_node] += 1
T = int(input())

for _ in range(T):
    K,M,P = map(int,input().split())
    strahler_list = [0 for _ in range(M+1)]
    graph = [[] for _ in range(M+1)]

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

    

    tree_dp(M)
    print(K,strahler_list[M])
    

 이 풀이는 42_jakang님의 풀이를 공부하면서 한것이었고, 이 풀이 방식은 다음과 같습니다.

어차피 가장 끝노드 M은 고정되어있으므로, 가장 끝 노드에서부터 하나하나씩 부모를 찾아 들어가봅니다.

그리고 부모노드의 strahler_list가 현재노드보다 크면 갱신을 해주고, 그 큰값들의 개수를 세줍니다.

만약에 그 개수가 2개 이상이면, 현재노드의 shrahler의 값을 키워줍니다.

이런 방식을 이용해서도 문제를 풀 수 있습니다.

import sys
from collections import deque

input = sys.stdin.readline


N,M = map(int,input().split())
graph = [set() for _ in range(N+1)]
degree = [0 for _ in range(N+1)]
for _ in range(M):
    pdN,*arr = list(map(int,input().split()))

    for i in range(pdN-1):
        x,y = arr[i],arr[i+1]
        if y not in graph[x]:
            graph[x].add(y)
            degree[y] += 1

stack = deque()
cnt = 0
result = []
flag = True

for i in range(1,N+1):
    if degree[i]==0:
        stack.append(i)
while cnt<N:
    if not stack:
        flag = False
        break
    node = stack.popleft()
    result.append(str(node))
    for next_node in graph[node]:
        degree[next_node] -= 1

        if degree[next_node] == 0:
            stack.append(next_node)
    cnt += 1

if flag:
    print('\n'.join(result))
else:
    print(0)

이 문제와 같은 경우 평범한 위상정렬이다.

여러명의 PD를 통해 앞에서부터, 하나씩 그래프에 SET으로 넣어주었다.

그리고 degree가 0인것들은 최초의 stack에 넣어주고 난뒤에 위상정렬을 구해주면서,

사이클이 발생할 시, 음악프로그램을 구할 수 없는 것이므로, 그때 flag로 분기 처리를 해주었다.

그리고 stack에 나온순서대로 result에 넣어주고 출력을 해주었다.

import sys
import heapq
input = sys.stdin.readline



N = int(input())
node_list = []
pay_list = []

for i in range(N):
    pay = int(input())
    heapq.heappush(node_list,(pay,i))
    pay_list.append(pay)


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

result = 0
visited = [False]*N
while node_list:
    pay,node = heapq.heappop(node_list)
    if visited[node]:
        continue
    visited[node] = True
    result += pay

    for next_node in range(N):
        if next_node != node:
            if pay_list[next_node] > connect_list[node][next_node]:
                pay_list[next_node] = connect_list[node][next_node]
                heapq.heappush(node_list,(pay_list[next_node],next_node))


print(result)

이 문제는 MST 문제로 기존의 MST와 다르게 여러개의 출발점을 동시에 가지는 MST라고 생각을 했다.

각 출발지점에 따라, 다른거이기 때문에 프림 알고리즘을 크루스칼 알고리즘보다 먼저 생각했다.

그래서 각 출발지점을 전부 입력으로 주어진 우물 개설비용으로 초기화 시켜준 점이 기존의 프림알고리즘하고

다른 방식이었다.

그리고 우물을 파는 비용,논의 위치를 heapq에 넣은듯 프림알고리즘을 해주었다.

그리고 방문 표시를 해서, 한번 들린곳은 다시 들리지 않도록 예외 처리를 해줬다.

기존의 MST에서 1곳의 출발지점을 정했던것과 달리, 모든 곳을 출발지점으로 생각하고, 비용을 갱신하면 되는 문제였다.

import sys

input = sys.stdin.readline

N = int(input())
edge = []
cost = []
def find_parent(ind):
    if make_set[ind] == ind:
        return ind
    make_set[ind] = find_parent(make_set[ind])
    return make_set[ind]


def union(A,B):
    X = find_parent(A)
    Y = find_parent(B)

    if X != Y:
        if rank[X] < rank[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if rank[X] == rank[Y]:
            rank[X] += 1

for i in range(N):
    pay = int(input())
    edge.append((pay,0,i+1))
    cost.append(pay)

arr = [list(map(int,input().split())) for _ in range(N)]
for i in range(N):
    for j in range(i):
        edge.append((arr[i][j],i+1,j+1))



make_set = [i for i in range(N+1)]
rank = [0 for _ in range(N+1)]
edge.sort()
cnt = 0
result = 0
for pay,a,b in edge:
    if find_parent(a) != find_parent(b):
        cnt += 1
        result += pay
        union(a,b)
    if cnt == N:
        break
print(result)

크루스칼을 활용한 풀이이다.

여기서도 기존의 MST와 비슷하지만, 다른점은 물이 생성을 하는곳을 0이라는 인덱스를 부모로 가지도록

설정을 해주었다. 우물을 파서, 공급을 받는 곳은, 위치가 다를지라도, 물을 공급받고 있는 것이기 때문에

하나의 집합이라고 볼수 있기 때문이다. 이와 같은 작업을 N개가 이어질때까지 반복해주면 된다.

이 문제는 사실 https://boj.kr/10423 의 문제와 거의 동일하다고 볼 수 있다.

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가 올때까지 반복문을 돌리는 방식으로 구현할 수 있다.

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