본문 바로가기
[PS] 문제풀이/백준

[ 백준 16236 ] 아기 상어 (C++)

by 안산학생 2020. 3. 11.

[문제보기]

 

[해결과정]

 1. input ( n , arr에 맵 입력받기 )

  -> 주의할점! 9는 상어의 초기 위치이다. 상어 위치를 다른 변수에 담고 맵에 9가 아닌 0으로 넣는다.

 

 2. solution 수행

  (1) 현재 상어 위치를 큐에 담는다

  (2) BFS 수행

     -> BFS를 돌며 현재 상어크기보다 같거나 작으면 진입

       -> 만약 현재 상어크기보다 작으면 잡을 수 있는 물고기 ableFish++;

       -> 그리고 map값에 *=-1 하며 음수로 만들기 (음수인 곳은 잡을 수 있는 물고기란 뜻)

       -> minFish에 가장 작은 이동거리 저장시키기

 

  (3) BFS가 끝나면, 맵 처음부터 끝까지 순회

    -> 순회하며 음수인 곳을 가장 처음 만나는 곳이 잡아야 하는 물고기.

    -> 물고기를 잡고, 상어가 잡은 물고기 shsum++;

       -> 만약 shsum 변수가 sh(상어현재크기) 와 같다면 shsum=0, sh++; 하기

 

  (4) 방문 체크배열 초기화, 잡을 수 있는 물고기 변수 ableFish = 0;

 

 

[소스코드]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
/*
    BOJ 16236 - 아기 상어
    Created by haejun on 2020/03/11
*/
#include<iostream>
#include<vector>
#include<queue>
#include<memory.h>
#include<math.h>
#include<algorithm>
#include<string>
using namespace std;
const int MAX = 22;
 
int arr[MAX][MAX];
int check[MAX][MAX];
int n;
 
//아기상어 위치
int sy, sx, sh = 2;
//아기상어가 먹은 물고기
int shsum = 0;
 
//좌표 구조체, 큐 생성
struct coor {
    int y;
    int x;
    int cnt;
};
queue <coor> q;
//inside
bool inside(int y, int x) {
    return y >= 0 && y < n && x >= 0 && x < n;
}
int dy[4= { -1,1,0,0 };
int dx[4= { 0,0,-1,1 };
 
//이동거리 도합
int maxsum = 0;
 
//잡을 수 있는 물고기 수
//BFS() 돌리고 나서도 0 이라면 끝
int ableFish = 0;
//가장 가까운 물고기
int minFish = 987987987;
 
void bfs() {
    minFish = 987987987;
    while (!q.empty()) {
        int y = q.front().y;
        int x = q.front().x;
        int cnt = q.front().cnt;
        q.pop();
        check[y][x] = cnt;
 
        int ny, nx;
        for (int i = 0; i < 4; i++) {
            ny = y + dy[i];
            nx = x + dx[i];
            if (inside(ny, nx) && check[ny][nx] == 0 && arr[ny][nx] <= sh) {
                if (arr[ny][nx] < sh && arr[ny][nx] != 0) {
                    if (arr[ny][nx] > 0) arr[ny][nx] *= -1;
                    ableFish += 1;
                    if (cnt + 1 < minFish) minFish = cnt + 1;
                }
                check[ny][nx] = cnt + 1;
                q.push({ ny, nx, cnt + 1 });
            }
        }
    }
}
 
void solution() {
    //for문 멈추는 flag;
    int fflag = 0;
    while (true) {
        // 1. 상어 현재 위치 기준으로 BFS 돌리기
        //    먹을 수 있는 고기 파악
        check[sy][sx] = 1;
        q.push({ sy,sx,1 });
        bfs();
        //먹을 수 있는 물고기가 없다면 끝.
        if (ableFish == 0break;
 
        //가장 가까운 거리의 먹을 수 있는 물고기는 check배열에 minFish 값
        // 2. 먹을 수 있는 물고기
        //    같은 값이라면, 가장 '위' 이면서 가장 '왼쪽' 인 물고기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (check[i][j] == minFish && arr[i][j] < 0) {
                    //먹은 물고기 
                    shsum += 1;
                    //상어 위치 갱신
                    sy = i; sx = j;
                    //맵에서 물고기 없애기...
                    arr[i][j] = 0;
                    //이동거리 더하기
                    maxsum += minFish - 1;
                    fflag = 1;
                    //만약 먹은 물고기 수와 상어크기가 같다면 상어크기+1
                    if (shsum == sh) {
                        shsum = 0;
                        sh += 1;
                    }
                    break;
                }
            }
            if (fflag == 1break;
        }
        fflag = 0;
        //잡을 수 있는 물고기 0으로 초기화
        ableFish = 0;
        //방문 배열 초기화
        memset(check, 0sizeof(check));
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 9) {
                sy = i;
                sx = j;
                arr[i][j] = 0;
            }
        }
    }
 
    solution();
 
    cout << maxsum << endl;
 
    return 0;
}
 

 

 

[해결 과정 중 실수한 부분 / 잡담]

 5개월 전에 풀었던 문제이다. 그때의 난 누구였는가? 오늘 새로 풀었을 때, 20분 만에 풀이가 완성되었지만.. 아주아주 미세한 실수로 인하여 엄청난 시간을 소요했다. 그 실수는 bfs에 대한 실수였다. 나는 상좌우하 순으로 bfs를 방문하면 자연스레 '가장 위, 가장 왼쪽'을 만족 할 것이라 생각했다. 하지만 가까운 거리라면 그럴 수 있지만, 먼 거리라면... 어느샌가부터 '가장 위, 가장 왼쪽'을 만족하지 못한다. 예를 들자면 큐에 넣은 순서대로 진행이 되니, 어느정도 진행이 됐을 때 왼쪽방향에 있던 큐의 아래 방향을 먼저 탐색하기 시작하여, 우측에 같은 새로줄을 먼저 탐색해야 하는 규칙에 어긋나게 된다.

 

 이것은 어떻게 보면 미세한 실수지만, 굉장히 큰 실수다. BFS에 대한 이해도가 높았다고 자만했던 나인데,, 반성한다.

 

[관련 문제 혹은 비슷한 문제]

 삼성 역량테스트



댓글