[백준] 20208 진우의 민트초코우유 python(pypy), C++

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

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

민트초코가 있는 곳을 방문하고 다시 돌아올수 있는지 사이클을 확인하는 문제이다. 

이때 집과 민트초코 혹은 민트 초코끼리의 거리가 현재 진우의 체력보다 같거나 높아야 다음 단계로 넘어갈수 있다.

 

민트초코가 있는 점을 저장하고 방문하는 순서를 완전 탐색으로 돌려서 찾으면 된다.

 

import sys; input = sys.stdin.readline
answer = 0
visit = None
mint_choco = None
start = None
def dfs(ind, M, H, last, total):
    global answer
    if ind != 0:
        tmp_dist = abs(last[0] - start[0]) + abs(last[1] - start[1])
        if tmp_dist <= M:
            answer = max(answer, total)
    if ind == len(mint_choco):
        return

    for i in range(len(mint_choco)):
        if visit[i]: continue
        tmp_dist = abs(last[0] - mint_choco[i][0]) + abs(last[1] - mint_choco[i][1])
        if M < tmp_dist: continue
        visit[i] = True
        dfs(ind + 1, M + H - tmp_dist, H, mint_choco[i], total + 1)
        visit[i] = False


def main():
    N, M, H = map(int, input().split())
    global visit, mint_choco, start
    mint_choco = []
    for i in range(N):
        tmp = list(map(int, input().split()))
        for j in range(N):
            if tmp[j] == 1:
                start = (i, j)
            elif tmp[j] == 2:
                mint_choco.append((i, j))
    visit = [False for _ in range(len(mint_choco))]
    # dfs(ind, M, H, last, total)
    dfs(0, M, H, start, 0)

    print(answer)


if __name__ == '__main__':
    main()

#include<iostream>
#include<vector>
#define max(x, y) (x < y) ? y : x
using namespace std;

int answer, H;
vector<pair<int, int>> mint_choco;
vector<bool> visit;
pair<int, int> start;

int abs(int x) {
   return (x < 0) ? -x : x;
}

int dist(pair<int, int> a, pair<int, int> b) {
   return abs(a.first - b.first) + abs(a.second - b.second);
}

void dfs(int ind, int M, pair<int,int> last, int total) {
   if (ind) {
      if (dist(last, start) <= M) {
         answer = max(answer, total);
      }
   }
   if (ind == mint_choco.size()) return;

   for (int i = 0; i < mint_choco.size(); i++)
   {
      if (visit[i]) continue;
      if (M < dist(last, mint_choco[i])) continue;
      visit[i] = true;
      dfs(ind + 1, M + H - dist(last, mint_choco[i]), mint_choco[i], total + 1);
      visit[i] = false;
   }
}

int main() {
   //ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   int N, M, i, j, tmp;
   cin >> N >> M >> H;
   for (i = 0; i < N; i++)
   {
      for (j = 0; j < N; j++)
      {
         cin >> tmp;
         if (tmp == 1) {
            start.first = i;
            start.second = j;
         }
         else if (tmp == 2) {
            mint_choco.push_back(make_pair(i, j));
         }
      }
   }
   for (i = 0; i < mint_choco.size(); i++)
   {
      visit.push_back(0);
   }
   dfs(0, M, start, 0);
   cout << answer << '\n';
   return 0;
}