[백준/C++] 19236 - 청소년 상어

풀이 시간: 3h57m12s90

시간 복잡도: O(3^16)

공간 복잡도: O(1)

문제

 

입력

첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.

출력

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 출력한다.

문제 풀이

우선 내 초기 문제 풀이는 이러하다. (오류)

상어는 현재 방향의 물고기가 있는 모든 칸을 이동할 수 있다는 점에 있어서, dfs 백트래킹을 사용해야겠다고 생각했다.

// 물고기 구조체 { 위치(x, y), 방향, 생존 여부 }
struct Fish {
    int x, y, dir;
    bool live;
};

// 상어 구조체 { 위치(x, y), 방향 }
struct Shark {
    int x, y, dir;
};

Fish fish[17]; // 물고기 구조체 배열 (총 16마리)
Shark shark; // 상어 구조체

먼저 난, 물고기와 상어의 구조체를 선언하고, 상어 한 마리와 물고기 총 16마리만큼의 크기를 가진 구조체 배열을 선언하였다.

if (i == 0 && j == 0) {
    fish[a] = { i, j, b - 1, false }; // 0, 0 위치 물고기 정보
    ans += a; // 0, 0 위치의 물고기 번호 삽입 (상어가 미리 먹고 시작)
    shark = { i, j, b - 1 }; // 상어 구조체 정보 저장
}
else fish[a] = { i, j, b - 1, true };

그리고 입력값을 받을 때, 처음부터 상어 위치를 (0, 0)에 삽입하고 시작하였다.

즉 상어가 (0, 0) 좌표에 들어가서 물고기를 먹고 시작을 하는 것이다.

따라서 초기 ans 값은 좌표 (0, 0)에 있는 물고기 번호가 된다.

그리고 물고기 번호대로 구조체 배열에 하나씩 대응하는 값을 넣는다.

 

그리고 dfs 함수를 호출해주는데, 이때 ans 값을 인자로 넘겨주도록 한다.

 

dfs 함수에서는 먼저 배열을 임시 저장해주고, 초반에 상어가 (0, 0) 좌표의 물고기를 먹고 시작했으므로, 바로 물고기 이동부터 해준다.

