9205번: 맥주 마시면서 걸어가기

제한사항

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)

각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).

다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)

송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)

문제 정리

출발점에서 편의점을 들려서 도착점으로 가거나, 출발점에서 바로 도착점으로 간다.

접근 방법

출발점에서 도착점에 도달 가능한 경우가 무엇일까요? 딱 밑에 두 가지 경우입니다.

1. 출발지에서 도착점까지 거리가 1000m 이하일 때
2. 도착 가능한 편의점에서 도착점까지 거리가 1000m 이하일 때

처음 실수

저는 처음에 편의점에 접근 순서가 상관 있을 것이라고 생각해서 방문 여부를 초기화했습니다.

시간복잡도는 O(n^n)이 되며 100^100이라는 엄청 오랜 시간이 걸립니다. 따라서, 테스트 케이스 자체는 전부 통과하겠지만 정답이 아닙니다. 애초에 편의점에 어떻게 도달하느냐는 중요하지 않습니다. 편의점에 도달하기만 하면 되므로 방문을 취소할 필요가 없습니다.

복잡도

시간복잡도 : O(VE) = O(VV) ⇒ O(N*N) = O(N^2)

코드

[C++]

#include "iostream"
#include "vector"
#include "string"

using namespace std;

const int BEER_COUNT = 20;
const int DISTANCE_PER_BEER = 50;
const int MAXIMUM_DISTANCE = BEER_COUNT * DISTANCE_PER_BEER;

string solution(const pair<int, int> &homePosition, const pair<int, int> &destinationPosition, const vector<pair<int, int>> &martPositions);
int getDistanceTwoPositions(const pair<int, int> &p1, const pair<int, int> &p2);
bool dfs(const pair<int, int> &currentPosition, const pair<int, int> &destinationPosition, const vector<pair<int, int>> &martPositions, bool (&visited)[101]);

string solution(const pair<int, int> &homePosition, const pair<int, int> &destinationPosition, const vector<pair<int, int>> &martPositions) {
    bool visited[101] = {false, };
    if (dfs(homePosition, destinationPosition, martPositions, visited)) {
        return "happy";
    }
    return "sad";
}

int getDistanceTwoPositions(const pair<int, int> &p1, const pair<int, int> &p2) {
    return abs(p1.first - p2.first) + abs(p1.second - p2.second);
}

bool dfs(const pair<int, int> &currentPosition, const pair<int, int> &destinationPosition, const vector<pair<int, int>> &martPositions, bool (&visited)[101]) {
    if (getDistanceTwoPositions(currentPosition, destinationPosition) <= MAXIMUM_DISTANCE) {
        return true;
    }

    for (int i = 0; i < martPositions.size(); i++) {
        if (visited[i]) {
            continue;
        }
        if (getDistanceTwoPositions(currentPosition, martPositions[i]) > MAXIMUM_DISTANCE) {
            continue;
        }

        visited[i] = true;
        if (dfs(martPositions[i], destinationPosition, martPositions, visited)) {
            return true;
        }
    }

    return false;
}

int main() {
    int testcaseCnt;
    string answer;
    cin >> testcaseCnt;
    for (int i = 1; i <= testcaseCnt; i++) {
        int martsCnt;
        cin >> martsCnt;

        int homeX, homeY;
        cin >> homeX >> homeY;
        pair<int, int> homePosition = make_pair(homeX, homeY);

        vector<pair<int, int>> martPositions;
        for (int j = 0; j < martsCnt; j++) {
            int martX, martY;
            cin >> martX >> martY;
            martPositions.push_back(make_pair(martX, martY));
        }

        int destinationX, destinationY;
        cin >> destinationX >> destinationY;
        pair<int, int> destinationPosition = make_pair(destinationX, destinationY);

        answer.append(solution(homePosition, destinationPosition, martPositions)).append("\\n");
    }
    cout << answer;
    return 0;
}

[Kotlin]

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.LinkedList
import kotlin.math.abs

const val MAXIMUM_BEER_COUNT = 20
const val DISTANCE_PER_BEER = 50
const val DISTANCE_LIMIT = MAXIMUM_BEER_COUNT * DISTANCE_PER_BEER

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var n = readLine().toInt()
    val output = StringBuilder()

    while (n-- > 0) {
        val cntOfMart = readLine().toInt()
        val homeInput = readLine().split(" ").map { it.toInt() }.toIntArray()

        val positionOfHome = homeInput[0] to homeInput[1]
        val positionsOfMarts = LinkedList<Pair<Int, Int>>()
        repeat(cntOfMart) {
            val martInput = readLine().split(" ").map { it.toInt() }.toIntArray()
            val positionOfMart = martInput[0] to martInput[1]
            positionsOfMarts.add(positionOfMart)
        }
        val destinationInput = readLine().split(" ").map { it.toInt() }.toIntArray()
        val positionOfDestination = destinationInput[0] to destinationInput[1]

        if (abs(positionOfHome.first - positionOfDestination.first) + abs(positionOfHome.second - positionOfDestination.second) <= DISTANCE_LIMIT) {
            output.append("happy\\n")
            continue
        }

        val result = solution(positionOfHome, positionsOfMarts, positionOfDestination)
        output.append(result).append("\\n")
    }

    println(output)
}

fun solution(positionOfHome: Pair<Int, Int>, positionsOfMarts: List<Pair<Int, Int>>, positionOfDestination: Pair<Int, Int>): String {
    if (dfs(positionOfHome, positionsOfMarts, BooleanArray(positionsOfMarts.size), positionOfDestination)) {
        return "happy"
    }
    return "sad"
}

fun dfs(currentPosition: Pair<Int, Int>, positionsOfMarts: List<Pair<Int, Int>>, visited: BooleanArray, positionOfDestination: Pair<Int, Int>): Boolean {
    if (getDistanceOfTwoPositions(currentPosition, positionOfDestination) <= DISTANCE_LIMIT) {
        return true
    }
    for (i in positionsOfMarts.indices) {
        if (visited[i]) {
            continue
        }
        if (getDistanceOfTwoPositions(currentPosition, positionsOfMarts[i]) > DISTANCE_LIMIT) {
            continue
        }

        visited[i] = true
        if (dfs(positionsOfMarts[i], positionsOfMarts, visited, positionOfDestination)) {
            return true
        }
				// 문제가 됐던 부분
				visited[i] = false
    }
    return false
}

fun getDistanceOfTwoPositions(p1: Pair<Int, Int>, p2: Pair<Int, Int>): Int {
    return abs(p1.first - p2.first) + abs(p1.second - p2.second)
}