[Algorithm] 백준 - 진우의 민트초코우유 (20208번)

문제

[백준] 진우의 민트초코우유

20208번: 진우의 민트초코우유

 

사용 알고리즘

- 브루트포스

- 구현

해결방법

• 문제조건에서 우유의 총합이 10개를 넘지 않는 단 것이 포인트
• 가능한 우유 좌표의 순열을 모두 탐색해서, 민우가 집으로 돌아올 수 있다는 전제하에 마실 수 있는 최대 우유 개수를 구한다
  (*순열 : 시퀀스에 담긴 원소를 중복없이 순서에 상관있게 나열하는 것)
  
  • 예를 들면,
    우유가 총 3개 있다고 했을 때, 각각의 우유 좌표를 벡터에 저장한다 {{1,1}, {3,4}, {6,3}}
    • 원소가 3개 있을 때 순열은 다음과 같다. 벡터의 인덱스로 생각하고 순서대로 탐색한다.
      1 2 3 => {1,1} -> {3,4} -> {6,3}
      1 3 2 => {1,1} -> {6,3} -> {3,4}
      2 1 3 => {3,4} -> {1,1} -> {6,3}
      2 3 1 => {3,4} -> {6,3} -> {1,1}
      3 1 2 => {6,3} -> {1,1} -> {3,4}
      3 2 1 => {6,3} -> {3,4} -> {1,1}
    • 탐색하면서 현재위치에서 남은 체력으로 이동이 가능한지 체크한다. 이동 가능한 경우 우유를 마실 수 있다는 의미 이므로 마신우유값을 증가한다
    • 집으로 돌아올 수 있는 경우에만 result를 체크한다

소스코드

사용언어 : c++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M, H;
int town[11][11];
vector<pair<int,int>> vec_milk;
pair<int, int> home;

int result;

int find_milk(vector<int> v)
{
    int milk = 0;
    int power = M;
    int result = 0;
    pair<int, int> start = home;

    for (int& i : v) {
        pair<int, int> p = vec_milk[i-1];
        int y = p.first;
        int x = p.second;

        // 현재위치에서 갈 수 있는지 확인
        int distance = abs(start.first - y) + abs(start.second - x);
        if (distance <= power) {
            milk++;
            power = power - distance + H;
            start = p; // 현재위치 변경

            // 집으로 돌아갈 수 있을 때
            if ((abs(home.first - y) + abs(home.second - x)) <= power) {
                result = milk;
            }
        } else {
            break;
        }
    }

    return result;
}

int main()
{
    cin >> N >> M >> H;

    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cin >> town[i][j];
            if (town[i][j] == 1) {
                home = make_pair(i, j);
            } else if (town[i][j] == 2) {
                vec_milk.push_back(make_pair(i, j));
            }
        }
    }

    // vec_milk 순열 생성 후 find_milk
    int cnt_milk = vec_milk.size();
    vector<int> vec_perm;
    for (int i=1; i<=cnt_milk; i++) {
        vec_perm.push_back(i);
    }

    do {
        result = max(result, find_milk(vec_perm));
    } while(next_permutation(vec_perm.begin(), vec_perm.end()));

    cout << result << endl;

    return 0;
}

next_permutation

* c++ 표준라이브러리로, 오름차순의 배열을 기반으로 순열을 반환해준다
* next_permutation(v.begin(), v.end()) : 매개변수로 순열을 시작할 범위의 첫번 째 주소, 그리고 포함되지 않는 마지막 주소를 넣는다

* 반대로 내림차순의 배열을 기반으로 하는 prev_permutation도 있으며 사용방법은 같다

 

(참고블로그)

velog

 

 

순열을 만들지 않고, 우유 좌표를 담고있는 벡터만을 가지고 dfs를 도는 방법도 있다 (soongle님이 백트래킹 방법이라며 알려주셨다)

(백트래킹)

#include <iostream>
#include <vector>

using namespace std;

