C - [요구사항 미달 백준 2178] 아기상어 (feat. BFS)

Checkpoint

 

소요시간 약 100분

친구 추천으로 풀게 된 문제

알고리즘분류에 시뮬레이션이 있었지만 아직 뭔지 몰라서 BFS로만 구현 중

 

* 요구사항 2개 미달로 결과가 달라짐 ( 미달성 요구사항 밑에 마킹해놓음)

-> 예상 지점: dir 배열의 상하좌우에 따른 탐색 순서 변화

-> 물고기가 1개일 경우와 N개일 경우 따로 처리하는 코드가 없음, 결과 부분에서 변화를 줘야할지 설계를 잘못한건지 판단하지 않음

* 시간 초과 이슈 예상

-> 물고기를 먹고 다시 BFS를 순화하는 과정에서 불필요한 움직임이 발생

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

 

진행중인 코드

#include <stdio.h>
#include <stdlib.h>
int N = 0;
int arry[20][20];
int visited[20][20];
int queue[400][2];
int time = 0;
int front = 0;
int rear = 0;
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
int distance = 0;
int temp_x = 0;
int temp_y = 0;

void enqueue(int x, int y){
    queue[rear][0] = x;
    queue[rear][1] = y;
    rear ++;
};

void dequeue(int *x, int *y){
    *x = queue[front][0];
    *y = queue[front][1];
    front ++;
    return;
};

void bfs(int x, int y, int size, int count, int time){

    enqueue(x, y);
    printf("time: %d size: %d, count: %d x: %d y: %d\n", time, size, count, x, y);

    while(front < rear){
        int x, y;
        dequeue(&x, &y);
        for(int i = 0 ; i < 4; i++){
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            // size 이하일 경우만 움직일 수 있음
            if(0<= nx && nx < N && 0 <= ny && ny < N && arry[ny][nx] <= size && !visited[ny][nx]){
                // size보다 작으면 먹을 수 있음
                if( 0< arry[ny][nx] && arry[ny][nx] < size){

                    // 어떻게 처리해야할지 몰라서 변수 할당후 계산
                    // 그전에 먹은 위치와 현재 위치 거리 비교
                    distance += abs(nx - temp_x) + abs(ny - temp_y);
                    temp_x = nx;
                    temp_y = ny;
                    
                    // 먹으면 0으로 바뀜
                    arry[ny][nx] = 0;

                    // 먹은 횟수 증가
                    count ++;
                    
                    //먹었을 경우만 visited 표시 > 재방문 필요가 없기 때문에
                    visited[ny][nx] = 1; 
                    
                    // 먹은 횟수와 사이즈가 동일하면 물고기 성장 & count 초기화
                    if(count == size){
                        size ++;
                        count = 0;
                    }
                    //먹었으면 bfs 초기화 후 다음 물고기를 찾으러 감
                    front = 0;
                    rear = 0;
                    time ++;
                    return bfs(nx, ny, size, count, time);
                } else{
                    enqueue(nx, ny);
                }
            }
        }
    }
};

int main() {
    int x, y = 0;
    int size = 2;
    int count = 0;
    scanf("%d", &N);
    for(int i = 0; i < N; i ++){
        for(int j = 0 ; j < N; j ++){
            scanf("%d", &arry[i][j]);
            if(arry[i][j] == 9){
                x = j;
                y = i;
            }
        }
    }

    bfs(x, y, size, count, time);
    if(distance == 0){
        printf("0");
    } else{
        printf("%d", time + distance);
    }
    return 0;
}