백준, BOJ, 16236번 C++ [CPP]

아.. 자그마한 문제가 큰 에러를 만든다.

 

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

 

---

 

#맞는 풀이

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>


#define X first
#define Y second

using namespace std;
// 위, 왼, 아, 오 순
int dx[4] = { 0,-1,0,1 };
int dy[4] = { 1,0,-1,0 };

struct Fish {
    int x;
    int y;
    int value;
};


int N;

int map[21][21]; // 맵
int visited[21][21]; // 방문(초기값 -1)



int x, y; // 아기상어 초기 위치
int mag = 2; // 아기상어 초기 크기
int bite = 0;  //아기상어 잡아먹은 횟수
int cnt = 0; //시간.

vector<Fish> vec;


//Fish 우선순위, 최소거리, 위에있는거, 왼쪽에 있는거
bool comp(const Fish& a, const Fish& b) {
    if (a.value == b.value) {
        if (a.x == b.x) {
            return a.y < b.y;
        }
        return a.x < b.x;
    }
    return a.value < b.value;
}


//해당 좌표에서 크기를 입력받고 -> 먹을 수 있는 물고기 찾아감.
int BFS(int a, int b) {
    vec.clear();
    //visited초기화 -1
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            visited[i][j] = -1;
        }
    }

    queue<pair<int, int>> Q;
    visited[a][b] = 0; // 첫노드
    Q.push({ a,b });

    while (!Q.empty()) {
        auto cur = Q.front();
        Q.pop();

        for (int dir = 0; dir < 4; dir++) {
            int nx = dx[dir] + cur.X;
            int ny = dy[dir] + cur.Y;

            //범위에 벗어나거나
            if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            //방문했거나 갈 수 없는 길일 경우(크기)
            if (visited[nx][ny] > -1 || map[nx][ny] > mag)continue;

            //먹을 수 있는 물고기를 찾으면 거리가 최솟값이고 그 중에서 가장 위에 것 그다음으로 가장 왼쪽 것부터 가야함.

            //만약 해당 노드가 먹을 수 있는 물고기라면
            if (map[nx][ny] > 0 && map[nx][ny] < mag) {
                //해당 위치와 해당 위치의 값 반환
                Fish f;
                f.x = nx;
                f.y = ny;
                f.value = visited[cur.X][cur.Y] + 1;
                //해당 값 vec에 넣음
                vec.push_back(f);
            }

            //먹을 수 있는 물고기든 아니든 계속 진행.
            Q.push({ nx,ny });
            visited[nx][ny] = visited[cur.X][cur.Y] + 1; // 큐에 넣을 때 방문처리

        }
    }

    //모든 BFS를 돌며 먹을 수 있는 물고기 조사함
    //그 중 최솟값부터, 위에, 왼쪽에 있는 것으로 감.
    if (!vec.empty()) {
        sort(vec.begin(), vec.end(), comp); // 위의 조건대로 정렬
        auto N = vec[0]; //가장 첫번째 원소로감

        //상어 위치 및 시간 조정
        x = N.x;
        y = N.y;
        cnt += N.value;

        //해당 위치 물고기 없앰
        map[x][y] = 0;
        //물고기 먹음
        bite++;
        if (bite == mag) {
            bite = 0;
            mag++;
        }
        return 1;
    }
    else { // 비어있다면 갈 수 있는 곳이 없는 것임
        return 0;
    }
}



int main() {

    cin >> N;

    //입력받음 (인덱스 0부터 사용함)
    //상어 위치 받음
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
            int temp = map[i][j];
            if (temp == 9) {
                x = i;
                y = j;
            }
        }
    }
    
    map[x][y] = 0; // 상어가 있던 노드는 0으로 바꿈. -> 이거 안해서 시간 2시간날림

    //1. 자신이 먹을 수 있는 물고기가 있는지
    //1-1 있으면 먹으러 감 그 후 1번으로 다시감
    //1-2 없으면 종료

    while (1) {
        int a = BFS(x, y);
        if (a == 0)break;

    }
    cout << cnt;
}

 

 

설명을 최대한 자세히 써놓았다.

내가 애먹은 부분은

comp에서 여러개를 비교할 때는 ==처리를 잘 해줘야 한다는거..

그리고 초기 상어 위치를 map에서 0으로 안바꿔서 2시간 날림...

 

그래서 다른 분이 구조체할 때 오버로딩 하라고..

링크를 알려줬다.

 

연산자 오버로딩을 통한 사용자 정의 객체 정렬을 하란다.

클래스나 구조체에도 적용할 수 있다고 한다.

https://hellowoori.tistory.com/51