글 읽기 - 14948 군대탈출 반례 하나만 부탁드립니다 (C++14) (반례추가)

roeniss 4년 전 2

--------------------------------- (수정)---------------------------------

이론은 맞았는데 구현에 큰 빈틈이 있었네요. 해결하였습니다.

아래 댓글로 반례 하나 만들어 두었습니다. 누군가에게 도움이 되길...

--------------------------------- (수정 끝)---------------------------------

실력이 많이 부족해서 예외 케이스를 못잡고 있습니다. 반례 하나만 찾아주시면 정말 감사하겠습니다.

(경고) 이 아래 텍스트로는 로직을 간단하게 설명하였으니 조심하시길 바랍니다!

# 로직 설명

dfs + 이분탐색 으로 접근했습니다.

지나간 자리를 checkbox라는 배열로 선언했고, 이분탐색 middle값이 갱신될때마다 리셋해주었습니다.

특별히, dfs 내에서 다음 지점으로 나아갈 때, 이미 지나간 자리여도 특수장비를 써서 지나갔었다면 && 현재 특수장비를 안쓰고 그 지점에 갈 수 있다면 해당 지점으로 가도록 설정하였습니다. 즉, 장비는 아낄 수 있으면 아끼도록 하였습니다.

게시판에 있는 반례 데이터는 모두 통과하였습니다.

감사합니다.

#include <iostream>
//#include <vector>
//#include <string>
//#include <fstream>
//#include <deque>
//#include <stack>
#include <algorithm>
//#include <queue>
//#include <cmath>

#define S(x) int (x); scanf("%d", &x);
#define C(x) int (x); cin >> (x);
#define CC(x) cin >> (x);
#define SS(x) scanf("%d ", &x);
#define P(x) printf("%d\n", (x));
#define ll long long int
#define ee '\n';
using namespace std;
typedef pair<int, int> pii;

using namespace std;


int **arr;
int **check; // 0: 안감, 1: 스킬 사용, 2: 스킬 미사용
int n, m;
int arrow[8][2] = {
        {1,  0}, // 아래
        {0,  1}, // 우측
        {-1, 0}, // 왼쪽
        {0,  -1}, // 위
        {2,  0},
        {0,  2},
        {-2, 0},
        {0,  -2}
};

// 리턴값: 이 레벨을 맥시멈으로 수행이 가능한가
bool dfs(int level, bool skill, int y, int x, int **checkbox) {
    if (y == n - 1 && x == m - 1) return true;

    bool possible = false;
    for (int i = 0; i < 4; ++i) {
        int yy = y + arrow[i][0]; // 세로
        int xx = x + arrow[i][1]; // 가로
        if (0 <= xx && 0 <= yy && yy < n && xx < m) {
            int next = arr[yy][xx];
            if (next <= level) {
                if ((checkbox[yy][xx] == 1 && skill) || checkbox[yy][xx] == 0) {
                    checkbox[yy][xx] = 2;
                    if (dfs(level, skill, yy, xx, checkbox)) possible = true;
                }
            }
        }
    }
    if (skill)
        for (int i = 4; i < 8; ++i) {
            int yy = y + arrow[i][0]; // 세로
            int xx = x + arrow[i][1]; // 가로
            if (0 <= xx && 0 <= yy && yy < n && xx < m) {
                int next = arr[yy][xx];
                if (next <= level && checkbox[yy][xx] == 0) {
                    checkbox[yy][xx] = 1;
                    if (dfs(level, false, yy, xx, checkbox)) possible = true;
                }
            }
        }
    return possible;
}

void reset_check(int **arr) {
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) arr[i][j] = 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    CC(n)
    CC(m)
    int max_available = -1, min_available = 1000000001;
    arr = (int **) malloc(n * sizeof(int *));
    check = (int **) malloc(n * sizeof(int *));
    for (int i = 0; i < n; ++i) {
        arr[i] = (int *) malloc(m * sizeof(int));
        check[i] = (int *) malloc(m * sizeof(int));
    }
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            cin >> arr[i][j];
            max_available = max(max_available, arr[i][j]);
            min_available = min(min_available, arr[i][j]);
            check[i][j] = 0;
        }

    int l = max(arr[0][0], arr[n - 1][m - 1]), r = max_available;
    int answer;
    while (l <= r) {
        int middle = (l + r) / 2;
        check[0][0] = 1;
        bool possible = dfs(middle, true, 0, 0, check);
        if (possible) {
            answer = middle;
            r = middle - 1;
        } else l = middle + 1;
        reset_check(check);
    }

    cout << answer << ee

    return 0;
}

10 10
0 0 0 0 0 9 9 9 9 9
9 9 9 9 0 9 9 9 9 9
0 0 0 9 0 9 9 9 9 9
0 9 0 9 0 9 9 9 9 9
0 9 0 0 0 9 9 9 9 9
0 9 9 9 0 9 9 9 9 9
0 9 9 9 9 9 9 9 9 9
0 0 0 0 0 0 0 0 0 0
0 9 9 9 0 9 9 9 9 9
9 9 9 9 0 9 9 9 9 0

답: 0

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

문제

문제

출처

ICPC

14948 군대탈출 반례 하나만 부탁드립니다 (C++14) (반례추가)

roeniss 4년 전 2

roeniss 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말