트리에서 두 노드 사이 유일한 경로를 찾는 방법

1. 문제

 

30893번: 트리 게임 (acmicpc.net)

30893번: 트리 게임

 

 

2. 풀이

 

트리니까, 출발 정점 S에서 도착 정점 E로 이동하는 경로는 유일하면서 반드시 존재한다.

 

이때, 선공은 어떻게든 S에서 E로 이동시킬려하고 후공은 E로 어떻게든 못가게 하는게 목적

 

여기서 한번 방문한 노드는 다시는 방문하지 못하니까, 이동 못하게 방해하는게 가능하다.

 

핵심은 S에서 E로 가는 경로를 찾아야하는데 DFS를 하면서 이동한 경로를 리스트에 담아 저장하면..

 

deepcopy해야하는데 여기서 시간이 오래걸리더라

 

def find_path(u,target):
    
    visited = [0]*(n+1)

    stack = [(u,[u])]

    while stack:
        
        u,path = stack.pop()

        if visited[u] == 1:
            
            continue
        
        visited[u] = 1

        for v in tree[u]:
        
            if visited[v] == 0:
                
                if v == target:
                    
                    path.append(v)
                    
                    return path

                dpath = path[:]
                dpath.append(v)

                stack.append((v,dpath))

 

 

어떻게든 안할려고 해도 리스트나 dict가 가진 특성때문에...

 

shallow copy한것처럼 path[u] = v하면 stack에 들어간 모든 path가 전부 path[u] = v로 바뀌더라고

 

def find_path(u,target):
    
    visited = [0]*(n+1)

    stack = [(u,{u:-1})]

    while stack:
        
        u,path = stack.pop()

        if visited[u] == 1:
            
            continue
        
        visited[u] = 1

        for v in tree[u]:
        
            if visited[v] == 0:
                
                if v == target:
                    
                    path[u] = v
                    
                    return path

                path[u] = v
                stack.append((v,path))

 

 

한가지 방법은 트리의 특징을 이용해서 경로를 역추적하는 것이다

 

u에서 v로 이동할때, v의 부모가 u이고 이는 유일한 길이기 때문에 배열을 따로 만들어서 저장해둔다

 

https://deepdata.tistory.com/461

다익스트라 알고리즘에서 실제 최단 경로 구하기

 

위에거랑 좀 비슷함

 

다음 트리에서 1부터 시작해서 7로 가는 경로 위 정점을 찾을려고 하는데,

 

1부터 시작해서 2,3,4 인접한 정점을 순회할거잖아.

 

그런데 parent[4] = 1, parent[2] = 1, parent[3] = 1로 2,3,4가 1에서 왔다는걸 표시해두는거지

 

 

마찬가지로 다음 경우에도...

 

parent[5] = 3, parent[8] = 5, parent[6] = 5, parent[7] = 5로 표시해두는거지

 

 

 

이렇게 한번의 DFS로 parent배열이 구해지는데..

 

[-1,-1,1,1,1,3,5,5,5] 이런식으로.. 그러면 1번에서 7번으로 이동한 경로를 찾기 위해서

 

7번부터 시작해서 역으로 부모 노드를 찾아가는 것이다.

 

7번에서 >>> parent[7] = 5이므로, 5 > 7로 왔다는 뜻이 된다.

 

다시 5번에서 >>> parent[5] = 3이므로 3 > 5 > 7로 왔다는 뜻이 된다.

 

다시 3번에서 >>> parent[3] = 1이므로 1 > 3 > 5 > 7로 왔다는 뜻이다.

 

1번부터 7번의 경로를 찾는 것이므로, 1,3,5,7임을 알 수 있다.

 

def find_path(u,target):
    
    visited = [0]*(n+1)
    stack = [u]
    parent = [-1]*(n+1)

    while stack:
        
        u = stack.pop()

        if visited[u] == 1:
            
            continue
        
        visited[u] = 1

        for v in tree[u]:
        
            if visited[v] == 0:
                
                if v == target:
                    
                    parent[v] = u
                    
                    return parent

                parent[v] = u
                stack.append(v)

n,s,e = map(int,stdin.readline().split())

tree = [[] for _ in range(n+1)]

for _ in range(n-1):
    
    a,b = map(int,stdin.readline().split())
    tree[a].append(b)
    tree[b].append(a)

flag = False
path = find_path(s,e)

win_path = {}

t = e

while path[t] != -1:
    
    p = path[t]
    win_path[p] = t

    t = p

 

 

이 경로를 알았으면 선공, 후공 번갈아가면서 1번부터 시작해서 7번으로 탐색하면 되는데

 

한가지 방법은 트리의 경로는 유일하기 때문에 선공이 이길려면 반드시 미리 구해놓은 경로를 따라가면서 이동해야하므로,

 

현재 정점이 u이면 u 다음의 이기는 경로 위 정점으로 dfs를 해야할 것이고

 

후공은 이길려면 이기는 경로로 탐색하면 안되기 때문에 u의 인접한 정점을 모두 찾아서

 

이기는 경로가 아닌 다른 경로의 정점을 우선적으로 dfs하고

 

다른 경로의 정점이 모두 방문 상태라면 마지막으로 이기는 경로 위의 정점이 방문 상태가 아니라면 그곳으로 dfs해야할 것이다

 

from sys import stdin,setrecursionlimit
setrecursionlimit(10**6)

