<a target="_blank" href="https://www.acmicpc.net/problem/15686">https://www.acmicpc.net/problem/15686</a> <div><br></div> <div><br></div> <div><br></div> <div>제가 이해한 풀이방법은</div> <div><br></div> <div>치킨집을 줄이고자 하는 수(m)까지 줄여야 하는데</div> <div><br></div> <div>Combination을 통해서 줄일 수 있는 모든 경우의 수를 다 조사하고</div> <div><br></div> <div>최적의 경우를 출력하는 것입니다.</div> <div><br></div> <div>그래서 아래의 코드를 적었습니다.</div> <div><br></div> <div><br></div> <div><br></div> <div><div>#include <bits/stdc++.h></div> <div><br></div> <div>using namespace std;</div> <div><br></div> <div><br></div> <div><br></div> <div>#define EMPTY 0</div> <div>#define HOME 1</div> <div>#define CHICKEN 2</div> <div><br></div> <div><br></div> <div>int n;</div> <div>int m;</div> <div>int **board;</div> <div><br></div> <div><br></div> <div>int score = 999999999;</div> <div><br></div> <div>class Coord</div> <div>{</div> <div>public:</div> <div><span style="white-space:pre;"> </span>int cX, cY;</div> <div><br></div> <div><span style="white-space:pre;"> </span>Coord() : Coord(0, 0)</div> <div><span style="white-space:pre;"> </span>{}</div> <div><br></div> <div><span style="white-space:pre;"> </span>Coord(int x_, int y_) : cX(x_), cY(y_)</div> <div><span style="white-space:pre;"> </span>{}</div> <div><br></div> <div>};</div> <div><br></div> <div><br></div> <div>class Node</div> <div>{</div> <div>public:</div> <div><br></div> <div><span style="white-space:pre;"> </span>vector<Coord> coords;<span style="white-space:pre;"> </span>//치킨 집을 최대 m개만 저장한다.</div> <div><br></div> <div><br></div> <div><span style="white-space:pre;"> </span>Node()</div> <div><span style="white-space:pre;"> </span>{}</div> <div><br></div> <div><span style="white-space:pre;"> </span>Node(vector<Coord> coords_) : coords(coords_)</div> <div><span style="white-space:pre;"> </span>{}</div> <div><br></div> <div>};</div> <div><br></div> <div><br></div> <div>vector<Coord> home;</div> <div>vector<Coord> chicken;</div> <div><br></div> <div>int GetDistance(Coord lhs, Coord rhs)</div> <div>{</div> <div><span style="white-space:pre;"> </span>int dx = lhs.cX - rhs.cX;</div> <div><span style="white-space:pre;"> </span>int dy = lhs.cY - rhs.cY;</div> <div><br></div> <div><span style="white-space:pre;"> </span>if (dx < 0)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>dx = dx * -1;</div> <div><span style="white-space:pre;"> </span>}</div> <div><br></div> <div><span style="white-space:pre;"> </span>if (dy < 0)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>dy = dy * -1;</div> <div><span style="white-space:pre;"> </span>}</div> <div><br></div> <div><span style="white-space:pre;"> </span>return dx + dy;</div> <div><br></div> <div><br></div> <div><br></div> <div>}</div> <div><br></div> <div><br></div> <div><br></div> <div>bool* flag;</div> <div><br></div> <div>void GetChickenDistance(Node tmp_node)</div> <div>{</div> <div><span style="white-space:pre;"> </span>int total_score = 0;</div> <div><span style="white-space:pre;"> </span>int local_score = 999999999;</div> <div><br></div> <div><span style="white-space:pre;"> </span>for (int j = 0; j < home.size(); j++)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>for (int i = 0; i < tmp_node.coords.size(); i++)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>int value = GetDistance(home[j], tmp_node.coords[i]);</div> <div><br></div> <div><span style="white-space:pre;"> </span>if (local_score > value)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>local_score = value;</div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span>}</div> <div><br></div> <div><span style="white-space:pre;"> </span>total_score += local_score;</div> <div><br></div> <div><span style="white-space:pre;"> </span>local_score = 999999999;</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>}</div> <div><br></div> <div><span style="white-space:pre;"> </span>if (score > total_score)</div> <div><span style="white-space:pre;"> </span>score = total_score;</div> <div><br></div> <div>}</div> <div><br></div> <div><br></div> <div><br></div> <div>void DFS(int n_, int k)</div> <div>{</div> <div><span style="white-space:pre;"> </span>if (n_ == k)<span style="white-space:pre;"> </span>//남은 0~n을 모두다 true로 한다.</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>Node tmp_node;</div> <div><br></div> <div><span style="white-space:pre;"> </span>for (int i = 0; i < n_; i++)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>flag[i] = true;</div> <div><span style="white-space:pre;"> </span>}</div> <div><br></div> <div><br></div> <div><span style="white-space:pre;"> </span>for (int i = 0; i < chicken.size(); i++)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>if (flag[i] == true)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>tmp_node.coords.push_back(chicken[i]);</div> <div><br></div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span>}</div> <div><br></div> <div><span style="white-space:pre;"> </span>//tmp_node에 있는 치킨집과 home을 통해 치킨 거리를 계산한다.</div> <div><span style="white-space:pre;"> </span>GetChickenDistance(tmp_node);</div> <div><br></div> <div><span style="white-space:pre;"> </span>for (int i = 0; i < n_; i++)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>flag[i] = false;</div> <div><span style="white-space:pre;"> </span>}</div> <div><br></div> <div><span style="white-space:pre;"> </span>return;</div> <div><br></div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span>else if (k == 1)<span style="white-space:pre;"> </span>//남은 0~n중 하나만 true 이다.</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>for (int j = 0; j < n_; j++)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>Node tmp_node;</div> <div><br></div> <div><br></div> <div><span style="white-space:pre;"> </span>flag[j] = true;</div> <div><br></div> <div><span style="white-space:pre;"> </span>for (int i = 0; i < chicken.size(); i++)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>if (flag[i] == true)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>tmp_node.coords.push_back(chicken[i]);</div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span>}</div> <div><br></div> <div><span style="white-space:pre;"> </span>flag[j] = false;</div> <div><br></div> <div><br></div> <div><span style="white-space:pre;"> </span>//치킨거리 계산</div> <div><br></div> <div><span style="white-space:pre;"> </span>GetChickenDistance(tmp_node);</div> <div><br></div> <div><span style="white-space:pre;"> </span>}</div> <div><br></div> <div><span style="white-space:pre;"> </span>return;</div> <div><br></div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>flag[n_ - 1] = true;</div> <div><span style="white-space:pre;"> </span>DFS(n_ - 1, k - 1);</div> <div><br></div> <div><span style="white-space:pre;"> </span>flag[n_ - 1] = false;</div> <div><span style="white-space:pre;"> </span>DFS(n_ - 1, k);</div> <div><br></div> <div>}</div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>int main(void)</div> <div>{</div> <div><span style="white-space:pre;"> </span>scanf("%d %d", &n, &m);</div> <div><br></div> <div><span style="white-space:pre;"> </span>int input;</div> <div><br></div> <div><span style="white-space:pre;"> </span>for (int j = 0; j < n; j++)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>for (int i = 0; i < n; i++)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>scanf("%d", &input);</div> <div><br></div> <div><span style="white-space:pre;"> </span>if (input == HOME)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>home.push_back(Coord(i, j));</div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span>else if (input == CHICKEN)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>chicken.push_back(Coord(i, j));</div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span>}</div> <div><br></div> <div><br></div> <div><br></div> <div><span style="white-space:pre;"> </span>/*</div> <div><span style="white-space:pre;"> </span>board = new int*[n];</div> <div><br></div> <div><span style="white-space:pre;"> </span>for (int i = 0; i < n; i++)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>board[i] = new int[n];</div> <div><span style="white-space:pre;"> </span>//memset(board[i], 1, n*sizeof(int));</div> <div><span style="white-space:pre;"> </span>}</div> <div><br></div> <div><span style="white-space:pre;"> </span>for (int j = 0; j < n; j++)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>for (int i = 0; i < n; i++)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>scanf("%d", &board[j][i]);</div> <div><br></div> <div><span style="white-space:pre;"> </span>if (board[j][i] == HOME)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>home.push_back(Coord(i, j));</div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span>else if (board[j][i] == CHICKEN)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>chicken.push_back(Coord(i, j));</div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span>*/</div> <div><br></div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>flag = new bool[chicken.size()];</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>for (int i = 0; i < chicken.size(); i++)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>flag[i] = false;</div> <div><span style="white-space:pre;"> </span>}</div> <div><br></div> <div><br></div> <div><span style="white-space:pre;"> </span><span style="font-size:9pt;">DFS(chicken.size(), m);</span></div> <div><span style="white-space:pre;"> </span></div> <div><br></div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>printf("print : %d\n", score);</div> <div><br></div> <div><br></div> <div><br></div> <div><span style="white-space:pre;"> </span>return 0;</div> <div>}</div></div> <div><br></div> <div><br></div> <div><br></div> <div>함수단위로 설명을 드리자면</div> <div><br></div> <div>GetDistance</div> <div> 치킨집과 가정집 사이의 치킨거리를 구한다.</div> <div><br></div> <div><br></div> <div>GetChickenDistance</div> <div> 가정집과 선별된 치킨집 간에 치킨거리 연산을 GetDistance 함수를 통해 서로서로다 수행하고 최소 치킨거리를 구한다.</div> <div><br></div> <div>DFS</div> <div> combination을 통해서 치킨집을 선별하는 함수. 선별이 끝나자 마자 GetChickenDistance 함수로</div> <div> 선별된 치킨집을 통해 얻을 수 있는 최소 치킨거리를 계산한다.</div> <div><br></div> <div><br></div> <div><br></div> <div>크게 3가지 함수로 이루어저 있습니다.</div> <div><br></div> <div>사이트에 올라와 있는 테스트케이스가 모두다 맞는것을 확인하고 제출 하였는데</div> <div><br></div> <div>"틀렸습니다"</div> <div><br></div> <div>가 나오네요...</div> <div><br></div> <div>아무래도 비공개 테스트케이스에서 잘못된 출력이 나와서 그런듯한데</div> <div><br></div> <div>대체 어디가 잘못된걸까요...??</div> <div><br></div> <div>출력이 어떤식으로 잘못된건지 알려주질 않으니 어디서부터 고쳐 나가야 할지 조차 모르겠습니다.</div> <div><br></div> <div>다른사람들 코드랑 비교해 보아도 전체적인 알고리즘도 거의 비슷하고</div> <div><br></div> <div>제가 직접 테스트케이스를 만들어서 여러 프로그램을 같이 돌려보면 출력도 같게 나오는데</div> <div><br></div> <div>뭐가틀린걸까요...??</div> <div><br></div> <div><br></div> <div><br></div> <div>풀소스코드를 통째로 가져와서 질문하는게 안좋은 방법인건 알고있지만</div> <div><br></div> <div>너무 답답하네요 ㅠㅠ.....</div>