for (int i = 1; i < 17; ++i) {
    if (!fish[i].live) continue; // 죽은 물고기는 스킵
    int d = fish[i].dir, nX, nY, nextFishNum;
    ...

물고기는 1번부터 16번까지 모든 물고기를 순차적으로 탐색하며, 45도 반시계 방향으로 돌면서 교환 가능한 위치와 교환을 해준다.

일단, 죽은 물고기인 경우는 그냥 스킵해준다. 왜냐하면 죽은 물고기는 이동할 수 없기 때문이다.

그리고 물고기의 방향과, 다음 위치, 교환될 물고기 번호에 대한 변수를 선언한다.

 

do { 
    // 다음 위치
    nX = fish[i].x + dir[d][0];
    nY = fish[i].y + dir[d][1];

    // 공간을 벗어나거나, 상어가 있는 위치일 경우 45도 반시계 회전 후 다시 탐색
    if (nX < 0 || nX >= 4 || nY < 0 || nY >= 4 || (shark.x == nX && shark.y == nY)) d = (d + 1) % 8;
    else { 
        // 교환 가능한 위치인 경우 물고기 위치 교환
        /* 죽은 물고기더라도 그 물고기의 구조체 위치는 계속 이동(다른 물고기와의 교환을 위해 필요)
        죽은 물고기는 live = false, arr[i][j]=0으로 변경됨 (상어가 arr를 통해 먹을 것이기 때문에 arr을 0으로 만들어 주어야 함) */
        nextFishNum = arr[nX][nY];
        fish[nextFishNum].x = fish[i].x;
        fish[nextFishNum].y = fish[i].y;
        fish[i].x = nX;
        fish[i].y = nY;
        fish[i].dir = d; // 현재 물고기 방향도 갱신
        break; 
    }
} while (d != fish[i].dir); // 다시 제자리 방향으로 돌아왔을 경우 종료

do-while 문 내부에서는 먼저, 현재 물고기가 가리키는 방향의 다음 위치를 지정하고, 그 다음 위치가 공간을 벗어났는지, 상어가 있는지 판단해준다.

만약 공간을 벗어났거나 상어가 있는 위치일 경우, 현재 물고기의 방향을 45도 회전한 후 다시 탐색해준다.

그렇지 않고 교환이 가능한 위치인 경우에는 물고기 위치를 교환해준다. 이때, 현재 물고기 방향도 d로 갱신해주어야 한다.

여기서 do-while 문은 현재 계속 돌리고 있는 d의 방향이 제자리 즉, 현재 물고기의 기존 방향(fish[i].dir)으로 돌아왔을 경우에 더 이상 탐색할 수 없으므로 종료한다.

 

그 다음에 상어를 이동시켜주는데, 우선 상어의 방향은 한 번 진행될 때 한 방향으로만 진행되므로 그대로 진행될 것이며, 물고기를 먹었을 때 해당 물고기의 방향으로 갱신이 된다. 따라서 백트래킹을 해주기 위해 미리 상어의 기존 방향을 임시저장해준다.

 

그리고 for 문을 돌려주는데 총 4x4 배열이므로 상어는 현재 위치에서 최대 3번을 이동할 수 있다. 따라서 다음과 같이 구현해주었다.

for (int i = 1; i < 4; ++i) {
    // 상어가 탐색할 다음 위치
    int nX = shark.x + dir[tempDir][0] * i;
    int nY = shark.y + dir[tempDir][1] * i;
    ...
}

이 때 다음 위치를 선정할 때는 for문의 i를 사용하여 곱한만큼 해당 방향으로 진행해주면 된다.

이렇게 하면 굳이 이동 과정에서 이전 위치를 저장해둘 필요가 없다.

 

if (nX < 0 || nX >= 4 || nY < 0 || nY >= 4) continue; // 범위 이탈 제외
int nextFishNum = arr[nX][nY]; // 다음 물고기 번호 임시 저장
if (nextFishNum == 0 || !fish[nextFishNum].live) continue; // 죽은 물고기 제외

그리고 상어가 중간에 있을수도 있으므로 nX, nY가 격자 밖으로 나가는지도 한 번 확인해준다.

또한, 죽은 물고기가 있는 위치로는 이동할 수 없기 때문에 건너뛰어 준다.

// 상어 이동 및 해당 위치 물고기 먹음
shark = { nX, nY, fish[nextFishNum].dir };
arr[nX][nY] = 0;
fish[nextFishNum].live = false;

dfs(cnt + nextFishNum); // 다음 탐색 진행

// 백트래킹
fish[nextFishNum].live = true;
arr[nX][nY] = nextFishNum;
shark.x -= dir[shark.dir][0] * i;
shark.y -= dir[shark.dir][1] * i;
shark.dir = tempDir;

그 다음으로 이제 나머지는 상어가 이동할 수 있는 위치이므로, 물고기를 먹기 위해 상어를 이동시켜주면 된다.

먼저 상어 구조체에 위치 값과 방향을 먹고자하는 물고기가 있는 위치의 값들로 재설정해준다.

그리고 arr 배열의 먹고자 하는 물고기가 있는 자리에 0, 그 물고기를 죽음(false)로 표시한다.

 

그리고 다음 dfs를 탐색해주면 된다.

 

가장 중요한 백트래킹 과정인데, 물고기를 다시 살리고 상어를 제자리로 돌려놓으면 되는 것이다.

그래서 arr 배열의 물고기가 있던 자리에 물고기의 번호를 다시 두고, 다시 살려둔다.

그리고 상어는 제자리로 가야하므로, 현재 for 문의 i 값만큼 다시 그 이전 방향으로 돌아가주면 된다.

또한, 상어는 한 번 탐색할 때 한 방향으로 쭉 탐색하므로, dfs 내부에서 처음에 상어의 방향을 임시 저장해둔 값으로 다시 돌려놓으면 된다.

오류 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int ans = 0;
vector<vector<int>> arr(4, vector<int>(4, 0)); // 물고기 번호 위치
int dir[8][2] = {{-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}};

// 물고기 구조체 { 위치(x, y), 방향, 생존 여부 }
struct Fish {
    int x, y, dir;
    bool live;
};

// 상어 구조체 { 위치(x, y), 방향 }
struct Shark {
    int x, y, dir;
};

Fish fish[17]; // 물고기 구조체 배열 (총 16마리)
Shark shark; // 상어 구조체

// 물고기 이동
void fishMove() {
    for (int i = 1; i < 17; ++i) {
        if (!fish[i].live) continue; // 죽은 물고기는 스킵
        int d = fish[i].dir, nX, nY, nextFishNum;
        do { 
            // 다음 위치
            nX = fish[i].x + dir[d][0];
            nY = fish[i].y + dir[d][1];

            // 공간을 벗어나거나, 상어가 있는 위치일 경우 45도 반시계 회전 후 다시 탐색
            if (nX < 0 || nX >= 4 || nY < 0 || nY >= 4 || (shark.x == nX && shark.y == nY)) d = (d + 1) % 8;
            else { 
                // 교환 가능한 위치인 경우 물고기 위치 교환
                /* 죽은 물고기더라도 그 물고기의 구조체 위치는 계속 이동(다른 물고기와의 교환을 위해 필요)
                죽은 물고기는 live = false, arr[i][j]=0으로 변경됨 (상어가 arr를 통해 먹을 것이기 때문에 arr을 0으로 만들어 주어야 함) */
                nextFishNum = arr[nX][nY];
                fish[nextFishNum].x = fish[i].x;
                fish[nextFishNum].y = fish[i].y;
                fish[i].x = nX;
                fish[i].y = nY;
                fish[i].dir = d; // 현재 물고기 방향도 갱신
                break; 
            }
        } while (d != fish[i].dir); // 다시 제자리 방향으로 돌아왔을 경우 종료
    }
}

void dfs(int cnt) {
    vector<vector<int>> tempArr = arr; // 배열 임시 저장
    int tempDir = shark.dir; // 상어 방향 변동 없음

    fishMove(); // 물고기 이동

    for (int i = 1; i < 4; ++i) {
        // 상어가 탐색할 다음 위치
        int nX = shark.x + dir[shark.dir][0] * i;
        int nY = shark.y + dir[shark.dir][1] * i;

        if (nX < 0 || nX >= 4 || nY < 0 || nY >= 4) continue; // 범위 이탈 제외
        int nextFishNum = arr[nX][nY]; // 다음 물고기 번호 임시 저장
        if (nextFishNum == 0 || !fish[nextFishNum].live) continue; // 죽은 물고기 제외

        // 상어 이동 및 해당 위치 물고기 먹음
        shark = { nX, nY, fish[nextFishNum].dir };
        arr[nX][nY] = 0;
        fish[nextFishNum].live = false;

        dfs(cnt + nextFishNum); // 다음 탐색 진행

        // 백트래킹
        fish[nextFishNum].live = true;
        arr[nX][nY] = nextFishNum;
        shark.x -= dir[shark.dir][0] * i;
        shark.y -= dir[shark.dir][1] * i;
        shark.dir = tempDir;
    }

    ans = max(cnt, ans); // 상어가 먹은 물고기 최댓값 갱신
    arr = tempArr;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int a, b;
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            cin >> a >> b;
            arr[i][j] = a;
            if (i == 0 && j == 0) {
                fish[a] = { i, j, b - 1, false }; // 0, 0 위치 물고기 정보
                ans += a; // 0, 0 위치의 물고기 번호 삽입 (상어가 미리 먹고 시작)
                shark = { i, j, b - 1 }; // 상어 구조체 정보 저장
            }
            else fish[a] = { i, j, b - 1, true };
        }
    }
    dfs(ans); // 현재까지 먹은 물고기 수
    cout << ans;
    return 0;
}

 

