[백준] 원 이동하기 2

 

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

22948번: 원 이동하기 2

A원과 B원 사이의 경로를 구하는 문제입니다. 먼저, 저는 크게 2가지 케이스로 나누어서 진행하였습니다. A와 B중 한쪽이 나머지 한쪽에 포함되는 경우, 그렇지 않은 경우로 나누었습니다.

 

1. 한쪽이 나머지 한쪽을 포함하는 경우

어느 원이 더 큰 원인지를 판별하기 위하여 반지름을 비교하게 됩니다. 만약, 도착원인 B가 더 작은 경우에는 B를 포함하고 도 큰 원들의 리스트에 시작원인 A가 포함되게 됩니다.따라서, B를 포함하고 더 큰 원들을 반지름이 작은 순에서 오름차순으로 정렬한 다음 A를 만날 때까지를 저장하고 이를 뒤집어서 출력하게 되면 정답이 되게 됩니다.

 

두번째로 시작원인 A가 더 작은 경우에는 도착원 B가 A를 포함하고 더 큰 원들을 찾았을 때 B가 포함이 되게 됩니다. 이 경우에는 A -> B를 찾아 탐색하게 되므로 뒤집지 않고 출력하면 정답이 됩니다.

 

2. 서로 포함관계가 없는 경우

서로 포함관계가 없는 경우에는 최소 공통 조상을 찾아야합니다. 1번 케이스의 경우에는 A 혹은 B가 최소 공통 조상이 되지만 이번 경우에는 따로 찾아줘야합니다. 1번에서 했던 것처럼 A와 B를 각각 포함하고 더 큰 원들을 각각 저장하고 A의 조상 원들에 대해 방문 처리를 해주고 B의 조상들을 탐색하면서 이미 방문된 첫번째 원을 만나면 해당 원이 최소 공통 조상이 됩니다. 이렇게 공통 조상을 구했으면 A -> 공통 조상까지의 경로 , 공통 조상 -> B까지의 경로를 합쳐주면 A->B까지의 경로를 구할 수 있습니다.

 

 

import sys

# sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

IN = 0
OUT = 1

n = int(input())

circles = [(-1, -1)] * (n + 1)

for _ in range(n):
    num, x, r = tuple(map(int, input().split()))
    circles[num] = (x, r)

a, b = tuple(map(int, input().split()))

circle_a = circles[a]
circle_b = circles[b]

# 원점사이의 거리
def getDistance(x1, x2):
    return abs(x1 - x2)


def getRelation(a, b):
    ax, ar = a
    bx, br = b

    dist = getDistance(ax, bx)
    r_sum = ar + br

    # 원점 사이의 거리가 반지름의 합보다 큰 경우에는 서로 밖에 있는 원이다.
    if dist < r_sum:
        return IN

    # 원점 사이의 거리가 반지름의 합보다 작은 경우는 안에 안에 있는 원이다.
    return OUT


# start를 포함하고 있는 더 큰 원들을 가져온다.
def getBiggerCircles(start):
    bigger_circles = []

    # 기준이 되는 원의 x좌표와 반지름
    sx, sr = start
    for i, circle in enumerate(circles):
        if i == 0:
            continue

        x, r = circle

        # 기준이 되는 원보다 반비름이 커야 기준 원을 포함하고 있다.
        # 그리고 서로 내부 관계에 있으야 포함하고 있으면서 더 큰 원들이다.
        if r > sr and getRelation(start, circle) == IN:
            bigger_circles.append(i)
    # 반지름순으로 오름차순 정렬
    bigger_circles.sort(key=lambda x: circles[x][1])
    return bigger_circles


answer = []

# 하나의 원이 다른 원의 내부에 있는 경우
if getRelation(circle_a, circle_b) == IN:
    ax, ar = circle_a
    bx, br = circle_b

    # A가 더 큰 경우에는  B -> A 경로를 찾아서 뒤집으면 된다.
    if ar < br:
        biggerCircles = getBiggerCircles(circle_b)
        answer.append(b)
        for idx in biggerCircles:
            answer.append(idx)
            if idx == a:
                break

        # 뒤집기
        answer = answer[::-1]

    # B가 더 큰 경우에는 A -> B 경로를 찾으면 된다.
    else:
        biggerCircles = getBiggerCircles(circle_a)
        answer.append(a)

        for idx in biggerCircles:
            answer.append(idx)
            if idx == b:
                break

