글 읽기 - [C++]몇시간동안 이 문제만 붙들고 있네요.. 도와주세요

yoon980208 3년 전 0

로직은 맞는 것 같은데 어떤 부분인지 정답이 아닌 더 큰 값이 나옵니다. 혹시 이유를 아시는 분 있으실까요 ...

1. 물고기를 잡아먹는다

2. 물고기를 이동시킨다

3. 상어를 이동시킨다

로직으로 DFS를 돌리고 있습니다..!

#include <iostream>
#include <queue>
#include <map>
#include <cstring>
using namespace std;
struct Dir {
    int y;
    int x;
    Dir(int _y, int _x) {
        y = _y;
        x = _x;
    };
};

struct Fish {
    int y;
    int x;
    bool isAlive;
    int dir;
    Fish(int _y, int _x, bool _isAlive, int _dir) {
        y = _y;
        x = _x;
        isAlive = _isAlive;
        dir = _dir;
    };
};

Dir moveDir[8] = {{-1, 0},{-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}}; //반시계 방향으로 방향정렬
int room[4][4];
vector<Fish> fishes(17, Fish(0, 0, 0, true)); //물고기 번호 index에 물고기 위치를 담는다
int answer = 0;
void input() {
    for(int i=0; i<4; i++) {
        for(int j=0; j<4; j++) {
            int a, b;
            cin>>a >> b;
            room[i][j] = a;
            fishes[a] = Fish(i, j, true, b-1);
        }
    }
}

//경계값 벗어나는지 확인하는 함수
bool isAvailable(int y, int x) {
    if(0 <= y && y < 4 && 0<= x && x< 4) return true;
    return false;
}

void DFS(int map[4][4], vector<Fish> fishes, int y, int x, int sum) {
    
    //인자에 있는 변수값을 그대로 사용하는 것은 위험한 방식이기 때문에
    //임시 변수값을 만들고 값을 담아준다
    /*******************************************************************************************/
    int cpy_map[4][4];
    memcpy(cpy_map, map, sizeof(cpy_map));
    vector<Fish> cpy_fishes;
    for(int i=0; i<fishes.size(); i++) cpy_fishes.push_back(fishes[i]);
    /*******************************************************************************************/
    
    /*1: 잡아먹자!*/
    int currentIdx = cpy_map[y][x];
    sum += currentIdx;
    cpy_map[y][x] = 0;
    cpy_fishes[currentIdx].isAlive = false;
    int sharkDir = cpy_fishes[currentIdx].dir;
    answer = max(answer, sum);
//    cout<<sum<<"<"<<answer<<">"<<endl;
//    for(int i=0; i<4; i++) {
//        for(int j=0; j<4; j++) {
//            cout<<cpy_map[i][j]<<" ";
//        }
//        cout<<endl;
//    }
    
    /*2: 물고기의 이동*/
    for(int i=1; i<=16; i++) {
        Fish fish = cpy_fishes[i];
        if(!fish.isAlive) continue;

        for(int d=0; d<8; d++) { //나아갈 수 있는 방향이 나올 때까지 회전하면서 확인
            int nextDir = (fish.dir + d) % 8;
            int nextY = fish.y + moveDir[nextDir].y;
            int nextX = fish.x + moveDir[nextDir].x;
            if(isAvailable(nextY, nextX) && !(nextY == y && nextX == x)) {
                //이동할 수 있는 칸: 경계 범위 안이며, 상어가 없어야하며
                //다른 물고기가 존재하거나 빈칸인 경우 이동할 수 있다
                if(cpy_map[nextY][nextX] != 0) {//다른 물고기가 있다면?
                    //바꾸자
                    //상대 물고기 위치 갱신
                    int nextIdx = cpy_map[nextY][nextX];
                    Fish nextFish = cpy_fishes[nextIdx];
                    cpy_fishes[nextIdx] = Fish(fish.y, fish.x, true, nextFish.dir);
                    cpy_map[nextY][nextX] = i;
                    
                    //현재 위치에 다른 물고기를 정보를 넣어준다
                    cpy_fishes[i] = Fish(nextY, nextX, false, nextDir);
                    cpy_map[fish.y][fish.x] = nextIdx;
                } else { //빈칸이라면
                    cpy_map[fish.y][fish.x] = 0;
                    cpy_map[nextY][nextX] = i;
                    cpy_fishes[i] = Fish(nextY, nextX, false, nextDir);
                }
                break;
            }
        }
    }
//    cout<<"[물고기 이동 후]"<<endl;
//    for(int i=0; i<4; i++) {
//        for(int j=0; j<4; j++) {
//            cout<<cpy_map[i][j]<<" ";
//        }
//        cout<<endl;
//    }
//
    /*3: 상어 이동*/
    for(int cnt = 1; cnt <= 3; cnt++) {
        int nextY = y + moveDir[sharkDir].y * cnt;
        int nextX = x + moveDir[sharkDir].x * cnt;
        if(isAvailable(nextY, nextX)){
            if(cpy_map[nextY][nextX] != 0) {
//                cout<<y<<","<<x<<"->"<<nextY<<","<<nextX<<":"<<sum<<endl;
//                cout<<"==========================="<<endl;
                DFS(cpy_map, cpy_fishes, nextY, nextX, sum);
            }
        } else break;
    }
}

int main(int argc, const char * argv[]) {
    input();
    DFS(room, fishes, 0, 0, 0);
    cout<<answer<<endl;
    return 0;
}

yoon980208 3년 전 0

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 제가 바보네요! 96, 101번째 줄에도 서로 SWAP하는 물고기들이 살아있음을 나타내는 true로 바꾸어준 뒤 해결했습니다!

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

문제

문제

출처

ICPC

[C++]몇시간동안 이 문제만 붙들고 있네요.. 도와주세요

yoon980208 3년 전 0

yoon980208 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말