기술 블로그

16236번 아기 상어 본문

알고리즘 문제/BOJ

16236번 아기 상어

parkit 2018. 10. 26. 01:09
728x90
반응형

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






최근에 다시 푼 코드 : https://hsdevelopment.tistory.com/225






2018년 하반기 삼성 SW 역량 테스트 문제이다.


생각보다 오래 걸렸는데,


이미 v안에 있는 것들은 먹을 수 있는 것이라서 굳이 크기를 비교할 필요가 없었다.



나는 무식하게 for문 안에서 먹이의 크기까지 비교했었다. 



덕분에(?) vector 안에도 pair를 2개 선언했었다.


코드가 2개인데, 하나는 그냥 for문을 활용해 먹이를 찾는 것이고, 


다른 코드는 sort를 활용한 것이다.



나중에 시간 된다면, 

vector<pair<int, pair<int, int> > > v; 가 정렬이 어떻게 되는지 알아봐야겠다.

위치도 바꿔서 알아봐야겠다.






for문 활용

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
typedef struct position
{
    int y;
    int x;
    int eat;
    int size;
    int count;
}position;
 
position bs;
 
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, -1, 0, 1 };
 
int Map[22][22] = { 0, };
 
int N = 0;
 
int fy = 0, fx = 0;
// 찾은 먹이 위치 : (y, x)
 
bool visit[22][22] = { false, };
 
bool stop = false;
 
void findEat()
{
    queue<pair<int, int> > q;
 
    vector<pair< int, pair<int, int> > > v;
 
    q.push({ bs.y, bs.x });
 
    visit[bs.y][bs.x] = true;
 
    fy = N; // 가장 작은 행을 찾기 위함
 
    int ret = 1;
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int r = q.front().first;
            int c = q.front().second;
 
            q.pop();
 
            for (int i = 0; i < 4; i++)
            {
                for (int j = 0; j < 4; j++)
                {
                    int row = r + dy[i];
                    int column = c + dx[i];
 
                    if (visit[row][column] || row >= N || row < 0 || column >= N || column < 0) continue;
 
                    visit[row][column] = true;
 
                    bool Next = true;
 
                    if (Map[row][column] == 0 || bs.size == Map[row][column])
                    {
                        q.push({ row, column });
                        Next = false;
                    }
 
                    if (Next)
                    {
                        if (bs.size > Map[row][column])
                        {
                            v.push_back({ ret,{ row, column } });
                            q.push({ row, column });
                            stop = false;
                        }
                    }
                }
            }
        }
 
        ++ret;
    }
 
    int var = 987654321;
    int pos = 987654321;
    int cnt = 0;
 
    for (int i = 0; i < v.size(); i++) // v안에 있는 것들은 이미 먹을 수 있는 것들임
    {
        if (pos >= v[i].first) // 거리 비교
        {
            if (pos == v[i].first) // 거리가 같다면
            {
                if (fy > v[i].second.first) // 행이 더 작은걸 저장
                {
                    fy = v[i].second.first;
                    fx = v[i].second.second;
                    cnt = v[i].first;
                }
            }
            else if (pos > v[i].first) // 거리가 더 짧은 거리에 먹이가 있다면
            {
                fy = v[i].second.first;
                fx = v[i].second.second;
                cnt = v[i].first;
            }
 
            pos = v[i].first;
        }
    }
 
    Map[fy][fx] = 0;
    bs.count += cnt;
 
    ++bs.eat;
 
    if (bs.eat == bs.size)
    {
        ++bs.size;
        bs.eat = 0;
    }
 
    bs.y = fy;
    bs.x = fx;
}
 
int main(void)
{
    memset(Map, 0, sizeof(Map));
 
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            scanf("%d", &Map[i][j]);
 
            if (Map[i][j] == 9)
            {
                bs.y = i;
                bs.x = j;
                bs.eat = 0;
                bs.size = 2;
                bs.count = 0;
                Map[i][j] = 0;
            }
        }
    }
 
    while (1)
    {
        stop = true;
        memset(visit, false, sizeof(visit));
 
        findEat();
 
        if (stop || fy == N) break;
    }
 
    printf("%d\n", bs.count);
 
    return 0;
}
cs








sort 활용

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
typedef struct position
{
    int y;
    int x;
    int eat;
    int size;
    int count;
}position;
 
position bs;
 
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, -1, 0, 1 };
 
int Map[22][22] = { 0, };
 
int N = 0;
 
int fy = 0, fx = 0;
// 찾은 먹이 위치 : (y, x)
 
bool visit[22][22] = { false, };
 
bool stop = false;
 
void findEat()
{
    queue<pair<int, int> > q;
 
    vector<pair< int, pair<int, int> > > v;
 
    q.push({ bs.y, bs.x });
 
    visit[bs.y][bs.x] = true;
 
    fy = N; // 가장 작은 행을 찾기 위함
 
    int ret = 1;
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int r = q.front().first;
            int c = q.front().second;
 
            q.pop();
 
            for (int i = 0; i < 4; i++)
            {
                for (int j = 0; j < 4; j++)
                {
                    int row = r + dy[i];
                    int column = c + dx[i];
 
                    if (visit[row][column] || row >= N || row < 0 || column >= N || column < 0) continue;
 
                    visit[row][column] = true;
 
                    bool Next = true;
 
                    if (Map[row][column] == 0 || bs.size == Map[row][column])
                    {
                        q.push({ row, column });
                        Next = false;
                    }
 
                    if (Next)
                    {
                        if (bs.size > Map[row][column])
                        {
                            v.push_back({ ret, { row, column } });
                            q.push({ row, column });
                            stop = false;
                        }
                    }    
                }
            }
        }
 
        ++ret;
    }
 
    int var = 987654321;
    int pos = 987654321;
    int cnt = 0;
 
    if (v.size() >= 1)
    {
        sort(v.begin(), v.end());
 
        fy = v[0].second.first;
        fx = v[0].second.second;
 
        Map[fy][fx] = 0;
        bs.count += v[0].first;
 
        ++bs.eat;
 
        if (bs.eat == bs.size)
        {
            ++bs.size;
            bs.eat = 0;
        }
 
        bs.y = fy;
        bs.x = fx;
    }
}
 
int main(void)
{
    memset(Map, 0, sizeof(Map));
 
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            scanf("%d", &Map[i][j]);
 
            if (Map[i][j] == 9)
            {
                bs.y = i;
                bs.x = j;
                bs.eat = 0;
                bs.size = 2;
                bs.count = 0;
                Map[i][j] = 0;
            }
        }
    }
 
    while (1)
    {
        stop = true;
        memset(visit, false, sizeof(visit));
 
        findEat();
 
        if (stop || fy == N) break;
    }
    
    printf("%d\n", bs.count);
 
    return 0;
}
cs









728x90
반응형
저작자표시

'알고리즘 문제 > BOJ' 카테고리의 다른 글

1806번 부분합  (0) 2018.10.27
16234번 인구 이동  (2) 2018.10.26
2869번 달팽이는 올라가고 싶다  (0) 2018.10.21
2609번 최대공약수와 최소공배수  (0) 2018.10.14
13225번 Divisors  (0) 2018.10.14
'알고리즘 문제/BOJ' Related Articles more