def find_path(u,target):
    
    visited = [0]*(n+1)
    stack = [u]
    parent = [-1]*(n+1)

    while stack:
        
        u = stack.pop()

        if visited[u] == 1:
            
            continue
        
        visited[u] = 1

        for v in tree[u]:
        
            if visited[v] == 0:
                
                if v == target:
                    
                    parent[v] = u
                    
                    return parent

                parent[v] = u
                stack.append(v)

def game(u,target,turn):
    
    global flag

    if u == target:
        
        flag = True
        return
    
    visited[u] = 1

    if turn == 0:
        
        v = win_path.get(u,-1)

        if v != -1 and visited[v] == 0:
            
            game(v,target,1)
        
    
    else:
        
        no = []
        yes = []

        k = win_path.get(u,-1)

        for v in tree[u]:
            
            if visited[v] == 0:
                
                if k == v:
                    
                    yes.append(v)
                
                else:
                    
                    no.append(v)
        
        if len(yes) == 1 and len(no) == 0:
            
            game(yes[0],target,0)
        
        else:
            
            for v in no:
                
                game(v,target,0)
            
n,s,e = map(int,stdin.readline().split())

tree = [[] for _ in range(n+1)]

for _ in range(n-1):
    
    a,b = map(int,stdin.readline().split())
    tree[a].append(b)
    tree[b].append(a)

flag = False
path = find_path(s,e)

win_path = {}

t = e

while path[t] != -1:
    
    p = path[t]
    win_path[p] = t

    t = p

visited = [0]*(n+1)

game(s,e,0)

if flag:
    
    print('First')

else:
    
    print('Second')

 

 

 

3. 다른 풀이

 

문제 만든 사람이 의도한 풀이는 먼저 트리의 경로는 유일하며 반드시 존재하기 때문에,

 

s에서 e로 이동하는 경로위 정점 s,a2,a3,...,e를 일단 찾고

 

생각을 해보면 선공은 반드시 이 경로를 따라가야만 게임에서 이길 수 있고,

 

후공은 이 경로를 한번이라도 벗어나게 한다면 게임에서 이길 수 있다

 

트리라서 어디 벗어났다가 s > a2에서 b3로 왔다가 다시 a4 > a5 > ... > e로 가는 경우는 없다

 

s에서 e로 가는 경로가 s,a2,a3,...,e로 유일하기 때문임

 

 

선공은 먼저 움직이기 때문에 s > a2, a3 > a4, a5 > a6...로 짝수번째 정점 위에 서게 된다.

 

후공은 선공 다음에 움직이기 때문에 a2 > a3, a4 > a5,...로 짝수번째 정점의 말을 홀수번째 정점 위로 옮기게 된다.

 

후공이 이길려면 이 짝수번째 정점에서 다음 홀수번째 정점으로 이동하는 과정에서 다른 정점으로 옮겨야한다.

 

a2 > a3, a4> a5,... 이 과정 각각에서 a2에서 a3가 아닌 다른 정점으로 옮길 수 있는지, a4에서 a5가 아닌 다른 정점으로 옮길 수 있는지를 보면 된다.

 

그러면 이동 경로 s,a2,a3,...,e를 역추적으로 찾고, 후공이 이동시켜야하는 정점 a2,a4,...에 대하여...

 

a2,a4,...가 인접한 정점이 몇개인지만 세면 된다

 

이동시킬 수 있는 정점이 2개 이상이면 무조건 후공의 승리가 된다

 

마지막 도착 정점 e가 후공이 이동시켜야하는 정점이라면.. 도착으로 끝난거니까 이건 그냥 넘겨야한다

 

#트리의 경로 유일성
#s에서 e로 이동하는 트리의 경로를 찾는 방법
from sys import stdin

#DFS로 u에서 v로 이동할때, v가 u에서 왔다는것을 parent[v] = u로 표시
def find_path(u,target):

    visited = [0]*(n+1)
    stack = [u]
    parent = [-1]*(n+1)

    while stack:

        u = stack.pop()

        if visited[u] == 1:

            continue

        visited[u] = 1

        for v in tree[u]:

            if visited[v] == 0:

                if v == target:

                    parent[v] = u

                    return parent

                parent[v] = u
                stack.append(v)

n,s,e = map(int,stdin.readline().split())

tree = [[] for _ in range(n+1)]

for _ in range(n-1):

    a,b = map(int,stdin.readline().split())
    tree[a].append(b)
    tree[b].append(a)

path = find_path(s,e)

#경로 역추적
#도달 정점 e부터 시작해서 parent[e] = v이면 v > e이므로 [v,e]
#e를 v로 갱신하고 parent[v] = u이면 u > v > e이므로 [u,v,e]
#이런 식으로 반복문으로 찾는다
win_path = [e]

t = e

while path[t] != -1:

    p = path[t]
    win_path.append(p)

    t = p

#path = [e,an-1,an-2,...,a2,s] 형태로 거꾸로 되어있다
first = True

j = 1
for i in range(len(win_path)-1,-1,-1):
    
    if j % 2 == 0: #후공이 움직여야하는 정점 v

        v = win_path[i]
        
        if v == e: #이미 도달 정점이라면 조사할 필요가 없다
            continue
        
        #tree가 양방향으로 구현되어 있어서
        #tree[v]에는 부모 정점 u가 포함되어 있다
        #u 이외에도 다른 정점 v1,v2,.. 2개 이상이 포함(총 3개 이상)되어 있다면 후공의 승리
        #u 이외에도 다른 정점이 v1으로 1개라면 선공의 승리 가능성이 있다
        if len(tree[v]) >= 3:
            
            first = False
            break    
    j += 1

if first:
    
    print('First')

else:
    
    print('Second')