Gidhub BE Developer

[SW Expert Academy] 2117. 홈 방범 서비스

2018-09-03
goodGid
Algorithm

Problem

Problem URL : 홈 방범 서비스

[1] Answer Code (18. 10. 14)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define p pair<int,int>
using namespace std;

int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

int map[20][20];
int v[20][20];
int ans;
int n,m;

struct Node{
    int x;
    int y;
    int cnt;
    int k;
    Node(int a, int b, int c, int d): x(a), y(b), cnt(c), k(d) {};
};

int cal(int value){
    return (value * value) + ( (value-1) * (value-1) );
}

bool inRange(int x, int y){
    if(x < 0 || x >= n || y < 0 || y >= n)
        return false;
    return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int TC;
    cin >> TC;
    for(int tc=1; tc<=TC; tc++){
        memset(map,0,sizeof(map));
        ans = -1;
        cin >> n >> m;
        vector<Node> home;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++) {
            cin >> map[i][j];
            if(map[i][j])
                home.push_back(Node(i,j,1,1));
            else
                home.push_back(Node(i,j,0,1));
            }
        }
        int size = (int) home.size();
        
        for(int h=0; h<size; h++){
            memset(v,0,sizeof(v));
            int st_x = home[h].x;
            int st_y = home[h].y;
            int cnt = home[h].cnt;
            int _k = home[h].k;
            
            queue<Node> q;
            q.push(Node(st_x,st_y,cnt,_k));
            v[st_x][st_y] = 1;
            
            int cost;
            int total_cnt = cnt;
            
            while (! q.empty()) {
                int x = q.front().x;
                int y = q.front().y;
                int _cnt = q.front().cnt;
                int _k = q.front().k;
                q.pop();
                
                cost = m * _cnt - cal(_k);
                if(cost >= 0)
                    ans = ans < _cnt ? _cnt : ans;
                
                for(int i=0; i<4; i++){
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    
                    if(! inRange(nx, ny)) continue;
                    if(v[nx][ny]) continue;
                    
                    v[nx][ny] = 1;
                    if(map[nx][ny] == 1)
                        total_cnt ++;
                    
                    q.push(Node(nx,ny,total_cnt,_k+1));
                }
            } // end of while
        } // end of for h
        
        cout << "#" << tc << " " << ans << endl ;
    }
    return 0;
}

Review

  • 모든 정점에서 BFS를 돌리면 AC를 받을 수 있다.

  • 처음에 집에서만 모든 정점에 대해 BFS를 돌리는 실수를 했다.

  • 다음과 같이 Input이 주어질 경우 틀리게 되었다.

00100
00000
10001
00000
00100
  • (2,2)에서 시작하는 경우를 살피지 못하기 때문이다.

[2] Answer Code (18. 09. 03)

#include<iostream>
#include<cstring>
#include<queue>
#define p pair<int,int>
using namespace std;

int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
int map[20][20];
int visit[20][20];
int n,m;
int ans;
queue<p> q;

void bfs(int x, int y){
    int k = 1;
    visit[x][y] = 1;
    q.push({x,y});
    
    int cnt = map[x][y];
    while (k <= n+n) {
        int cost = cnt * m - ( k*k + (k-1)*(k-1) );
        if(cost >= 0)
            ans = ans > cnt ? ans : cnt;
        
        int size = (int) q.size();
        for(int i=0; i<size; i++){
            int _x = q.front().first;
            int _y = q.front().second;
            q.pop();
            for(int j=0; j<4; j++){
                int nx = _x + dx[j];
                int ny = _y + dy[j];
                
                if(nx == -1 || nx == n || ny == -1 || ny == n || visit[nx][ny]) continue;
                visit[nx][ny] = 1;
                q.push({nx,ny});
                if(map[nx][ny])
                    cnt++;
            }
        }
        k++;
    }
    while (! q.empty()) { q.pop();}
}

int main(){
    int TC;
    cin >> TC;
    for (int tc=1; tc<=TC; tc++) {
        ans = -1;
        memset(map,0,sizeof(map));
        cin >> n >> m;
        
        for(int i=0; i<n; i++) for(int j=0; j<n; j++) scanf("%d",&map[i][j]);
        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                memset(visit,0,sizeof(visit));
                bfs(i,j);
            }
        }
        printf("#%d %d\n",tc, ans);
    } // end of for tc
    return 0;
}

Review