그러나 이 코드에는 문제가 있었다. 일단 모든 예제의 답이 제대로 나오지 않았다. 그래서 다른 블로그를 참고하여 내 코드에서 틀린 부분을 찾아보았다. 참고 블로그는 다음과 같다.

https://yabmoons.tistory.com/495

크게 2가지의 문제가 있었다.

1. 물고기를 이동할 때, arr 배열을 갱신해주지 않았다.

오류 코드에서 보면 물고기를 교환해주는 부분에서 단순히 fish 구조체 배열에 대한 물고기 교환만 이루어졌다.

정작 arr 배열 자체에 대한 물고기 교환이 없었으므로 오류가 나는 것이 당연하다. 따라서 다음과 같이 코드를 수정해주었다.

nextFishNum = arr[nX][nY];
fish[nextFishNum].x = fish[i].x;
fish[nextFishNum].y = fish[i].y;
arr[fish[i].x][fish[i].y] = nextFishNum; // 추가
fish[i].x = nX;
fish[i].y = nY;
fish[i].dir = d;
arr[nX][nY] = i; // 추가

2. 물고기 구조체 배열 또한 백트래킹해주어야 한다.

물고기 구조체 배열 또한 상어가 어떤 물고기를 먹고, 물고기들이 어떻게 이동하느냐에 따라서 값이 달라진다.

따라서 이 배열도 백트래킹을 해주어야 한다.