int N, M, H;
int result;
int visited[11][11];
pair<int, int> home;
vector<pair<int,int>> vec_milk;

void dfs(pair<int, int> p, int h, int m) // 현재 좌표, 남은 체력, 마신 우유
{
    // 집으로 돌아갈 수 있다면 최대우유 개수 갱신
    if ((abs(p.first - home.first) + abs(p.second - home.second)) <= h) {
        result = max(result, m);
    }

    visited[p.first][p.second] = 1;

    for (pair<int, int>& v : vec_milk) {
        int ny = v.first;
        int nx = v.second;
        int distance = abs(ny-p.first) + abs(nx-p.second);

        // 방문하지 않았고, 남은체력으로 이동가능한 경우
        if (!visited[ny][nx] && (distance <= h)) {
            int next_h = h - distance + H;
            int next_m = m + 1;

            dfs(v, next_h, next_m);

            visited[ny][nx] = 0; // 방문 초기화    
        }
    }

}


int main()
{
    cin >> N >> M >> H;

    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            int n;
            cin >> n;
            if (n == 1) {
                home = make_pair(i, j);
            } else if (n == 2) {
                vec_milk.push_back(make_pair(i, j));
            }
        }
    }

    dfs(home, M, 0);

    cout << result << endl;

    return 0;
}

순열로 해결하는 방법은, 가야할 길(루트)을 미리 조합으로 설정해서 탐색하는 방식인거고, 백트래킹의 경우 조건설정을 통해 현재위치에서 갈 수 있는 곳만 재귀 호출로 이동하는 방식이다. (사실 같은 방법인데, 재귀호출을 하느냐 안하느냐의 차이)

 

 

한줄평

처음엔 전체 좌표에서 4방향 이동하는 방식을 사용해 dfs로 풀었는데 계속 시간초과가 났다;;

검색해보니 전체 좌표를 탐색하는게 아니고 우유 좌표만 활용하는 문제더라. . ( o̴̶̷᷄ ·̫ o̴̶̷̥᷅ )

이런 유형의 문제도 있구나 싶어서 재밌었다 ~

dfs 활용한 코드 (시간초과나요)

#include <iostream>
#include <utility> // pair를 사용하기 위한 헤더 파일
#include <algorithm> // max 함수를 사용하기 위한 헤더 파일

using namespace std;

int N, M, H;
int town[11][11];
int visited[11][11];
pair<int, int> home;
int res;

int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; //상하좌우

void dfs(pair<int, int> p, int h, int m) {
    // 집에 도착한 경우, 결과값 갱신
    if (p == home && visited[p.first][p.second] == 1) {
        res = max(res, m);
        return;
    }

    visited[p.first][p.second] = 1;

    // 상, 하, 좌, 우로 이동하면서 유효한 위치인지 확인하고 DFS 호출
    for (int i = 0; i < 4; i++) {
        int dy = p.first + dir[i][0];
        int dx = p.second + dir[i][1];

        // 유효한 위치인지, 방문한 적 없는지, 체력이 남아있는지 확인
        if (dy >= 0 && dy < N && dx >= 0 && dx < N && h > 0 && (!visited[dy][dx] || (dy == home.first && dx == home.second))) {
            pair<int, int> nextPos(dy, dx);
            int nextH = h - 1;
            int nextM = m;

            // 만약 우유가 있는 위치라면, 우유를 마시고 체력을 회복
            if (town[dy][dx] == 2) {
                nextM++;
                nextH += H;
            }

            if (nextM >= 10) { // 우유 최대 개수는 10개
                return;
            }

            dfs(nextPos, nextH, nextM);

            // DFS가 끝나면, 다음 위치의 방문 여부를 되돌림
            if (nextPos != home) {
                visited[dy][dx] = 0;
            }
        }
    }
}

int main() {
    cin >> N >> M >> H;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> town[i][j];
            if (town[i][j] == 1) {
                home = make_pair(i, j);
            }
        }
    }

    dfs(home, M, 0);

    cout << res << endl;

    return 0;
}