C언어로 백준 16236번: 아기 상어 (삼성 A형 기출 문제)

by 코딩하는 낙타 2020. 3. 17. 14:21

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

16236번: 아기 상어

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크

www.acmicpc.net

내 풀이:

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

#include <stdio.h>
int N, arr[20][20];
int dy[4] = { -1, 0, 1, 0 }, dx[4] = { 0, 1, 0, -1 };
int eat_y = 21, eat_x = 21;
int y, x;
 
 
int main(void) {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] == 9) {
                y = i;
                x = j;
                arr[i][j] = 0;
            }
        }
    }
 
    int size = 2, ans = 0, q[400][2], visited[20][20] = { 0 };
    int eat = 0;
 
    q[0][0] = y;
    q[0][1] = x;
    int front = 0, rare = 1, cnt = 0;
 
    while (front < rare) {
        int last_rare = rare;
        for (; front < last_rare; front++) {
            y = q[front][0];
            x = q[front][1];
            for (int dir = 0; dir < 4; dir++) {
                int ny, nx;
                ny = y + dy[dir];
                nx = x + dx[dir];
                if (0 <= ny && ny <= N - 1 && 0 <= nx && nx <= N - 1 && visited[ny][nx] == 0 && arr[ny][nx] <= size) {
                    visited[ny][nx] = 1;
                    if (0 < arr[ny][nx] && arr[ny][nx] < size) {
                        if (eat_y > ny) {
                            eat_y = ny;
                            eat_x = nx;
                        }
                        else if (eat_y == ny) {
                            if (eat_x > nx) {
                                eat_x = nx;
                            }
                        }
                    }
                    else {
                        q[rare][0] = ny;
                        q[rare][1] = nx;
                        rare += 1;
                    }
                }
            }
        }
        cnt += 1;
 
        if (eat_y < 21) {
            eat += 1;
            if (eat == size) {
                size += 1;
                eat = 0;
            }
 
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    visited[i][j] = 0;
                }
            }
            front = 0;
            rare = 1;
            q[0][0] = eat_y;
            q[0][1] = eat_x;
            arr[eat_y][eat_x] = 0;
            ans += cnt;
            cnt = 0;
            eat_y = 21;
            eat_x = 21;
        }
    }
 
    printf("%d", ans);
 
    return 0;
}

 

시간: 0ms

BFS를 구현하기 위해 C언어로 queue를 구현하였다. front와 rare를 이용하여 큐에 새로 들어오는 값, 큐가 끝나는 순간 등을 표현하였다.

저작자표시

'C언어 > 문제풀이 (삼성 A형 대비)' 카테고리의 다른 글

C언어로 풀어보는 백준 17281번: ⚾ (0)	2020.03.21
C언어로 백준 15683: 감시 (0)	2020.03.17
C언어로 풀어보는 백준 17144번: 미세먼지 안녕! (0)	2020.03.10