# 두 원이 외부에 있는 경우
else:
    bigger_than_a = getBiggerCircles(circle_a)
    bigger_than_b = getBiggerCircles(circle_b)

    visited = [False] * (n + 1)

    common_ancestor = 0
    # a의 조상들 체크
    for idx in bigger_than_a:
        visited[idx] = True

    # a,b의 공통 조상 찾기
    for idx in bigger_than_b:
        if visited[idx] == True:
            common_ancestor = idx
            break

    # a -> 공통 조상 경로
    temp1 = [a]
    for idx in bigger_than_a:
        temp1.append(idx)
        if idx == common_ancestor:
            break

    # 공통 조상이 0인 경우 0 추가
    if common_ancestor == 0:
        temp1.append(0)

    # 공통조상 -> b 경로
    temp2 = [b]
    for idx in bigger_than_b:
        if idx == common_ancestor:
            break
        temp2.append(idx)


    answer = temp1 + temp2[::-1]


print(len(answer))
print(*answer)

 

두번째 풀이입니다. 최소 공통 조상을 찾기 위해 더 나은 풀이를 찾다가 발견한 문제입니다. 서로의 포함관계 여부를 따지지 않고 최소 공통 조상을 구할 수 있는 것이 특징입니다. 원리는 다음과 같습니다.

 

먼저 원의 x축과 만난 왼쪽 좌표를 기준으로 오름차순으로 정렬합니다. 각각의 원들을 탐색하면서 바로 직속 조상을 찾기 위해 스택을 이용합니다. 현재 원보다 왼쪽 좌표가 작은 원들의 특징은 2가지 입니다. 현재 원을 포함하고 있는 원이거나 현재 원보다 왼쪽에 있는 겹치지 않는 원입니다. 스택에 현재 좌표보다 왼쪽 좌표가 더 작은 원의 오른쪽 좌표가 저장되어 있고 만약 이 오른쪽 좌표보다 현재 원의 왼쪽 좌표가 더 크면 포함 관계가 아니므로 pop 해서 버리고 그 반대의 경우에는 포함하고 있는 부모 원이므로 현재 원의 부모 idx를 저장해둡니다. 

 

모든 원의 부모 원을 알고 있으므로 a와 b의 부모 원들의 리스트를 마찬가지로 찾아줍니다. 그 다음, 두 리스트에서 마지막 원소들을 비교해서 달라지는 경우가 곧 부모가 다른 경우입니다. 이 부모가 달라지기 직전에 겹쳤던 원이 최소 공통 조상이 되게 됩니다. 그리고 현재 각각의 리스트에 남아있는 원들은 A와 B의 조상들이므로 곧 A->B로 이동하는 경로가 되게 됩니다.

 

 

import sys

# sys.stdin = open("input.txt", "r")

input = sys.stdin.readline

n = int(input())

circles = []

for _ in range(n):
    num, x, r = tuple(map(int, input().split()))
    # 원의 왼쪽, 오른쪽 좌표를 저장
    circles.append((x - r, x + r, num))

a, b = tuple(map(int, input().split()))

# 왼쪽 좌표를 기준으로한 오름차순 정렬
circles.sort()

# 각 원의 부모 원을 찾아줄 스택
stack = [(1e9, 0)]

# 각 원의 부모 원의 인덱스를 저장할 리스트
parent = [0 for x in range(n + 1)]

for i in range(n):
    left, right, idx = circles[i]

    # 만약 왼쪽에 존재하는 원의 오른쪽이 현재 원의 왼쪽보다 작으면 서로 밖에 존재하는 원이므로 스택에서 제거해준다.
    while stack[-1][0] < left:
        stack.pop()

    # 현재 원을 포함하는 바로 한단계 위 부모 원의 인덱스를 저장
    parent[idx] = stack[-1][1]
    stack.append((right, idx))

route_a = [a]
route_b = [b]

# 원 A의 조상들을 탐색해서 넣어준다.
while a:
    a = parent[a]
    route_a.append(a)

# 원 B의 조상들을 탐색해서 넣어준다.
while b:
    b = parent[b]
    route_b.append(b)

# a와 b의 조상이 달라지기 직전의 last가 최소 공통 조상이므로 저장해둔다.
last = 0

# a와 b의 조상이 달라질 때까지 pop을 해준다.
while route_a and route_b and route_a[-1] == route_b[-1]:
    last = route_a[-1]
    route_a.pop()
    route_b.pop()

# 정답 출력
print(len(route_a) + len(route_b) + 1)

for c in route_a:
    print(c , end=' ')

print(last, end=' ')

for c in route_b[::-1]:
    print(c, end = ' ')