[백준 BOJ] 19236번 - 청소년 상어 (C++)

📌 참고

교공 알고리즘 스터디에서 다룬 문제는 19주차부터 벨로그에 기록하고 있습니다 (18주차 이전 문제들을 추후 복습 겸 업로드할 계획도 있습니다 🤗) 그 외 개인적으로 풀어본 백준 및 프로그래머스 문제는 스스로 유의미하다고 여겨진 부분들이 있는 문제만 선별하여 벨로그에 기록하고 있습니다 벨로그에 올라오지 않은 다른 문제와 코드가 궁금하신 분들은 아래의 github에서 추가로 확인하실 수 있습니다 👀 방문해주셔서 감사합니다 🙏

💚 github | dianstar/Algorithm-BOJ
💚 github | dianestar/Algorithm-Programmers

교공 알고리즘 스터디 19주차 삼성기출

19236번: 청소년 상어 | 문제 바로가기

문제풀이 (2022-01-09 SUN 💻)

🤔 사담

ㅎㅎㅎㅎ 몇 시간 걸려서 푼 건지 모르겠다..
구현 문제는 웬만해서 막히고 디버깅 어지간히 안 되면
던지고 새로운 방법으로 푸는 게 낫다 는 큰 교훈을 얻은 날^^

⭐ 풀이의 핵심

👉 DFS를 활용하고 백트래킹을 위해 배열을 복사해두는 게 핵심이었던 문제였다
✅ 2차원 배열 대신에 2차원 벡터 사용했으면 코드가 더 짧아지지 않았을까 싶다
(벡터는 함수 인자로 넘어갈 때 &를 안 붙여주면 기본적으로 call by value라서 백트래킹을 위해 배열 복사 하는 부분이 생략될 수 있음)

👉 백트래킹 필요하고 살필 정보가 많은 경우에는 웬만하면 구조체 선언하고 시작해야겠다
처음에는 물고기 번호 담는 행렬, 방향 담는 행렬, 물고기 행렬 인덱스 값 담는 벡터,
물고기 생사 여부 담는 벡터... 하나하나 따로 만들었다가 대멘붕 파티.. 🤦‍♀️

👉 fishes라는 1차원 배열을 따로 선언해서
입력받을 때부터 물고기 번호==Fish 구조체 배열 인덱스가 되도록 배열에 Fish 구조체를 넣어줬다
어차피 탐색할 때 1번부터 16번까지 순서대로 돌기 때문에
입력 받을 때 이렇게 조치를 안 해주면 탐색 시작하기 전에 또 번거로운 작업을 거쳐줘야 한다..

🚨 간과 또는 실수한 부분

죽은 물고기(빈칸) 위치와 상어가 있는 위치를 구분할 필요가 있었는데
처음에 이 둘을 구분하지 않고 똑같이 행렬 값을 -1로 처리해줬더니 문제가 발생했었다

🔽 코드 (C++)

#include <iostream>
using namespace std;

struct Fish {
    int dir, row, col, isDead;
};

int answer = 0;

//0:UP 1:LEFT_UP 2:LEFT 3:LEFT_DOWN 4:DOWN RIGHT_DOWN:5 RIGHT:6 RIGHT_UP:7
int moveRow[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int moveCol[8] = { 0, -1, -1, -1, 0, 1, 1, 1 };

/*
void printFishes(int matrix[][4]) {
    for (int i=0; i<4; i++) {
        for (int j=0; j<4; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}
*/

void moveFishes(int matrix[][4], Fish fishes[], int sharkRow, int sharkCol) {
    // cf) 물고기는 번호가 작은 물고기부터 순서대로 이동한다. 
    for (int i=1; i<=16; i++) { // 1번~16번 물고기 순서대로 이동
        // 상어에게 먹힌 물고기의 경우 스킵
        if (fishes[i].isDead == 1) { continue; }
        
        // 이동할 칸의 행열 값 구하여 이동 가능 여부 체크
        int nextRow = fishes[i].row + moveRow[fishes[i].dir];
        int nextCol = fishes[i].col + moveCol[fishes[i].dir];
        // cf) 물고기가 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다.
        // cf) 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 
        while (nextRow < 0 || nextRow >= 4 || nextCol < 0 || nextCol >= 4 ||
        nextRow == sharkRow && nextCol == sharkCol) {
            fishes[i].dir = (fishes[i].dir + 1) % 8;
            nextRow = fishes[i].row + moveRow[fishes[i].dir];
            nextCol = fishes[i].col + moveCol[fishes[i].dir];
        }

        // cf) 물고기가 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸이다.
        if (matrix[nextRow][nextCol] == -1) { // 빈 칸일 경우
            matrix[nextRow][nextCol] = i;
            matrix[fishes[i].row][fishes[i].col] = -1;

            fishes[i].row = nextRow;
            fishes[i].col = nextCol;
        }
        else { // 다른 물고기가 있는 칸일 경우
            int exchangeFish = matrix[nextRow][nextCol];
            matrix[nextRow][nextCol] = i;
            matrix[fishes[i].row][fishes[i].col] = exchangeFish;

            fishes[exchangeFish].row = fishes[i].row;
            fishes[exchangeFish].col = fishes[i].col;
            fishes[i].row = nextRow;
            fishes[i].col = nextCol;
        }
    }
}

void sharkSearch(int matrix[][4], Fish fishes[], int row, int col, int sum) {
    // 백트래킹을 위해 배열 복사
    int tempMatrix[4][4];
    Fish tempFishes[17];
    for (int i=0; i<4; i++) {
        for (int j=0; j<4; j++) {
            tempMatrix[i][j] = matrix[i][j];
        }
    }
    for (int i=1; i<=16; i++) {
        tempFishes[i] = fishes[i];
    }

    // 상어가 물고기를 먹음
    int targetFish = tempMatrix[row][col];
    int sharkDir = tempFishes[targetFish].dir;
    tempFishes[targetFish].isDead = 1;
    tempMatrix[row][col] = -1;
    sum += targetFish;

    // 합이 최댓값일 경우 갱신
    if (sum > answer) { answer = sum; }

    // 물고기 이동
    moveFishes(tempMatrix, tempFishes, row, col);

    // 상어 이동
    // cf) 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 
    int nextRow, nextCol;
    for (int i=1; i<=3; i++) { // 4*4 행렬 구조이므로 최대 3칸까지 이동 가능
        nextRow = row + moveRow[sharkDir] * i;
        nextCol = col + moveCol[sharkDir] * i;

        // 공간의 경계를 넘는 칸으로는 이동할 수 없음
        if (nextRow < 0 || nextRow >= 4 || nextCol < 0 || nextCol >= 4) { break; }

        // cf) 물고기가 없는 칸으로는 이동할 수 없다.
        // 지나갈 수는 있음 주의!
        if (tempMatrix[nextRow][nextCol] == -1) { continue; }

        // 재귀적으로 호출
        sharkSearch(tempMatrix, tempFishes, nextRow, nextCol, sum);
    }
}

int main() {
    int matrix[4][4];
    Fish fishes[17];

    int a, b;
    for (int i=0; i<4; i++) {
        for (int j=0; j<4; j++) {
            scanf("%d %d", &a, &b);
            matrix[i][j] = a;
            fishes[a].dir = b-1;
            fishes[a].row = i;
            fishes[a].col = j;
            fishes[a].isDead = 0;
        }
    }

    sharkSearch(matrix, fishes, 0, 0, 0);
    printf("%d", answer);

    return 0;    
}