[Coding Test] BOJ_UCPC 2020_전단지 돌리기

이런 부분은 이렇게 사용했으면 좋겠다! 싶거나 추가했으면 하는 내용은 과감히 댓글 부탁드립니다.

 

[전단지 돌리기]

현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이의 목표는 케니소프트에서 출발하여 모든 노드에 전단지를 돌리고, 다시 케니소프트로 돌아오는 것이다. 현민이는 힘이 좋기 때문에 현재 노드에서 거리가 D 이하인 모든 노드에 전단지를 돌릴 수 있다.

날씨가 매우 덥기 때문에, 현민이는 최소한만 이동해서 목표를 달성하고 싶다! 현민이를 위해 현민이가 이동해야 하는 총 거리를 구해주자.

 

입력

첫번째 줄에는 노드의 개수 N(1≤N≤100,000)과 케니소프트의 위치 S(1≤S≤N), 힘 D(0≤D≤N)이 주어진다.

두 번째 줄부터 N번째 줄까지, 트리의 간선 정보를 의미하는 두 자연수 x, y가 공백으로 구분되어 주어진다. 이는 x번 노드와 y번 노드가 연결되어 있음을 의미한다. (1≤x,y≤N, x≠y)

주어지는 연결관계는 트리를 구성하며, 모든 간선의 길이는 1이다.

 

출력

현민이가 목표를 완수하기 위해 이동해야 하는 최소 거리를 출력하여라.

 

입출력 예

input:
6 1 1
1 2
2 3
2 4
3 5
5 6

output:
6

 

 

---

한번 보고서는 문제가 잘 이해가 안돼서 저에게 질문을 해봤어요.

어떤 결과를 원하는가?
총 이동거리를 출력해야한다.
(거리는 이동할 때마다 +1)

이동은 어디로하는가?
현민이가 목적을 달성하기위한 최소 거리를 향한다.

목적은 무엇인가?
케니소프트에서 출발해 모든 노드에 전단지를 돌리고 돌아오는 것이다.

내 생각의 다른 경로

저는 Depth First Search 알고리즘을 이용해 진행하기로 했어요!

입력에 따른 graph를 만들어주고, 해당 graph를 통해 DFS 알고리즘으로 search 순서를 출력하는 코드에요.

def dfs(graph, start):
    visited = []
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            stack += graph[node]
    return visited

graph = dict()
n, s, d = map(int, input('숫자 3개 입력: ').split())

for i in range(n): graph[i+1] = []
for i in range(n-1):
    t1, t2 = map(int, input().split())
    if graph.get(t1):
        graph[t1].append(t2)
    else:
        graph[t1] = [t2]

print(dfs(graph, s))

 

위 예시를 기준으로 입력하니 출력된 순서에요.

[1, 2, 4, 3, 5, 6]

 

이제 거의 다 왔습니다! 현재 노드에서 가장 깊이 갈 수 있는 곳을 찾아야해요.

 

작성한 코드에요. 차차 보완이 필요하다 판단한 코드지만 올려놓습니다! ㅎㅎ

def distance(graph, s):
    cnt = 0
    cur = s
    tmp_value = []; tmp_cnt = []
    distance = []
    while True:
        if graph.get(cur):
            if len(graph.get(cur)) > 1:
                tmp_value.append(graph.get(cur))
                tmp_cnt.append(cnt)
            cur = graph.get(cur)[0]
            cnt += 1
            distance.append(cnt)
        elif tmp_value:
            for i in range(len(tmp_value)):
                cnt = tmp_cnt[i]
                for j in range(1, len(tmp_value[i])-1):
                    cur = graph.get(cur)[j]
                    cnt += 1
                del tmp_value[i]
                distance.append(cnt)
        else:
            for i in range(len(distance)):
                distance[i] = (distance[i]-1) * 2
            distance.sort(); distance.reverse()
            return distance[0]

graph = dict()
n, s, d = map(int, input().split())
for i in range(n): graph[i+1] = []
for i in range(n-1):
    t1, t2 = map(int, input().split())
    if graph.get(t1):
        graph[t1].append(t2)
    else:
        graph[t1] = [t2]

print(distance(graph, s))

 

 

HyunJin-Jeong/Practice_CodingTest-Python