×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,101,837명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. bfs


이 문제는 조건만 잘 생각하면 쉽게 해결 할 수 있다.


1. 상어는 자신보다 작거나 같은 크기의 상어가 있는 곳을 움직 일 수 있다.

2. 상어는 자신보다 작은 것만 먹을 수 있다.

3. 상어는 아래 정렬조건을 가진다.

- 거리가 가장 가까운 물고기를 먹으러 간다.

- 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.



사실 정렬은 pair를 이용하여 거리,y좌표,x좌표를 담고 sort를 하면 알아서 정렬되도록 조건이 되어있다.


자신이 먹을 수 있는 상어를 모두 shark 벡터에 담고 정렬 한 후 벡터가 비어있다면 INF를 리턴, 그 외에는 벡터 첫번째 값을 리턴한다.


그리고 BFS의 리턴값이 INF라면 엄마 상어를 부르면 되고(종료)


BFS값이 존재한다면 그게 최단 거리에 있는 먹을 수 있는 상어를 의미하므로 먹이고 다음 BFS를 진행하면 된다.




소스 코드 : 


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
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#include <memory.h>
 
#define INF 987654321
using namespace std;
 
typedef pair<intint> pii;
 
int arr[22][22];
int dy[4= { -1,0,0,};
int dx[4= { 0,-1,1,};
bool visit[22][22];
 
int n;
int sy, sx, sSize = 2, eat;
int ans;
 
pair<pii, pii> bfs() {
    memset(visit, 0sizeof(visit));
 
    queue<pair<pii, int> > q;
    q.push({ {sy,sx}, });
 
    vector<pair<int, pii>> shark;
 
    while (!q.empty()) {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int dist = q.front().second;
        q.pop();
 
        if (arr[y][x] != && arr[y][x] < sSize) 
            shark.push_back({ dist,{ y,x } });
 
        if (visit[y][x])
            continue;
 
        visit[y][x] = true;
 
        for (int i = 0; i < 4; i++) {
            int ny = dy[i] + y;
            int nx = dx[i] + x;
 
            if ((<= ny && ny < n) && (<= nx && nx < n) && arr[ny][nx] <= sSize)
                q.push({ {ny,nx}, dist + });
        }
    }
 
    if(shark.empty())
        return{ { INF, INF } , { INF, INF } };
 
    sort(shark.begin(), shark.end());
    
    int dist = shark[0].first;
    int y = shark[0].second.first;
    int x = shark[0].second.second;
    int size = arr[y][x];
    return{ {y,x},{dist,size} };
}
 
int main() {
    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)
                sy = i, sx = j, arr[i][j] = 0;
        }
 
    while (1) {
        pair<pii, pii> tmp = bfs();
        if (tmp.second.first == INF)
            break;
 
        int y = tmp.first.first;
        int x = tmp.first.second;
        int dist = tmp.second.first;
        int size = tmp.second.second;
 
        ans += dist;
 
        sy = y;
        sx = x;
        eat++;
        arr[y][x] = 0;
        if (eat == sSize) 
            sSize++, eat = 0;
    }
 
    printf("%d\n", ans);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus

반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[16234번] 인구 이동  (4) 2018.10.22
[16235번] 나무 재테크  (0) 2018.10.22
[16236번] 아기 상어  (4) 2018.10.21
[14890번] 경사로  (0) 2018.09.27
[1038번] 감소하는 수  (0) 2018.09.25
[16159번] 전광판의 숫자  (0) 2018.09.22
  1. 깐밤 2018.10.23 10:37

    가누님 안녕하세요?
    좋은 코드 잘 봤습니다.
    제가 reference용으로 참고하기 위해
    https://github.com/kkanbam/code/blob/master/BOJ/16236_refcode.cpp
    에, 가누님 코드에 코멘트를 달아 올려놨습니다.
    Copyright 표시는 해 두었지만 혹시 문제가 되거나 불쾌하시다면 이 글에 덧글로 알려주셔요.
    미리 말씀 못 드려서 죄송하고, 좋은 코드 감사드립니다.

    • 가누 2018.10.23 11:03 신고

      감사합니다~
      깃헙 주석을 봤는데요

      == 9일때 0을 대입해주는건
      상어 위치가 이동할수있는 거리임을 명시해주는 것이고

      return {inf, inf} { inf, inf} 는 애초에 loc가 pair이기때문에 inf inf inf inf가 됩니다

  2. 깐밤 2018.10.23 11:26

    ㅠ.ㅠ
    가누님 리뷰해 주셔서 감사합니다 ㅠ.ㅠ 너무 부끄럽네요..
    본격적으로 알고리즘 공부한지 얼마 안되서 그런지 모르겠지만
    알고리즘이 안 느는거 아닐까 하는 생각이 듭니다.
    가누님께서 모집하시는 스터디는 백준 몇 문제나 풀어야 들어갈 수 있는것인가요?
    감사합니다.
    즐거운 점심되세요~

    • 가누 2018.10.23 11:48 신고

      스터디 관련해서는 메일보내주세요~
      kkw564@naver.com

      주석 내용을 보니 bfs를 잘 이해하고있고 제가 짠 코드를 자세히 이해하고있는데 어느 부분에서 실력이 안느는것같다는건가요..??