BOJ 16491 - 대피소 찾기 링크
(2023.09.22 기준 G1)

문제

N개의 로봇과 N개의 대피소가 있다. 하나의 대피소에는 하나의 로봇만 수용할 수 있고, 로봇마다 하나의 대피소를 할당하려 한다. 로봇은 대피소로 이동할 때, 직선경로로 이동한다. 이 때, 모든 로봇의 대피소로 이동하는 직선경로가 겹치지 않게끔 로봇마다 할당된 대피소 출력

알고리즘

모든 경우의 수를 가지치기 하면서 살펴봐야 한다. 선분 교차 판정으로 하여금 백트래킹

풀이

로봇 차례대로, 아직 로봇을 수용하지 않은 대피소 하나씩 연결하면서 직전까지 연결된 로봇과 대피소의 직선경로들과 겹치지 않는지 선분 교차 판정으로 확인하자. 만약, 이런 식으로 모든 로봇에 대피소를 할당했다면 성공. 실패했다면 다른 대피소를 할당해보면서 백트래킹을 하면 된다.

코드를 보면 바로 이해가 갈 것이다.

코드

• C++

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> pii;

const int MAXN = 100;

int N, RtoS[MAXN], visited[MAXN];
pii R[MAXN], S[MAXN];

int ccw(pii a, pii b, pii c){
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

bool is_intersect(pii a, pii b, pii c, pii d){
    int ab = ccw(a, b, c) * ccw(a, b, d);
    int cd = ccw(c, d, a) * ccw(c, d, b);
    if (!ab && !cd){
        if (a > b) swap(a, b);
        if (c > d) swap(c, d);
        return c <= b && a <= d;
    }
    return ab <= 0 && cd <= 0;
}

bool dfs(int r){
    if (r == N) return true;

    for (int s = 0; s < N; s++){

        // 로봇이 할당되지 않은 대피소를 우선 찾는다.
        if (visited[s]) continue;

        // 찾은 대피소와 로봇을 이은 직선경로가 다른 로봇의 대피 직선경로와 겹치는지 확인
        bool result = true;
        for (int i = 0; i < r; i++) if (is_intersect(R[r], S[s], R[i], S[RtoS[i]])){
            result = false;
            break;
        }

        // 겹친다면 다른 대피소 찾기
        if (!result) continue;

        // 겹치지 않는다면 대피소를 할당하고 남은 로봇들에 대피소를 할당하러 가기
        RtoS[r] = s;
        visited[s] = true;
        if (dfs(r + 1)) // 할당이 전부 성공했다면 True 반환
            return true;
        RtoS[r] = -1; // 실패했다면 다른 대피소 찾기
        visited[s] = false;
    }

    // 모두 실패한다면 현재 할당된 대피소는 불가능한 것
    return false;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 0; i < N; i++) cin >> R[i].x >> R[i].y; // robot
    for (int i = 0; i < N; i++) cin >> S[i].x >> S[i].y; // shelter

    fill(RtoS, RtoS + N, -1); // 로봇마다 할당된 대피소
    fill(visited, visited + N, false); // 대피소마다 로봇이 할당되었는지 체크
    dfs(0);

    for (int i = 0; i < N; i++) cout << RtoS[i] + 1 << '\n';
}

• Python

import sys; input = sys.stdin.readline

def ccw(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1])

def is_intersect(a, b, c, d):
    ab = ccw(a, b, c) * ccw(a, b, d)
    cd = ccw(c, d, a) * ccw(c, d, b)
    if not ab and not cd:
        if a > b:
            a, b = b, a
        if c > d:
            c, d = d, c
        return c <= b and a <= d
    return ab <= 0 and cd <= 0

def dfs(r):
    if r == N:
        return True

    for s in range(N):

        # 로봇이 할당되지 않은 대피소를 우선 찾는다.
        if visited[s]:
            continue

        # 찾은 대피소와 로봇을 이은 직선경로가 다른 로봇의 대피 직선경로와 겹치는지 확인
        result = True
        for i in range(r):
            if is_intersect(R[r], S[s], R[i], S[RtoS[i]]):
                result = False
                break

        # 겹친다면 다른 대피소 찾기
        if not result:
            continue

        # 겹치지 않는다면 대피소를 할당하고 남은 로봇들에 대피소를 할당하러 가기
        RtoS[r] = s
        visited[s] = True
        if dfs(r + 1): # 할당이 전부 성공했다면 True 반환
            return True
        RtoS[r] = -1 # 실패했다면 다른 대피소 찾기
        visited[s] = False

    # 모두 실패한다면 현재 할당된 대피소는 불가능한 것
    return False
            
N = int(input())
R = [tuple(map(int, input().split())) for _ in range(N)] # robot
S = [tuple(map(int, input().split())) for _ in range(N)] # shelter

RtoS = [-1] * N # 로봇마다 할당된 대피소
visited = [False] * N # 대피소마다 로봇이 할당되었는지 체크
dfs(0)

for s in RtoS:
    print(s + 1)