acmicpc.net 1967,1167(트리,DFS), 11725(트리,DFS), 1068(트리,DFS)

https://www.acmicpc.net/problem/1967

알면 간단하다. 어떤 한 점에서던지 가장 먼 노드의 거리를 구하면 그 노드는 가장 먼 두 점중 한 점이다.

그러니까 아무 점에서 시작해서 가장 먼 노드를 구한다. 그리고 그 노드에서 가장 먼 점의 거리를

구하면 그게 답이다. 아래 dfs함수에서 확인할수 있다.

# -*- encoding: cp949 -*-
def dfs(y):
    visited = [0 for i in xrange(10002)]
    s = [[y,0]]
    visited[y] = 1
    max_weight,node = 0,1
    while s:
        p = s.pop()
        if max_weight < p[1]:
            max_weight = p[1]
            node = p[0]
        for i in xrange(len(v[p[0]])):
            t = v[p[0]][i]
            if visited[t[0]]==0:
                visited[t[0]] = 1
                s.append([t[0], t[1]+p[1]])
    return [node,max_weight] #node = 노드번호, max_weight = 노드y 부터 노드 node까지의 거리.
n=input()
v = [[] for i in xrange(n+1)]
for k in xrange(n-1):
    p,s,w = map(int,raw_input().split())
    v[p].append([s,w])
    v[s].append([p,w])
print dfs(dfs(1)[0])[1]

https://www.acmicpc.net/problem/1167

위 코드에서 입력부만 바꿔준다.

~~~
n=input()
v = [[] for i in xrange(n+1)]
for k in xrange(n):
    p = map(int,raw_input().split())[:-1]
    for i in xrange(1,len(p),2):
        v[p[0]].append([p[i],p[i+1]])
        v[p[i]].append([p[0],p[i+1]])

print dfs(dfs(1)[0])[1]

https://www.acmicpc.net/problem/11725

이건 더 간단하다. 마찬가지로 리스트에 정점을 다 넣어준 후 루트가 1이라고 했으므로 DFS로 1부터 시작

한다. 1의 자식들은 부모를 전부 1로 설정해주고 스택에 1의 자식들의 자식들을 넣어주고 부모를 자식으로

설정해놓는다. 이걸 계속 반복하면 된다. (파이썬이라 그런지 시간초과는 안뜨는데 채점하는데 

10분넘게걸림...)

# -*- encoding: cp949 -*-
def dfs(y):
    global parent
    visited = [0 for i in xrange(100002)]
    s = [[v[y],1]]
    visited[y] = 1
    while s:
        p = s.pop()
        for i in xrange(len(p[0])):
            t = p[0][i] #자식들에서 갈수있는 정점
            if visited[t]==0:
                parent[t] = p[1]
                s.append([v[t], t]) #[부모에서 갈수있는자식, 부모번호]
                visited[t] = 1

n=input()
v = [[] for i in xrange(n+1)]
parent = [0 for i in xrange(n+1)]
for k in xrange(n-1):
    p,s = map(int,raw_input().split())
    v[p].append(s)
    v[s].append(p)

dfs(1)
for p in parent[2:n+1]:
    print p

https://www.acmicpc.net/problem/1068

이것도 쉽다. 조금만 변경하면 된다. 입력받은후 부모에서 갈수있는 자식들을 v에 저장해놓는다.

지울 노드를 입력받은후 DFS를 돌면서 노드와, 노드의 자식들의 끝에 -1을 넣어준다.

나중엔 노드를 하나하나 돌면서 자식이 없는 노드를 찾으면 된다.

원래 리프노드였던것도 부모가 지워지면 -1이 끝에 붙으므로 길이가 0이 아니게 된다.

그리고 주의할점은 지울 노드의 부모 노드에서 지울 노드를 지워줘야 한다는 점.

# -*- encoding: cp949 -*-
def dfs(y):
    global v, parent
    visited = [0 for i in xrange(51)]
    s = [y]
    visited[y] = 1
    while s:
        p = s.pop()
        for i in xrange(len(v[p])):
            t = v[p][i]
            if visited[t]==0:
                s.append(t)
                visited[t] = 1
        v[p].append(-1)
        if p in v[parent[p]]: #지울 노드의 부모 노드에서 지울 노드를 지워줌.
            v[parent[p]].remove(p)
n=input()
v = [[] for i in xrange(n)]
parent = map(int,raw_input().split())
for i,p in enumerate(parent):
    if p!=-1:
        v[p].append(i)
d=input()
dfs(d)
#print v
#print parent
answer = 0
for p in v:
    if len(p)==0:
        answer += 1
print answer