14502-연구소

정말 오랜만에 PS를 해봤다. 중간고사 때문에 그렇기도 하고, 그냥 내가 이 길을 걸을 능력이 있는지 하는 회의가 많이 들어서 그랬다. 결론은 공부도 안해놓고서 이길이 맞을까 하는건 의미 없다 생각해서, 그냥 다시 하기로 했다. 오랜만에 다시 하니까 확실히 재밌다. 그리고 뭔가 요즘은 과학/수학/컴퓨터 뽕이 차오르는 느낌이다.

뭔가 2학년 올라가니까 사회성이 필요한 경우가 많이 생기는데(동아리 회의 진행할땐 미치는 줄 알았다) 하다보면 늘겠지.. 발판삼아서 많이 성장했으면 좋겠다.

어차피 들어오는 사람 별로 없어서 그냥 의식의 흐름대로 써봤다. 

 

오늘 푼 문제는 14502번 연구소 이다.

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

14502번: 연구소

PS 쉬기전에 마지막으로 잡았던 문제였었는데, 잘 안풀렸었다. 근데 이번에 다시 풀어보니까 한 5분만에 풀었다.

 

#include <cstdio>
#include <vector>
int map[10][10], origin[10][10], visited[10][10], n, m, tmp, ans, d[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}, wallCnt;
std::vector<std::pair<int, int>> toWall;
std::vector<std::pair<int, int>> virus;

int max(int a, int b) {
    return (a>b)?a:b;
}

void calc(int x, int y) {
    if(x < 0 || x >= n || y < 0 || y >= m || map[x][y] == 1 || visited[x][y]) return;
    tmp++;
    visited[x][y] = true;
    for(int i = 0; i < 4; i++) {
        calc(x + d[i][0], y + d[i][1]);
    }
    return;
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i  = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            scanf("%d", &origin[i][j]);
            if(origin[i][j] == 0) toWall.push_back(std::make_pair(i, j));
            else if(origin[i][j] == 2) virus.push_back(std::make_pair(i, j));
            else wallCnt++;
        }
    }
    for(int i = 0; i < toWall.size(); i++) {
        for(int j = i+1; j < toWall.size(); j++) {
            for(int l = j+1; l < toWall.size(); l++) {
                for(int x = 0; x < n; x++) {
                    for(int y = 0; y < m; y++) {
                        map[x][y] = origin[x][y];
                        visited[x][y] = false;
                    }
                }
                map[toWall[l].first][toWall[l].second] = 1;
                map[toWall[j].first][toWall[j].second] = 1;
                map[toWall[i].first][toWall[i].second] = 1;
                tmp = 0;
                for(int i = 0; i < virus.size(); i++) calc(virus[i].first, virus[i].second);
                tmp = n*m - wallCnt - tmp - 3;
                ans = max(ans, tmp);
            }
        }
    }
    printf("%d\n", ans);
}

브루트 포스다.

기본 맵을 입력 받고, 벽을 세울수 있는 모든 경우의수를 고려하면 된다.