글 읽기 - C++) 치킨배달 백트래킹 질문

woogie 1년 전 0

안녕하세요. 고수님들 백트래킹에 익숙치 않아서 질문 드립니다.

vector에 데이터타입을 구조체를 만들어 y,x를 만들었습니다.

성공한 코드에서는 vector에 변수 c를 하나 더 만들어

for(int i=0; i<c.size(); i++)

c.push_back(chicken[i]);

c.pop_back(); 을 주어 성공하였으나

굳이 chicken이라는 vector가 존재하는데 왜 또 c라는 변수를 주어 새로 값을 갱신하는것이

필요하지 않다고 느껴 답을 제출하였더니 틀렸습니다.

단순히 방문유무만 체크하여도 모든 경우의 수를 체크하는게 아닌지요?

천천히 설명해주시면 정말 감사드리겠습니다 !!

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

#define MAX 50

using namespace std;

struct Position {
  int y;
  int x;
};

int Map[MAX][MAX];
int visited[13];
int N,M;
int ans = 9999;

//시도해보았으나 틀린 코드
vector<Position> chicken, house;
//성공한코드 vector<Position> chicken, house, c;

int dist() {

  int sum = 0;
  //시도해보았으나 틀린 코드  
  for(int i=0; i<house.size(); i++) {
    int r1 = house[i].y;
    int c1 = house[i].x;
    int distance = 9999;
    for(int j=0; j<chicken.size(); j++) {
      int r2 = chicken[j].y;
      int c2 = chicken[j].x;
      int temp = abs(r1-r2) + abs(c1-c2);
      distance = min(distance,temp);
    }
    /*성공한 코드
    for(int i=0; i<house.size(); i++) {
        int r1 = house[i].y;
        int c1 = house[i].x;
        int distance = 9999;
        for(int j=0; j<c.size(); j++) {
          int r2 = c[j].y;
          int c2 = c[j].x;
          int temp = abs(r1-r2) + abs(c1-c2);
          distance = min(distance,temp);
    }
    */
    sum += distance;
  }
  return sum;
}

void dfs(int idx, int cnt) {

  if(cnt == M) {
    ans = min(ans,dist());
    return;
  }
  //시도해보았으나 틀린코드  
  for(int i=idx; i<chicken.size(); i++) {
    if(!visited[i]) {
      visited[i] = true;
      dfs(i+1, cnt+1);
      visited[i] = false;
    }
  }
  /*성공한 코드
  for(int i=idx; i<chicken.size(); i++) {
    if(!visited[i]) {
      visited[i] = true;
      c.push_back(chicken[i]);
      dfs(i+1, cnt+1);
      visited[i] = false;
      c.pop_back();  
    }
  }
  */
}

int main() {

  cin >> N >> M;

  for(int y=0; y<N; y++) {
    for(int x=0; x<N; x++) {
      cin >> Map[y][x];
      if(Map[y][x]==1) {
        house.push_back({y,x});
      }
      if(Map[y][x]==2) {
        chicken.push_back({y,x});
      }
    }
  }

  dfs(0,0);
  cout << ans << endl;

  return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

C++) 치킨배달 백트래킹 질문

woogie 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말