void dfs(int cnt) {
    Fish tempFish[17]; // 임시 배열
    copy(begin(fish), end(fish), begin(tempFish)); // 임시 저장
    ...
    copy(begin(tempFish), end(tempFish), begin(fish)); // 백트래킹
}

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int ans = 0;
vector<vector<int>> arr(4, vector<int>(4, 0)); // 물고기 번호 위치
int dir[8][2] = {{-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}};

// 물고기 구조체 { 위치(x, y), 방향, 생존 여부 }
struct Fish {
    int x, y, dir;
    bool live;
};

// 상어 구조체 { 위치(x, y), 방향 }
struct Shark {
    int x, y, dir;
};

Fish fish[17]; // 물고기 구조체 배열 (총 16마리)
Shark shark; // 상어 구조체

// 물고기 이동
void fishMove() {
    for (int i = 1; i < 17; ++i) {
        if (!fish[i].live) continue; // 죽은 물고기는 스킵
        int d = fish[i].dir, nX, nY, nextFishNum;
        do { 
            // 다음 위치
            nX = fish[i].x + dir[d][0];
            nY = fish[i].y + dir[d][1];

            // 공간을 벗어나거나, 상어가 있는 위치일 경우 45도 반시계 회전 후 다시 탐색
            if (nX < 0 || nX >= 4 || nY < 0 || nY >= 4 || (shark.x == nX && shark.y == nY)) d = (d + 1) % 8;
            else { 
                // 교환 가능한 위치인 경우 물고기 위치 교환
                /* 죽은 물고기더라도 그 물고기의 구조체 위치는 계속 이동(다른 물고기와의 교환을 위해 필요)
                죽은 물고기는 live = false, arr[i][j]=0으로 변경됨 (상어가 arr를 통해 먹을 것이기 때문에 arr을 0으로 만들어 주어야 함) */
                nextFishNum = arr[nX][nY];
                fish[nextFishNum].x = fish[i].x;
                fish[nextFishNum].y = fish[i].y;
                arr[fish[i].x][fish[i].y] = nextFishNum; // 추가
                fish[i].x = nX;
                fish[i].y = nY;
                fish[i].dir = d; // 현재 물고기 방향도 갱신
                arr[nX][nY] = i; // 추가
                break; 
            }
        } while (d != fish[i].dir); // 다시 제자리 방향으로 돌아왔을 경우 종료
    }
}

void dfs(int cnt) {
    vector<vector<int>> tempArr = arr; // 배열 임시 저장
    Fish tempFish[17]; // 추가
    copy(begin(fish), end(fish), begin(tempFish)); // 추가
    int tempDir = shark.dir; // 상어 방향 변동 없음

    fishMove(); // 물고기 이동

    for (int i = 1; i < 4; ++i) {
        // 상어가 탐색할 다음 위치
        int nX = shark.x + dir[tempDir][0] * i;
        int nY = shark.y + dir[tempDir][1] * i;

        if (nX < 0 || nX >= 4 || nY < 0 || nY >= 4) continue; // 범위 이탈 제외
        int nextFishNum = arr[nX][nY]; // 다음 물고기 번호 임시 저장
        if (nextFishNum == 0 || !fish[nextFishNum].live) continue; // 죽은 물고기 제외

        // 상어 이동 및 해당 위치 물고기 먹음
        shark = { nX, nY, fish[nextFishNum].dir };
        arr[nX][nY] = 0;
        fish[nextFishNum].live = false;

        dfs(cnt + nextFishNum); // 다음 탐색 진행

        // 백트래킹
        fish[nextFishNum].live = true;
        arr[nX][nY] = nextFishNum;
        shark.x -= dir[tempDir][0] * i;
        shark.y -= dir[tempDir][1] * i;
        shark.dir = tempDir;
    }

    ans = max(cnt, ans); // 상어가 먹은 물고기 최댓값 갱신
    copy(begin(tempFish), end(tempFish), begin(fish)); // 추가
    arr = tempArr;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int a, b;
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            cin >> a >> b;
            arr[i][j] = a;
            if (i == 0 && j == 0) {
                fish[a] = { i, j, b - 1, false }; // 0, 0 위치 물고기 정보
                ans += a; // 0, 0 위치의 물고기 번호 삽입 (상어가 미리 먹고 시작)
                shark = { i, j, b - 1 }; // 상어 구조체 정보 저장
            }
            else fish[a] = { i, j, b - 1, true };
        }
    }
    dfs(ans); // 현재까지 먹은 물고기 수
    cout << ans;
    return 0;
}

 

https://www.acmicpc.net/problem/19236