if(nx == 0 || nx == n-1 || ny == 0 || ny == n-1 ) continue;

  • 자꾸 nx == 0, nx == n-1로 코딩해서 시간을 많이 할애했다. 범위값에 조심해야겠다.

  • Sample Input 10번째가 400이 나와야하는데 399가 나왔다.
    그래서 그냥 제출했는데 TC 50개 중 1개가 틀린다.

  • while (k <= n) 범위 조건이 잘못됐다. k <= n+n 으로 하니까 맞는다. // 그냥 n+n을 한거다 다른 이유는 없었다.
    그런데 왜 k <=n 조건이면 안되는 이유를 모르겠어서 질문을 했다.

n==2이고, k==1일때는
0 0
1 0
 
k==2
1 0
1 1
이렇게 되면 k가 n과 같지만 (0,1)은 방문하지 못하게 됩니다.
즉 k가 3일때, 최종적으로 모든 곳을 방문할 수 있게 됩니다.
n이 4일때도 직접 그려보시면 n이 5가될 때 모든 배열을 방문할 수 있게 됩니다.
따라서 while(k<=n+1)로 해주시면 됩니다.

[3] Answer Code (18. 06. 01)


#include <cstdio>
#include <cstring>
using namespace std;
int T, N, M, K, Ans, Cnt, map[20][20];
void Input() {
    Ans = 0;
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
        scanf("%d", &map[i][j]);
}
int OddK() { return N % 2 == 0 ? N + 1 : N; }
int Abs(int a) { return a > 0 ? a : -a; }

void Check(int x,int y) {
    Cnt = 0;
    for (int i = x - K + 1; i <= x + K - 1; i++)
        for (int j = y - K + 1; j <= y + K - 1; j++)
            if (i >= 0 && j >= 0 && i < N && j < N &&
                i >= x - K + 1 + Abs(j - y) &&
                i <= x + K - 1 - Abs(j - y) &&
                (map[i][j] == 1))
                Cnt++;
    
    if (Cnt*M >= K * K + (K - 1)*(K - 1) && Ans < Cnt) Ans = Cnt;
}

void ReadMap() {
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
        Check(i, j);
}
int main() {
    scanf("%d", &T);
    for (int tc = 1; tc <= T; tc++) {
        Input();
        for (K = OddK(); K > 0; K--)
            ReadMap();
        printf("#%d %d\n", tc, Ans);
    }
}

Review

  • [이준용] 마름모로 답을 Check하는 방식

  • Check() 함수를 잘 보고 기억해두자 !

[4] Answer Code (18. 06. 01)


#include<iostream>
#include<cstring>
#include<queue>
#define p pair<int,int>
using namespace std;

int map[20][20];
int visit[20][20];
int n,m;
int max_home;
int dx[] = { 0,1,0,-1};
int dy[] = { 1,0,-1,0};

void bfs(int x, int y){
    visit[x][y] = 1;
    
    queue<p> q;
    q.push({x,y});
    
    int cnt = map[x][y];
    
    for(int k=1;;k++){
        if( q.empty() )
            break;
        
        int size = (int)q.size();
        
        int cost = cnt * m - ( k*k + (k-1)*(k-1) );
        if( cost >= 0 && max_home < cnt)
            max_home = cnt;
        
        for(int t=0; t<size; t++){
            x = q.front().first;
            y = q.front().second;
            q.pop();
            
            for(int i=0; i<4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if( nx >= 0 && nx < n && ny >= 0 && ny < n ){
                    if(!visit[nx][ny]){
                        q.push({nx,ny});
                        if(map[nx][ny])
                            cnt ++;
                    }
                    visit[nx][ny] = 1;
                }
            }
        }
    }
}


int main(){
    int TC;
    cin >> TC;
    
    for(int tc=1; tc<=TC; tc++){
        memset(map,0,sizeof(map));
        memset(visit,0,sizeof(visit));
        max_home = -1;
        cin >> n >> m;
        for(int i=0; i<n; i++) for(int j=0; j<n; j++) scanf("%d",&map[i][j]);
        
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++){
                memset(visit,0,sizeof(visit));
                bfs(i,j);
            }
        printf("#%d %d\n",tc,max_home);
    }
    return 0;
}

Review

  • 생각보다 시간이 많이 걸렸다.

  • 문제를 보면
    ‘손해를 보지 않는다’라는 말이 나온다. = 이익이 없어도 된다 이 부분 때문에 틀린 TC가 나왔다.

  • 재밌었다. 반드시 한번 더 풀어봐야할 문제 !

Recommend

Index