1767번 프로세서 연결하기

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf#

SW 역량 테스트의 감시가 생각났었다. 이 방식으로 풀었다. 15683번 감시

문제가 생각보다 쉬워서, 금방 풀고 제출하였더니, 49번 째에서 틀렸다.

근데 아무리 생각해봐도 반례를 못 찾아서, 댓글을 참고하였다.

나는 무려 3가지나 놓치고 있었다.

1. core가 core들에 의해 둘러 쌓인 경우를 생각하지 못 했다.

예를 들면 아래와 같다. MIN = 1e9 값이 그대로 출력되고 있었다.

1
3
0 1 0
1 1 1
0 1 0
#1 0
 
 
1
5
0 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0
#1 8

2. 문제에서

▶ 최대한 많은 Core에 전원을 연결하였을 경우, 전선 길이의 합을 구하고자 한다.

   단, 여러 방법이 있을 경우, 전선 길이의 합이 최소가 되는 값을 구하라.

라고 언급되어 있다. 즉, 최대한 많은 core이므로, 무조건 우선순위는 core의 개수가 많을 때이다.

이 부분을 생각하지 못 했다. 즉, core가 많을 수록, 그리고 많을 때의 전선 길이의 합이 최소가 될 수록.

이 부분을 고려하지 않고, 전선 길이의 최솟값만 고려했다. 근데 49번 째 테스트 케이스까지 간게 신기하다.

3. 

4방향을 탐색하고, core의 개수를 증가시켜주었는데(=core 연결), 

현재 core를 연결하지 않고, 그 다음 core를 연결하는 경우도 추가해줘야한다.

123번 째 줄.

49번 째 테스트 케이스에서 틀린 코드

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
using namespace std;
 
int N = 0, Map[15][15] = { 0, }, MIN = 0;
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
//      d =   0  1  2   3
 
vector<pair<int, int> > v;
 
void draw(int r, int c, int d, int value)
{
    int y = r + dy[d];
    int x = c + dx[d];
 
    while (1)
    {
        if (y < 0 || y >= N || x < 0 || x >= N) break;
 
        Map[y][x] += value;
        y += dy[d];
        x += dx[d];
    }
}
 
int chk()
{
    int ret = 0;
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (Map[i][j] == 100) ++ret;
 
    return ret;
}
 
bool can(int r, int c, int d)
{
    int y = r + dy[d];
    int x = c + dx[d];
 
    while (1)
    {
        if (y < 0 || y >= N || x < 0 || x >= N) break;
 
        if (Map[y][x] >= 1) return false;
 
        y += dy[d];
        x += dx[d];
    }
 
    return true;
}
 
void simulation(int idx)
{
    if (idx == v.size())
    {
        MIN = min(MIN, chk());
        return;
    }
 
    int y = v.at(idx).first;
    int x = v.at(idx).second;
 
    for (int i = 0; i < 4; i++)
        if (can(y, x, i))
        {
            draw(y, x, i, 100);
            simulation(idx + 1);
            draw(y, x, i, -100);
        }
}
 
int main(void)
{
    int m = 0, T = 0;
 
    scanf("%d", &T);
 
    for (int t = 1; t <= T; t++)
    {
        MIN = 2e9;
 
        scanf("%d", &N);
 
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
            {
                scanf("%d", &Map[i][j]);
 
                if (Map[i][j] == 1 && i != 0 && i != N - 1 && j != 0 && j != N - 1)
                {
                    v.push_back({ i ,j });
                }
            }
 
        simulation(0);
 
        printf("#%d %d\n", t, MIN);
 
        v.clear();
    }
 
    return 0;
}

정답 코드

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
//#pragma warning(disable:4996)  
//#pragma comment(linker, "/STACK:336777216")
// SWEA에서는 pragma 사용하면, 오류 뜸.
 
using namespace std;
 
int N = 0, Map[15][15] = { 0, }, MIN = 0, MAX = 0;
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
// 방향은 총 4가지 d =   0  1  2   3
 
vector<pair<int, int> > v;
 
void draw(int r, int c, int d, int value) // Map 배열에 value 부여
{
    int y = r + dy[d];
    int x = c + dx[d];
 
    while (1)
    {
        if (y < 0 || y >= N || x < 0 || x >= N) break;
 
        Map[y][x] += value;
 
        y += dy[d];
        x += dx[d];
    }
}
 
int chk() // 전선의 길이를 센다
{
    int ret = 0;
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (Map[i][j] == 100)
                ++ret;
 
    return ret;
}
 
bool can(int r, int c, int d) // 그릴 수 있는지 미리 검사
{
    int y = r + dy[d];
    int x = c + dx[d];
 
    while (1)
    {
        if (y < 0 || y >= N || x < 0 || x >= N) break;
 
        if (Map[y][x] >= 1) return false;
 
        y += dy[d];
        x += dx[d];
    }
 
    return true;
}
 
bool input(int r, int c) // v vector에 넣을 수 있는 core를 골라낸다.
{
    // 4가지 방향 모두 1(core)이 있으면, 당연히 무조건 0이 되기 때문에,
    // 굳이 v vector에 넣을 필요가 없다.
 
    bool use[4] = { false, };
 
    for (int i = 0; i < 4; i++)
    {
        int y = r + dy[i];
        int x = c + dx[i];
 
        if (y < 0 || y >= N || x < 0 || x >= N) use[i] = true;
        else if (Map[y][x] == 1) use[i] = true;
    }
 
    for (int i = 0; i < 4; i++) if (!use[i]) return true;
 
    return false;
}
 
void simulation(int idx, int core)
{
    if (idx == v.size()) // 우선 끝까지 탐색
    {
        int line = chk();
 
        if (MAX < core) // 연결한 코어의 개수가 더 많다면
        {
            MAX = core; // core 개수 갱신
            MIN = line; // 무조건 갱신(전제 조건 자체가 최대한 많은 core이므로)
        }
        else if (MAX == core) MIN = min(MIN, line); // 똑같다면, 혹시나 더 적을 수 있으니
 
        return;
    }
 
    int y = v.at(idx).first;
    int x = v.at(idx).second;
 
    for (int i = 0; i < 4; i++)
        if (can(y, x, i))
        {
            draw(y, x, i, 100);
            simulation(idx + 1, core + 1);
            draw(y, x, i, -100);
        }
 
    // 현재의 core를 연결 하지 않고, 다음 core를 연결하는 경우
    simulation(idx + 1, core);
}
 
int main(void)
{
    int m = 0, T = 0;
 
    scanf("%d", &T);
 
    for (int t = 1; t <= T; t++)
    {
        v.clear();
 
        MIN = 2e9;
        MAX = -1;
 
        scanf("%d", &N);
 
        for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) scanf("%d", &Map[i][j]);
 
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                if (Map[i][j] == 1 && input(i, j) && i != 0 && i != N - 1 && j != 0 && j != N - 1)
                    v.push_back({ i, j });
 
        simulation(0, 0);
 
        if (MIN == 2e9) MIN = 0; // 예외 처리
 
        printf("#%d %d\n", t, MIN);
    }
 
    return 0;
}