ggh-png.log

Combination and Permutation

BOJ - 2146 - 다리 만들기

Fri, 13 Jan 2023 07:06:49 GMT

BOJ - 2146 - 다리 만들기

문제

2146번: 다리 만들기

문제

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.

이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.

위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.

물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

입력

첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.

출력

첫째 줄에 가장 짧은 다리의 길이를 출력한다.

예제 입력 1

10
1 1 1 0 0 0 0 1 1 1
1 1 1 1 0 0 0 0 1 1
1 0 1 1 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0

예제 출력 1

출처

구현

#include 
#include 
#include 

using namespace std;

// map 
int n, m;
int map[304][304];
//  섬 번호 visited
int cvisited[304][304];
int visited[304][304];

// joy
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
//int y, x;

// ans
int ans = 987654321;

// 각 섬의 시작 좌표를 담는 큐 
queue, int>> q;

// cnt는 각 섬에 부여된 번호를 뜻합니다. 
void bfs(int sy, int sx, int scnt)
{
    queue, int>> qqq;
    qqq.push({{sy, sx}, scnt});

    while(qqq.size())
    {
        int y = qqq.front().first.first;
        int x = qqq.front().first.second;
        int cnt = qqq.front().second;
        qqq.pop();
        for(int i=0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || nx < 0 || ny >= n || nx >= m)
                continue;

            // 방문하지 않고, 같은 섬일 경우  
            if(!visited[ny][nx] && map[ny][nx] == cnt)
            {
                visited[ny][nx] = 1;
                qqq.push({{ny, nx}, cnt});
            }
            // 방문하지 않고, 바다일 경우 
            if(!visited[ny][nx] && !map[ny][nx])
            {
                visited[ny][nx] = visited[y][x] + 1;
                qqq.push({{ny, nx}, cnt});
            }
            // 다른 섬일 경우 == 다른 섬에 도착 하였을 경우  
            if(map[ny][nx] && map[ny][nx] != cnt)
            {
                visited[ny][nx] = 1;
                ans = min(visited[y][x], ans);
                return;
            }

        }
    }
}

// 섬 번호 부여 bfs 
void color(int sy, int sx, int scnt)
{
    queue, int>> qq;
    qq.push({{sy, sx}, scnt});

    while(qq.size())
    {
        int y = qq.front().first.first;
        int x = qq.front().first.second;
        int cnt = qq.front().second;

        qq.pop();
        for(int i=0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || nx < 0 || ny >= n || nx >= m)
                continue;

            if(!map[ny][nx])
                q.push({{y, x}, cnt});
            if(!cvisited[ny][nx] && map[ny][nx])
            {
                cvisited[ny][nx] = 1;
                map[ny][nx] = cnt;
                qq.push({{ny, nx}, cnt});
            }
        }
    }
}

int main()
{
    cin >> n;
    m = n;
    for(int i=0; i < n; i++)
        for(int j=0; j < m; j++)
            cin >> map[i][j];

    // 섬 번호 부여     
    int cnt = 0;
    for(int i=0; i < n; i++)
        for(int j=0; j < m; j++)
            if(!cvisited[i][j] && map[i][j])
            {
                cnt++;
                map[i][j] = cnt;
                color(i, j, cnt);
            }

    while(q.size())
    {
        bfs(q.front().first.first, q.front().first.second, q.front().second);
        fill(&visited[0][0], &visited[n][n], 0);
        q.pop();
    }

    cout << ans << endl;
    return 0;
}

SOL

각 섬의 번호 부여
각 섬의 모서리 좌표를 큐에 저장 (y, x, land number)
다리 bfs 탐색

Reference & 다른 PS 모음집

BOJ - 1759 - 암호 만들기

Thu, 15 Dec 2022 01:19:52 GMT

BOJ - 1759 - 암호 만들기

문제

1759번: 암호 만들기

문제

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

예제 입력 1

4 6
a t c i s w

예제 출력 1

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

구현

#include 
#include 
#include 

using namespace std;

// 주어진 알파벳에서 모음 2개 이상 추출 
int n, r;

string mo = "aeiou";
// 조합 
vector v;
vector vv;

void combi(int idx)
{
    // 조건을 만족할 경우 
    if(v.size() == n)
    {
        int ja_cnt = 0;
        int mo_cnt = 0;
        for (auto &el : v)
        {
            bool flag = 1;
            for(int i=0; i < mo.size(); i++)
                if(el == mo[i])
                {
                    mo_cnt++;
                    flag = 0;
                    break;
                }
            if(flag)
                ja_cnt++;
        }
        if(mo_cnt >= 1 && ja_cnt >= 2)
        {
            for(auto &el : v)
                cout << el;
            cout << endl;
            //return;
        }
    }
    // 조건을 만족하지 못한 경우 
    for(int i=idx+1; i < r; i++)    
    {  
        v.push_back(vv[i]);
        combi(i);
        v.pop_back();
    } 
        return;
}

int main()
{
    cin >> n >> r;
    for(int i=0; i < r; i++)
    {
        char tmp;
        cin >> tmp;
        vv.push_back(tmp);
    }
    sort(vv.begin(), vv.end());
    combi(-1);
    return 0;
}

SOL

n, r 에 따라 조합을 생성한다.
조건 (모음 1개이상, 자음 2개이상)에 만족하면 출력한다.

Reference & 다른 PS 모음집

Combination and Permutation

BOJ - 1707 - 이분 그래프

Mon, 12 Dec 2022 07:15:35 GMT

BOJ - 1707 - 이분 그래프

문제

1707번: 이분 그래프

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다.

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

제한

2 ≤ K ≤ 5
1 ≤ V ≤ 20,000
1 ≤ E ≤ 200,000

예제 입력 1

예제 출력 1

YES
NO

구현

#include 
#include 

using namespace std;

// 테케, 정점, 간선
int k, v, e;
int visited[20004];
// dfs 
void dfs(int start, vector v[])
{
    // 방문하지 않았더라면 색 1 부여
    if(!visited[start])
        visited[start] = 1;

    // 색 1을 부여한 접한 접점들 조사 
    for(int i=0; i < v[start].size(); i++)
    {
        int idx = v[start][i];
        // 방문을 하지 않았더라면 
        if(!visited[idx])
        {   // 이전 방문 요소가 1번 색이라면 
            if(visited[start] == 1)
                visited[idx] = 2;
            // 이전 방문 요소가 2번 색이라면 
            else if(visited[start] == 2)
                visited[idx] = 1;
            // 다음 요소 방문 
            dfs(idx, v);
        }
    }
}

string check(int V, vector v[])
{
    for(int j=1; j <= V; j++)
        for(int a=0; a < v[j].size(); a++)
        {
            int idx = v[j][a];
            if(visited[j] == visited[idx])
                return "NO";
        }
    return "YES";
}

// 2분 그래프 ... 두 색으로 표현 하되 

int main()
{
    cin >> k;
    for(int i=0; i < k; i++)
    {
        cin >> v >> e;
        int V, E;
        vector v[200004];
        // graph 생성 
        for(int j=0; j < e; j++)
        {
            cin >> V >> E;
            v[V].push_back(E);
            v[E].push_back(V);
        }
        for (int i = 1; i <= V; i++)
            if (!visited[i])
                dfs(i, v);

        cout << check(V, v) << endl;
        // 초기화
        fill(visited, visited + 20004, 0);
    }
    return 0;
}

SOL

양 방향 그래프 생성
dfs를 통해 visited 컬러 부여
check 를 이용하여 전 후 간선이 같다면 NO 출력

Reference & 다른 PS 모음집

BOJ - 19942 - 다이어트

Thu, 01 Dec 2022 05:26:35 GMT

BOJ - 19942 - 다이어트

문제

19942번: 다이어트

문제

식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각각 합이 최소 100, 70, 90, 10가 되도록 하는 경우를 생각해보자. 이 경우 모든 재료를 선택하면 쉽게 해결되지만, 우리는 조건을 만족시키면서도 비용이 최소가 되는 선택을 하려고 한다.

재료	단백질	지방	탄수화물	비타민	가격
1	30	55	10	8	100
2	60	10	10	2	70
3	10	80	50	0	50
4	40	30	30	8	60
5	60	10	70	2	120
6	20	70	50	4	40

예를 들어, 식재료 1, 3, 5를 선택하면 영양분은 100, 145, 130, 10으로 조건을 만족하지만 가격은 270이 된다. 대신 2, 3, 4를 선택하면 영양분의 합은 110, 130, 90, 10, 비용은 180이 되므로, 앞의 방법보다는 더 나은 선택이 된다.

입력으로 식재료 표가 주어졌을 때, 최저 영양소 기준을 만족하는 최소 비용의 식재료 집합을 찾아야 한다.

입력

첫 줄에 식재료의 개수 N$N$이 주어진다.

다음 줄에는 단백질, 지방, 탄수화물, 비타민의 최소 영양성분을 나타내는 정수 mp$mp$, mf$mf$, ms$ms$, mv$mv$가 주어진다.

이어지는 N$N$개의 각 줄에는 i$i$번째 식재료의 단백질, 지방, 탄수화물, 비타민과 가격이 5개의 정수 pi$p_i$, fi$f_i$, si$s_i$, vi$v_i$, ci$c_i$와 같이 주어진다. 식재료의 번호는 1부터 시작한다.

출력

첫 번째 줄에 최소 비용을 출력하고, 두 번째 줄에 조건을 만족하는 최소 비용 식재료의 번호를 공백으로 구분해 오름차순으로 한 줄에 출력한다. 같은 비용의 집합이 하나 이상이면 사전 순으로 가장 빠른 것을 출력한다.

조건을 만족하는 답이 없다면 -1을 출력하고, 둘째 줄에 아무것도 출력하지 않는다.

제한

$3 \le N \le 15$

3≤N≤15
$0 \le mp, mf, ms, mv \le 500$

0≤mp,mf,ms,mv≤500
$mp + mf + ms + mv > 0$

mp+mf+ms+mv>0
$0 \le p_i, f_i, s_i, v_i, c_i \le 500$

0≤pi,fi,si,vi,ci≤500

예제 입력 1

6
100 70 90 10
30 55 10 8 100
60 10 10 2 70
10 80 50 0 50
40 30 30 8 60
60 10 70 2 120
20 70 50 4 4

예제 출력 1

134
2 4 6

구현

#include 
#include 
#include 

using namespace std;

class vita
{
public:
    int a=0, b=0, c=0, d=0, e=0;
};

class result
{
public:
    int a, b, c, d, e;
    string f;
};

int num;
vector v;
int q, w, e, r, t;
int limA, limB, limC, limD;

string ans = "";
vector answer;

bool comapre(result a , result b)
{   // 금액이 같으면 사전순으로 정렬 
    if(a.e == b.e)
        return a.f > b.f;
    return a.e > b.e;
}

int main()
{
    cin >> num;
    cin >> limA >> limB >> limC >> limD;
    for(int i=0; i < num; i++)
    {
        cin >> q >> w >> e >> r >> t;
        v.push_back({q, w, e, r, t});
    }
    // 모든 경우의 수 
    // 6   64
    for(int i=0; i < (1 << num); i++)
    {
        vita lim;
        vector N;
        for(int j=0; j < num; j++)
            if(i & (1 << j))
            {
                lim.a += v[j].a;
                lim.b += v[j].b;
                lim.c += v[j].c;
                lim.d += v[j].d;
                lim.e += v[j].e;
                // 비타민 번호 index 
                N.push_back(j+1);
                // limit 조건에 충족 하면 
                if(lim.a >= limA && lim.b >= limB && lim.c >= limC && lim.d >= limD)
                {
                    ans = "";
                    for(auto &el : N)
                        ans += to_string(el) + " ";
                    result tmp;
                    tmp.a = lim.a;
                    tmp.b = lim.b;
                    tmp.c = lim.c;
                    tmp.d = lim.d;
                    tmp.e = lim.e;
                    tmp.f = ans;
                    answer.push_back(tmp);
                }
            }
    }
    // 조건에 충족한 정답이 있다면 
    if(answer.size())
    {
        sort(answer.rbegin(), answer.rend(), comapre);
        cout << answer.front().e << endl << answer.front().f << endl;
    }
    else
        cout << -1 << endl;
    return 0;
}

SOL

bitmasking을 이용하여 모든 경우의 수를 추출
1. 조건에 맞을 시 result vector에 push
2. cost를 기준으로 내림차순 정렬
  1. 내림차순 정렬 시 cost의 값이 같다면 사전순으로 정렬

Reference & 다른 PS 모음집

9. C++ STL sort() 함수 다루기 ②

BitMasking

C++ 비트 마스킹

Thu, 01 Dec 2022 05:19:10 GMT

C++ 비트 마스킹

개yo

이번 포스팅에선 기본적인 비트 연산을 알아보고 직접 구현해 보고, 이를 이용한 조합Combination을 함께 알아보도록 하겠다.

비트 연산

먼저 비트연산에 대하여 알아 보도록 하겠다.

우선 왼쪽 시프트 연산자 << 는 수를 왼쪽으로 이동한다는 의미다.

비트마스킹에서 보통 (1 << x)이 꼴로 많이 쓰인다.

int a = 8 → 0110

예를 들어 (1 << 2)는 2의 2승, (1 << 0)은 2의 0승을 상징한다.

idx번째 비트끄기	S &= ~(1 << idx)
idx번째에 대한 XOR 연산(0은 1로, 1은 0으로)	S ^= (1 << idx)
최하위 켜져있는 idx 찾기	idx = (S & -S)
n인 집합의 모든 비트를 켜기	(1 << n) - 1
idx번째 비트를 켜기	S
idx번째 비트가 있는지 확인하기	if(S & (1 << idx))
- 최하위 비트찾기 idx = (S & -S)

자 저 -1이 뭔지를 보자.

예를 들어 x = 0110 이라고 해보자. ~x = 1001이된다. (사실 그 위의 있는 비트도 뒤집히긴 하나 생략.)

여기서 ~ x + 1을 하게 되면 1010이 되고

이 ~x +1 & x를 하게 되면 가장 끝자리에 있는 켜져있는 비트를 뽑아낼 수 있다.

x = (~x + 1) 의 특징을 가지므로
x & x로 놓을 수 있다.

ex code

#include 

using namespace std; 

void t1()
{
    int n = 15; // 1111 
    int idx = 2;  
    n &= ~(1 << idx); // 1'1'11 -> 1'0'11 == 11
    cout << "1. idx번째 비트 끄기 : " << n << "\n";
}
void t2()
{
    int n = 11;  // 1011 
    int idx = 2;  
    n ^= (1 << idx); // 1'0'11 -> 1'1'11 == 15
    cout << "2. 0은 1로, 1은 0으로 XOR T2 : " << n << "\n";
}

void t3()
{
    int n = 6;  // 0110
    int idx = (n & -n);  // 0110 & 1110 == 0110
    cout << "3. 최하위 켜져있는 인덱스 T3: " << idx << "\n";
}
void t4()
{
    int n = 3;  // 000 - 100
    cout << "4. 크기가 n인 모든 집합의 모든 비트 켜기 T4 : " << (1 << n) - 1 << "\n";
}
void t5(){
    int n = 5;
    int idx = 1; // 0101 => 0111 7   
    n |= (1 << idx);  
    cout << "5. idx번째 불켜기 T5 : " << n << "\n";
}

void t6(){
    int n = 5; // 0101
    int idx = 1;   
    string a = n & (1 << idx) ? "yes" : "no";
    cout << "6. idx번째 비트가 있는지 확인하기 T6 : " << a << "\n";
}

int main() {   
    t1();
    t2();
    t3();
    t4();
    t5();
    t6(); 
    return 0;
}
/*
1. idx번째 비트 끄기 : 11
2. 0은 1로, 1은 0으로 XOR T2 : 15
3. 최하위 켜져있는 인덱스 T3: 2
4. 크기가 n인 모든 집합의 모든 비트 켜기 T4 : 7
5. idx번째 불켜기 T5 : 7
6. idx번째 비트가 있는지 확인하기 T6 : no
*/

비트마스킹

어떠한 특정원소를 찾을 때 어느정도의 시간복잡도는 자료구조 마다 다르다.

배열의 어떤 요소를 찾을 때 선형적인 시간 : O(N)
sorted array에서 이분탐색으로 찾을 때는 O(logN)
해싱테이블에서는 O(1)

그렇다면 불리언 배열에서 무언가를 찾는 등의 연산은 어떻게 될까? 보통 불리언배열은 vector, bitset, set 로 표현해서 처리하곤 한다. 여기서 find메서드를 쓰는 등을 통해 연산을 한다. 하지만 이러한 것들보다 비트연산을 쓰면 좀 더 가볍고 빠르게 된다.

이렇게 불리언배열의 역할을 하는 "하나의 숫자"를 만들어서 "비트 연산자"를 통해 탐색, 수정 등의 작업을 하는 것을 비트마스킹이라고 한다.

101은 1(0 0 1)과 4(1 0 0)의 합집합이며 이는 {0, 2}로 표현이 가능하고,

111은? {0, 1, 2}로 표현이 가능하다.

즉, 불리언배열을 만들어서 {0, 1, 0, 1} 이렇게 만들지 않고 0101 이라는 하나의 수, 5 등을 이용해 하나의 숫자로 불리언 배열같은 역할을 할 수 있다. 또한 앞서 배운 비트연산자를 통해 해당 요소가 포함되어있는지 안되어있는지 등을 쉽게 알 수 있다.

참고 : 왜 비트마스킹이라고 할까?

컴퓨터의 저장 공간인 메모리에는 0이나 1이 저장된다. 이러한 메모리의 용량을 표현하는 단위는 여러가지가 있는데 그 중 최소 단위를 비트(Bit)라고 하며 이 비트는 0 또는 1이라는 값을 가진다. 이를 기반으로 해당 비트를 켜거나(1로 만들거나) 끄거나(0으로 만들거나) 하는 "마스킹"하기 때문에 비트마스킹이라고 한다.

참고로 비트는 이진수의 약어다. 비트나 이진수나 똑같은 개념이라고 보면 된다. (BIT = Binary Digit)

비스마스킹을 이용한 경우의 수

비스마스킹은 경우의 수를 표현하는데도 잘 쓰이는데 예를 들어 {사과, 딸기, 포도, 배}의 모든 경우의 수는 어떻게 될까?

{사과}

{딸기, 사과}

총 16가지수가 나오게 되는데, 사과를 포함하거나 포함하지 않거나 해서 각각의 요소는 2개의 상태값을 가지기 때문에 2^4 = 16이 되는 것이다..

#include 
using namespace std;  
const int n = 4;
int main() {   
    string a[n] = {"사과", "딸기", "포도", "배"};
    for(int i = 0; i < (1 << n); i++){
        string ret = "";
        for(int j = 0; j < n; j++){
            if(i & (1 << j)){
                ret += (a[j] + " ");
            }
        }
        cout << ret << '\n';
    } 
    return 0;
} 
/*

사과 
딸기 
사과 딸기 
포도 
사과 포도 
딸기 포도 
사과 딸기 포도 
배 
사과 배 
딸기 배 
사과 딸기 배 
포도 배 
사과 포도 배 
딸기 포도 배 
사과 딸기 포도 배 
*/

이렇게 모든 집합을 표현한 것을 볼 수 있다.

i는 0000, 0001, 0010을 상징한다.

j는 0, 1, 2, 3을 기반으로 (1 << 0), (1 << 1) 등으로 해당 번째의 비트가 켜져있냐 켜져있지 않냐를 통해 집합을 확인 한다.

즉 이러한 것을 통해 4C1, 4C2 ... 이러한 조합들의 모든 경우의 수를 한번의 for문 만으로 표현이 가능한 셈이다.

문제에서 4C1, 4C2 여러가지 조합 등 모든 경우의 수를 기반으로 로직을 짜야 하는 경우 유용하다.

비트마스킹을 이용한 매개변수 전달

사과라는 매개변수가 포함이 되어있고 이어서 사과 + 포도, 사과 + 배 이런식의 매개변수를 더하는 것을 구현하고 싶다면 이렇게 하면 된다.

#include 
using namespace std;  
const int n = 4;
string a[4] = {"사과", "딸기", "포도", "배"};
void go(int num){
    string ret = "";    
    for(int i = 0; i < 4; i++){
        if(num & (1 << i)) ret += a[i] + " ";
    }
    cout << ret << '\n';
    return;
}
int main() {    
    for(int i = 1; i < n; i++){
        go(1 | (1 << i));
    } 
    return 0;
} 
/*
사과 딸기 
사과 포도 
사과 배
*/

이처럼 << 또는 & 등 비트연산자 등으로 불리언배열의 역할을 하는 비트마스킹을 알아보았다.

하지만 비트마스킹은 한계가 있습니다. 바로 31까지 가능하다. int형 숫자의 한계까지인 셈이다. long long은 어떠냐 하는 의견도 있는데 보통 2^ 30승정도만 해도... 10억이 되기 때문에 그 이후의 경우의 수를 센다는 것 자체가 이미 시간복잡도를 많이 초과하기 때문에 보통은 30 ~ 31 까지의 경우의 수만을 표현할 수 있다고 볼 수 있다.

Reference

[알고리즘 강의] 4주차. 비트마스킹

BOJ - 11724 - 연결 요소의 개수

Tue, 29 Nov 2022 03:53:50 GMT

BOJ - 11724 - 연결 요소의 개수

문제

11724번: 연결 요소의 개수

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

구현

#include 
#include 

using namespace std;

// map
vector map[1004];
int visited[1004];
int n, m;
int cnt = 0;

void dfs(int idx)
{
    visited[idx] = 1;
    for(auto &el : map[idx])
    {
        int index = el;
        if(!visited[index])
            dfs(el);
    }
}

int main()
{
    cin >> n >> m;
    int u, v;
    // 연결 리스트 생성 
    for(int i=0; i < m; i++)
    {
        cin >> u >> v;
        map[u].push_back(v);
        map[v].push_back(u);
    }
    // 완전 탐색, 방문하지 않았더라면 == 간선++
    for (int i = 1; i <= n; i++) 
        if (!visited[i])
        {
            cnt++;
            dfs(i);
        }

    cout << cnt;
    return 0;
}

SOL

연결 리스트 생성
탐색 후 방문하지 않았더라면 cnt++

Reference & 다른 PS 모음집

BOJ - 18405 - 경쟁적 전염

Thu, 24 Nov 2022 03:58:09 GMT

BOJ - 18405 - 경쟁적 전염

문제

18405번: 경쟁적 전염

문제

NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.

시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.

시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y는 각각 행과 열의 위치를 의미하며, 시험관의 가장 왼쪽 위에 해당하는 곳은 (1,1)에 해당한다.

예를 들어 다음과 같이 3x3 크기의 시험관이 있다고 하자. 서로 다른 1번, 2번, 3번 바이러스가 각각 (1,1), (1,3), (3,1)에 위치해 있다. 이 때 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류를 계산해보자.

1초가 지난 후에 시험관의 상태는 다음과 같다.

2초가 지난 후에 시험관의 상태는 다음과 같다.

결과적으로 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류는 3번 바이러스다. 따라서 3을 출력하면 정답이다.

입력

첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으로 구분되어 주어진다. 단, 해당 위치에 바이러스가 존재하지 않는 경우 0이 주어진다. 또한 모든 바이러스의 번호는 K이하의 자연수로만 주어진다. N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어진다. (0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)

출력

S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력한다. 만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다.

구현

#include 
#include 

using namespace std;

// map 
int n, m, k;
int map[204][204];
int visited[204][204];
int sy, sx, ss;
// joy
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
vector> v[1004];
vector> tmp[1004];

void spread(int y, int x, int color)
{ 
    for(int i=0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny >= n || nx >= m || ny < 0 || nx < 0)
            continue;
        if(!map[ny][nx])
        {
            map[ny][nx] = color;
            tmp[color].push_back({ny, nx});
        }
    }
}

int main()
{
    cin >> n >> k;
    m = n;
    int mx=0;
    for(int i=0; i < n; i++)
        for(int j=0; j < m; j++)
        {
            cin >> map[i][j];
            if(map[i][j])
                v[map[i][j]].push_back({i, j});
            mx = max(mx, map[i][j]);
        }

    cin >> ss >> sy >> sx;

    for(int j=0; j < ss; j++)
        for(int i=0; i <= mx; i++)
        {
            while(v[i].size())
            {
                spread(v[i].front().first, v[i].front().second , i);
                v[i].erase(v[i].begin());
            }
            while(tmp[i].size())
            {
                v[i].push_back({tmp[i].front().first, tmp[i].front().second});
                tmp[i].erase(tmp[i].begin());
            }
        }

    cout << map[sy-1][sx-1] << endl;
    return 0;
}

SOL

1초당 1회만 전염시킬 것

 void spread(int y, int x, int color)
 { 
     for(int i=0; i < 4; i++)
     {
         int ny = y + dy[i];
         int nx = x + dx[i];
         if(ny >= n || nx >= m || ny < 0 || nx < 0)
             continue;
         if(!map[ny][nx])
         {
             map[ny][nx] = color;
                         // 감염 확산 
             tmp[color].push_back({ny, nx});
         }
     }
 }

우선순위로 숫자가 낮은 감염요소부터 감염될 것

   // 주어진 시간동안   
     for(int j=0; j < ss; j++)
     // 우선순위가 낮은 감염요소부터 
         for(int i=0; i <= mx; i++)
         {
     // 감염 시작 
             while(v[i].size())
             {
                 spread(v[i].front().first, v[i].front().second , i);
                 v[i].erase(v[i].begin());
             }
     // 새로운 감염좌표 입력 
             while(tmp[i].size())
             {
                 v[i].push_back({tmp[i].front().first, tmp[i].front().second});
                 tmp[i].erase(tmp[i].begin());
             }
         }

Reference & 다른 PS 모음집

BOJ - 2665 - 미로만들기

Mon, 14 Nov 2022 03:46:53 GMT

BOJ - 2665 - 미로만들기

문제

2665번: 미로만들기

문제

n×n 바둑판 모양으로 총 n2개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다.

시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데, 아래 그림의 경우에는 시작방에서 끝 방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다.

아래 그림은 n=8인 경우의 한 예이다.

위 그림에서는 두 개의 검은 방(예를 들어 (4,4)의 방과 (7,8)의 방)을 흰 방으로 바꾸면, 시작방에서 끝방으로 갈 수 있지만, 어느 검은 방 하나만을 흰 방으로 바꾸어서는 불가능하다. 검은 방에서 흰 방으로 바꾸어야 할 최소의 수를 구하는 프로그램을 작성하시오.

단, 검은 방을 하나도 흰방으로 바꾸지 않아도 되는 경우는 0이 답이다.

입력

첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다.

출력

첫 줄에 흰 방으로 바꾸어야 할 최소의 검은 방의 수를 출력한다.

구현

#include 
#include 
#include 
#include 

using namespace std;

// map
int n, m;
int map[55][55];
int visited[55][55][255];

// joy 
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
vector v;

void bfs(int sy, int sx, int sbk)
{
    queue, int>> q;
    q.push({{sy, sx}, sbk});
    while(q.size())
    {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int bk = q.front().second;

        if(y == n-1 && x == m-1)
            v.push_back(bk);

        q.pop();
        for(int i=0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || ny >= n || nx < 0 || nx >= m)
                continue;
            if(map[ny][nx] && !visited[ny][nx][bk])
            {
                visited[ny][nx][bk] = visited[y][x][bk] + 1;
                q.push({{ny, nx}, bk});
            }
            if(!map[ny][nx] && !visited[ny][nx][bk+1])
            {
                visited[ny][nx][bk+1] = visited[y][x][bk] + 1;
                q.push({{ny, nx}, bk+1});
            }
        }
    }
}

int main()
{
    cin >> n;
    m = n;
    for(int i=0; i < n; i++)
    {
        string str;
        cin >> str;
        for(int j=0; j < m; j++)
            map[i][j] = str[j] - 48;
    }

    bfs(0, 0, 0);
    sort(v.begin(), v.end());

    cout << v[0] << endl;

    return 0;
}

SOL

visited[ y ][ x ][ bk ]
1. y, x == 좌표
2. bk == 벽을 뚫고간 횟수
bfs를 실행시켜 목적지에 도착하게 되면 벽을 뚫고 간 횟수흫 vector 에 저장
1. 저장된 vector를 내림차순 정렬 후 정답 출력

Reference & 다른 PS 모음집

C++ 순열과 조합

Mon, 24 Oct 2022 05:33:42 GMT

C++ 순열과 조합

개요

12명이 서로(2명씩) 인사하면 66가지의 경우에 수가 나오게 된다. 이 경우의 수는 순열과 조합으로 구할 수 있는데

이번 포스팅에선 이 순열과 조합에 대해 알아 보고, 코드로 구현까지 해보도록 하겠다.

순열

먼저 순열, permutation이란 순서가 정해진 임의의 집합을 다른 순서로 섞는 연산을 말한다.

즉 예를들어 { 1, 2, 3 } 의 요소가 있을 때 { 1, 3, 2 } 이런식으로 다른 순서로 섞는것을 연산 순열이라 한다.

만약 n 개의 집합 중 n개를 고르는 순열의 개수를 구할 때 중복을 허용한다면 n!이 된다.
위의 예를 들어 보자면 3개의 자연수{ 1, 2, 3 }를 이용해 만들 수 있는 3자리 자연수는 몇개 일까?

[ 123,132, 213, 231, 312, 321 ] 6개의 순열이 나오게 된다.

또 만약 3개의 자연수{ 1, 2, 3 }를 이용해 만들 수 있는 1자리 자연수는 3개다.

전자는 3개중 3개를 뽑는 것이기에 3!이 되고 후자는 3개중 1개를 뽑는 것이라 3이 되게 된다.

nPr = n! / (n - r)!

n : 요소의 개수 r : 요소에서 필요로하는 개수

위와 같은 문제는 위 공식에 따라 몇개인지 결정이 됩니다. 예를 들어 3개 중 3개를 뽑는다면 3!/(3 - 3)! 이 되고 3개 중 1개를 뽑는다면 3! / (3 - 1)! 이 되는 것이다.

이를 코드로 구현을 하면 비트 마스킹, next_permutation과 perv _permutation, 재귀 각각 세가지의 방법이 존재한다.

next_permutation, perv_permutation - Permutation

#include 
#include 
#include 
#include 
using namespace std;

void printV(vector &v)
{
    for(int i = 0; i < v.size(); i++)
            cout << v[i] << " ";
    cout << "\n";
}
int main()
{
    int a[3] = {1, 2, 3};
    vector v;
    for(int i = 0; i < 3; i++)
        v.push_back(a[i]);
        //1, 2, 3부터 오름차순으로 순열을 뽑습니다.

    do
        printV(v);
    while(next_permutation(v.begin(), v.end()));

    cout << "-------------" << '\n';
    v.clear();
    for(int i = 2; i >= 0; i--)
        v.push_back(a[i]);
        //3, 2, 1부터 내림차순으로 순열을 뽑습니다.
    do
        printV(v);
    while(prev_permutation(v.begin(), v.end()));

    return 0;
}

출력

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
-------------
3 2 1
3 1 2
2 3 1
2 1 3
1 3 2
1 2 3

사용법

오름차순

   do
        printV(v);
    while(next_permutation(v.begin(), v.end()));

내림차순

    do
        printV(v);
    while(prev_permutation(v.begin(), v.end()));

재귀함수 - Permutation

#include 
#include 
#include 
#include 
using namespace std;

int a[3] = {1, 2, 3};
vector v;

void printV(vector &v)
{
    for(int i = 0; i < v.size(); i++)
        cout << v[i] << " ";
    cout << "\n";
}

void makePermutation(int n, int r, int depth)
{
    if(r == depth)
    {   
        printV(v);
        return;
    }
    for(int i = depth; i < n; i++)
    {
        swap(v[i], v[depth]);
        makePermutation(n, r, depth + 1);
        swap(v[i], v[depth]);
    }
    return;
}

int main()
{
    for(int i = 0; i < 3; i++)
        v.push_back(a[i]);
    makePermutation(3, 3, 0);
    return 0;
}

출력

재귀 - Permutation sol

순열을 만들고, 다시 돌려 놓는다.
- 완전탐색 이용

 void makePermutation(int n, int r, int depth)
{
    if(r == depth)
    {   
        printV(v);
        return;
    }
    for(int i = depth; i < n; i++)
    {
        swap(v[i], v[depth]);
        makePermutation(n, r, depth + 1);
        swap(v[i], v[depth]);
    }
    return;
}

조합 - Combination

순열, permutation이 순서가 정해진 임의의 집합을 다른 순서로 섞는 연산이라면, 조합 Combination 은 순서가 정해지지 않은 집합들의 모음을 뜻한다.

nCr = n! / r!(n-r)!

n : 요소의 개수 r : 요소에서 필요로하는 개수

공식은 위와 같으며 예를들어 서로 다른 5개의 구슬 중 3개의 구슬을 뽑는 상황에서의 조합의 결과는 다음과 같다.

5C3 = 5! / 3!(5 - 3)! = 10

재귀함수 - Combination

#include 
#include 
#include 

using namespace std;

// 서로다른 5개의 구슬이 들어있는 구슬망에서 3개의 구슬을
// 뽑는 조합 구현 
// nCr = 5C3

int n = 5;
int r = 3;
int arr[] = {1, 2, 3, 4, 5};

vector v;

void CombiPrint(vector v)
{
    for(auto &el : v)
        cout << el << " ";
    cout << endl;
}

void combi(int start, vector v)
{
    // 3개의 구슬이 뽑아지면
    if(v.size() == r)
    {
        CombiPrint(v);
        return;
    }
    for(int i=start+1; i < n; i++)
    {
        v.push_back(arr[i]);
        combi(i, v);
        v.pop_back();
    }
    return;
}

int main()
{
    combi(-1, v);
    return 0;
}

출력

재귀 - Combination 완전 탐색

void combi(int start, vector v)
{
    // 3개의 구슬이 뽑아지면
    if(v.size() == r)
    {
        CombiPrint(v);
        return;
    }
    for(int i=start+1; i < n; i++)
    {
        v.push_back(arr[i]);
        combi(i, v);
        v.pop_back();
    }
    return;
}

벡터에 요소를 넣고 3개의 구슬을 뽑게되면 리턴하여 함수를 종료 하게 한다.

1차적으로 종료된 함수는 처음으로 뽑은 구슬을 다시 빼게 되면서 완전탐색을 할 수 있도록 구현 한다.

다중 for문 - r 값이 작을 경우 (3이하)

#include 

using namespace std;

int main()
{
    int a[] = {1, 2, 3, 4, 5, 6};
    for(int i = 0; i < 6; i++)
        for(int j = 0; j < i; j++)
            for(int k = 0; k < j; k++)
                cout << a[i] << " " << a[j] << " " << a[k] << endl; 
    return 0;
}

SOL

r 값 즉, 집합에서 요소를 뽑아야 되는 개수가 3이하로 작다면 위와 같이 다중 for문으로 구할 수 있다.

다중 for문의 장점은 재귀를 이용한 조합을 구현하는 것 보다 더 쉽게 구현 할 수 있다는 장점이 있다.

Reference

큰돌의 터전 : 네이버 블로그

BOJ - 1431 - 시리얼 번호

Thu, 20 Oct 2022 03:35:05 GMT

BOJ - 1431 - 시리얼 번호

문제

1431번: 시리얼 번호

문제

다솜이는 기타를 많이 가지고 있다. 그리고 각각의 기타는 모두 다른 시리얼 번호를 가지고 있다. 다솜이는 기타를 빨리 찾아서 빨리 사람들에게 연주해주기 위해서 기타를 시리얼 번호 순서대로 정렬하고자 한다.

모든 시리얼 번호는 알파벳 대문자 (A-Z)와 숫자 (0-9)로 이루어져 있다.

시리얼번호 A가 시리얼번호 B의 앞에 오는 경우는 다음과 같다.

A와 B의 길이가 다르면, 짧은 것이 먼저 온다.
만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다)
만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다.

시리얼이 주어졌을 때, 정렬해서 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어져 있다. 시리얼 번호는 중복되지 않는다.

출력

첫째 줄부터 차례대로 N개의 줄에 한줄에 하나씩 시리얼 번호를 정렬한 결과를 출력한다.

구현

#include 
#include 
#include 

using namespace std;

bool compare(string a, string b)
{
    if(a.size() == b.size())
    {
        int sizea = 0;
        int sizeb = 0;
        for(auto &el : a)
            if(el >= '0' && el <= '9')
                sizea += int(el) - 48;
        for(auto &el : b)
            if(el >= '0' && el <= '9')
                sizeb += int(el) - 48;
        if(sizea == sizeb)
            return a < b;
        return sizea < sizeb;  
    }
    return a.size() < b.size();
}

int main()
{
    vector v;
    int num;
    cin >> num;
    for(int i=0; i < num; i++)
    {
        string str;
        cin >> str;
        v.push_back(str);
    }
    sort(v.begin(), v.end(), compare);
    for(auto &el : v)
        cout << el << endl;
    return 0;
}

SOL

string 사이즈로 정렬
각각의 string 내에 포함되어 있는 숫자들의 합으로 정렬
사전순으로 정렬

Reference & 다른 PS 모음집

BOJ - 1245 - 농장 관리

Mon, 17 Oct 2022 04:36:50 GMT

BOJ - 1245 - 농장 관리

문제

1245번: 농장 관리

문제

농부 민식이가 관리하는 농장은 N×M 격자로 이루어져 있다. 민식이는 농장을 관리하기 위해 산봉우리마다 경비원를 배치하려 한다. 이를 위해 농장에 산봉우리가 총 몇 개 있는지를 세는 것이 문제다.

산봉우리의 정의는 다음과 같다. 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. (여기서 "인접하다"의 정의는 X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정의된다.) 또한 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야한다.

문제는 격자 내에 산봉우리의 개수가 총 몇 개인지 구하는 것이다.

입력

첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 산봉우리의 개수를 출력한다.

구현

#include 

using namespace std;

// map
int n, m;
int map[104][104];
bool visited[104][104];

// joy
int dy[] = {-1, 0, 1, 0, 1, 1, -1, -1};
int dx[] = {0, 1, 0, -1, 1, -1, -1, 1};
// ans
int ans = 0;
bool peak;
void dfs(int y, int x)
{
    visited[y][x] = 1;
    for(int i=0; i < 8; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 || nx < 0 || ny >= n || nx >= m)
            continue;
        if(map[ny][nx] > map[y][x])
            peak = 0;
        if(map[ny][nx] == map[y][x] && !visited[ny][nx])
            dfs(ny, nx);

    }
}

int main()
{
    cin >> n >> m;
    for(int i=0; i < n; i++)
        for(int j=0; j < m; j++)
            cin >> map[i][j];

    for(int i=0; i < n; i++)
        for(int j=0; j < m; j++)
            if(!visited[i][j] && map[i][j])
            {
                peak = 1;
                dfs(i, j);
                if(peak)
                    ans++;
            }

    cout << ans << endl;
    return 0;
}

SOL

// 봉우리가 아닐 경우 
if(map[ny][nx] > map[y][x])
    peak = 0;
// 같은 높이고, 방문하지 않았을 경우 
if(map[ny][nx] == map[y][x] && !visited[ny][nx])
    dfs(ny, nx);

Reference & 다른 PS 모음집

BOJ - 14923 - 미로탈출

Sun, 16 Oct 2022 05:24:51 GMT

BOJ - 14923 - 미로탈출

문제

14923번: 미로 탈출

문제

홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 있어 홍익이가 탈출하기 어렵게 하고 있다.

홍익이는 마법사의 연구실에서 훔친 지팡이가 있어, 벽을 길로 만들 수 있다. 그렇지만, 안타깝게도 마법의 지팡이는 단 한 번만 사용할 수 있다.

이때, 홍익이를 도와 미로에서 탈출할 수 있는지 알아보고, 할 수 있다면 가장 빠른 경로의 거리 D는 얼마인지 알아보자.

인접한 칸으로 이동하는데 똑같은 시간이 들고, 벽을 부수는 데 시간이 걸리지 않는다.

입력

N M
Hx Hy
Ex Ey
N X M 행렬

2 ≤ N ≤ 1000, 2 ≤ M ≤ 1000
1 ≤ Hx, Hy, Ex, Ey ≤ 1000
(Hx, Hy)≠ (Ex, Ey)
행렬은 0과 1로만 이루어져 있고, 0이 빈 칸, 1이 벽이다.

출력

D (탈출 할 수 없다면, -1을 출력한다.)

구현

#include 
#include 

using namespace std;

// map
bool map[1004][1004];
int visited[1004][1004][2];
int n, m;

// xy 
int hy, hx;
int ey, ex;
// joy
int dy[] = {-1, 1, 0, 0};
int dx[] = {0, 0, 1, -1};
// ans
int ans = -1;

void bfs(int sy, int sx, bool sbk)
{
    queue, bool>> q;
    q.push({{sy, sx}, sbk});
    while(q.size())
    {
        int y = q.front().first.first;
        int x = q.front().first.second;
        bool bk = q.front().second;
        q.pop();
        if(y == ey-1 && x == ex-1)
        {
            ans = visited[y][x][bk];
            break;
        }
        for(int i=0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || nx < 0 || ny >= n || nx >= m)
                continue;
            if(!map[ny][nx] && !visited[ny][nx][bk])
            {
                visited[ny][nx][bk] = visited[y][x][bk] + 1;
                q.push({{ny, nx}, bk});
            }
            if(map[ny][nx] && !bk && !visited[ny][nx][bk+1])
            {
                visited[ny][nx][bk+1] = visited[y][x][bk] + 1;
                q.push({{ny, nx}, bk+1});
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    cin >> hy >> hx;
    cin >> ey >> ex;

    for(int i=0; i < n; i++)
        for(int j=0; j < m; j++)
            cin >> map[i][j];

    bfs(hy-1, hx-1, 0);
    cout << ans << endl;
}

SOL

벽을 넘어간 경우와 그렇지 못한 경우를 2가지로 나누어 bfs를 구현한다.
1. visited[][][] 3차원 배열 생성

Reference & 다른 PS 모음집

BOJ - 3055 - 탈출

Sat, 15 Oct 2022 05:07:33 GMT

BOJ - 3055 - 탈출

문제

3055번: 탈출

문제

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.

입력

첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.

다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

출력

첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.

구현

#include 
#include 
#include 

using namespace std;

// map
int n, m;
char map[55][55];
int fvisited[55][55];
int evisited[55][55];

// joy 
int dy[] = {1, -1, 0, 0};
int dx[] = {0, 0, 1, -1};
// 도치, 비버 굴
int Sy, Sx;
int Dy, Dx;
// 홍수 위치
queue> wq;

// 홍수 bfs 
void flood()
{
    while(wq.size())
    {
        int y = wq.front().first;
        int x = wq.front().second;
        wq.pop();
        for(int i=0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || nx < 0 || ny >= n || nx >= m || fvisited[ny][nx])
                continue;
            if(map[ny][nx] == '.')
            {
                fvisited[ny][nx] = fvisited[y][x] + 1;
                wq.push({ny, nx});
            }
            if(map[ny][nx] == 'D')
                fvisited[ny][nx] = fvisited[y][x];

        }
    }
}

void escape(int sy, int sx)
{
    queue> q;
    q.push({sy, sx});
    while(q.size())
    {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        for(int i=0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || nx < 0 || ny >= n || nx >= m || evisited[ny][nx])
                continue;
            if(map[ny][nx] == 'D' || map[ny][nx] == '.' && (!fvisited[ny][nx] || (fvisited[ny][nx] > evisited[y][x] + 1)))
            {
                evisited[ny][nx] = evisited[y][x] + 1;
                q.push({ny, nx});
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    for(int i=0; i < n; i++)
        for(int j=0; j < m; j++)
        {
            cin >> map[i][j];
            if(map[i][j] == '*')
                wq.push({i, j});
            if(map[i][j] == 'D')
            {
                Dy = i;
                Dx = j;
            }
            if(map[i][j] == 'S')
            {
                Sy = i;
                Sx = j;
            }
        }
    flood();
    escape(Sy, Sx);
    if(!evisited[Dy][Dx])
        cout << "KAKTUS" << endl;
    else    
        cout << evisited[Dy][Dx] << endl;

    return 0;
}

SOL

홍수를 먼저 일으킨다.
탈출 경로를 구할 때 물이 들어오지 않거나, 탈출경로가 더 빠를 경우를 생각하여 bfs를 실행한다.

Reference & 다른 PS 모음집

BOJ - 2638 - 치즈

Tue, 11 Oct 2022 06:06:01 GMT

BOJ - 2638 - 치즈

문제

2638번: 치즈

문제

N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

<그림 1>

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

<그림 2>

<그림 3>

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

출력

출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

구현

#include 

using namespace std;

// map
int n, m;
bool map[104][104];
int visited[104][104];

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

void dfs(int y, int x)
{
    visited[y][x] = 1;
    for(int i=0; i < 4; i++)
    {
        int ny = dy[i] + y;
        int nx = dx[i] + x;
        if(ny < 0 || ny >= n || nx < 0 || nx >= m)
            continue;
        // 방문하지 않았고, 밖인 경우 
        if(!visited[ny][nx] && !map[ny][nx])
        {
            visited[ny][nx] = 1;
            dfs(ny, nx);
        }
        if(map[ny][nx])
            visited[ny][nx]++;
    }
}

int main()
{
    cin >> n >> m;
    for(int i=0; i < n; i++)
        for(int j=0; j < m; j++)
            cin >> map[i][j];
    int cnt = 0;
    while(1)
    {
        bool flag = 1;
        cnt++;
        dfs(0, 0);

        for(int i=0; i < n; i++)
        {
            for(int j=0; j < m; j++)
            {
                if(visited[i][j] >= 2)
                    map[i][j] = 0;
                if(map[i][j] == 1)
                    flag = 0;
            }
        }
        fill(&visited[0][0], &visited[n][m], 0);
        if(flag == 1)
            break;
    }
    cout << cnt << endl;
    return 0;
}

SOL

dfs 실행하되 빈 치즈인 부분에 인접하면 증산값++

한번 실행시 증산값이 2보다 크면 해당 좌표에 있는 치즈 제거

Reference & 다른 PS 모음집

BOJ - 17142 - 연구소 3

Tue, 11 Oct 2022 04:55:33 GMT

BOJ - 17142 - 연구소 3

문제

17142번: 연구소 3

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2

M = 3이고, 바이러스를 아래와 같이 활성 상태로 변경한 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 비활성 바이러스는 *, 활성 바이러스는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.

* 6 5 4 - - 2
5 6 - 3 - 0 1
4 - - 2 - 1 2
3 - 2 1 2 2 3
2 2 1 0 1 - -
1 - 2 1 2 3 4
0 - 3 2 3 4 *

시간이 최소가 되는 방법은 아래와 같고, 4초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.

0 1 2 3 - - 2
1 2 - 3 - 0 1
2 - - 2 - 1 2
3 - 2 1 2 2 3
3 2 1 0 1 - -
4 - 2 1 2 3 4
* - 3 2 3 4 *

연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

입력

첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

출력

연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.

구현

#include 
#include 
#include 

using namespace std;

// map
int n, m;
int map[55][55];
int visited[55][55];

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

// combination
bool combi[11];

// bfs 
queue> q;
vector> buff;
// virus 
vector> virusXY;
// 감염 가능구역 
vector> possibleXY;
// ans 
int ans = 987654321;

void virus()
{
    fill(&visited[0][0], &visited[n][n], -1);
    for(auto &el : buff)
    {
        visited[el.first][el.second] = 0;
        q.push({el.first, el.second});
    }

    while(q.size())
    {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        for(int i=0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || nx < 0 || ny >= n || nx >= n || visited[ny][nx] != -1 || map[ny][nx] == 1)
                continue;
            if(map[ny][nx] == 0 || map[ny][nx] == 2)
            {
                visited[ny][nx] = visited[y][x] + 1;
                q.push({ny , nx});
            }
        }
    }
}

void combination(int idx, int cnt)
{   // 모든 활성 바이러스를 쓴다면 
    if(cnt == m)
    {
        bool flag = 1;
        int MAX = 0;
        virus();
        for(auto &el : possibleXY)
        {
            int ff = el.first;
            int ss = el.second;

            if(visited[ff][ss] == -1)
            {
                flag = 0;
                break;
            }
            else
                MAX = max(MAX, visited[ff][ss]);
        }
        if(flag)
            ans = min(MAX, ans);

        return;
    }

    for(int i=idx; i < virusXY.size(); i++)
    {
        int ff = virusXY[i].first;
        int ss = virusXY[i].second;
        if(combi[i])
            continue;
        else
        {
            combi[i] = 1;
            buff.push_back({ff, ss});
            combination(i, cnt+1);
            buff.pop_back();
            combi[i] = 0;
        }
    }
}

// 비활성 바이러스 : 바이러스에 감염은 되었지만, 전염은 활성화가 되어야 한다. 
int main()
{
    cin >> n >> m;
    for(int i=0; i < n; i++)
        for(int j=0; j < n; j++)
        {
            cin >> map[i][j];
            if(map[i][j] == 2)
                virusXY.push_back({i, j});
            if(map[i][j] == 0)
                possibleXY.push_back({i, j});
        }

    combination(0, 0);

    if(ans == 987654321)
        cout << -1 << endl;
    else
        cout << ans << endl;
    return 0;
}

SOL

문제를 풀기 전 경우의 수를 생각해 보아야 한다.

만약 맵이 아래와 같이 이루어져 있다면,

7 3
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2

비활성 바이러스는 총 5개 그리고 활성화 할 수 있는 바이러스의 개수는 3개라면 5Combination2 즉 10개의 경우가 있다는 것을 알 수 있다.

따라서 코드를 통해 Combination을 구현 한다.

void combination(int idx, int cnt)
{   // 모든 활성 바이러스를 쓴다면 
    if(cnt == m)
    {
        bool flag = 1;
        int MAX = 0;
        virus();
        for(auto &el : possibleXY)
        {
            int ff = el.first;
            int ss = el.second;

            if(visited[ff][ss] == -1)
            {
                flag = 0;
                break;
            }
            else
                MAX = max(MAX, visited[ff][ss]);
        }
        if(flag)
            ans = min(MAX, ans);

        return;
    }

    for(int i=idx; i < virusXY.size(); i++)
    {
        int ff = virusXY[i].first;
        int ss = virusXY[i].second;
        if(combi[i])
            continue;
        else
        {
            combi[i] = 1;
            buff.push_back({ff, ss});
            combination(i, cnt+1);
            buff.pop_back();
            combi[i] = 0;
        }
    }
}

다시한번 총 정리를 해보자면

combination 함수를 통해 시간복잡도를 보완
비활성 바이러스, 감염이 될 수 있는 공간을 따로 추출하여 비교

Reference & 다른 PS 모음집

BOJ - 17141 - 연구소 2

Sat, 08 Oct 2022 06:33:44 GMT

BOJ - 17141 - 연구소 2

문제

17141번: 연구소 2

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 빈 칸은 바이러스를 놓을 수 있는 칸이다. 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2

M = 3이고, 바이러스를 아래와 같이 놓은 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 바이러스를 놓은 위치는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.

6 6 5 4 - - 2
5 6 - 3 - 0 1
4 - - 2 - 1 2
3 - 2 1 2 2 3
2 2 1 0 1 - -
1 - 2 1 2 3 4
0 - 3 2 3 4 5

시간이 최소가 되는 방법은 아래와 같고, 5초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.

0 1 2 3 - - 2
1 2 - 3 - 0 1
2 - - 2 - 1 2
3 - 2 1 2 2 3
3 2 1 0 1 - -
4 - 2 1 2 3 4
5 - 3 2 3 4 5

연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

입력

첫째 줄에 연구소의 크기 N(5 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

출력

구현

#include 
#include 
#include 

using namespace std;

// map
int n, m;
int map[55][55];
int visited[55][55];
bool combi[55];
// joy 
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};

// ans
int ans = 987654321;

// virus

vector> buff;

vector> VirusPos;
vector> check;

void virus()
{
    fill(&visited[0][0], &visited[n][n], 0);
    queue> q;
    for(int i=0; i < buff.size(); i++)
    {
        q.push({buff[i].first, buff[i].second});
        visited[buff[i].first][buff[i].second] = 1;
    }
    while(q.size())
    {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        for(int i=0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || nx < 0 || ny >= n || nx >= n || map[ny][nx] == 1)
                continue;
            // 방문하지 않았고, 감염 가능한 경우 
            if(!visited[ny][nx])
            {
                visited[ny][nx] = visited[y][x] + 1;
                q.push({ny, nx});
            }
        }
    }
    return;
}

// virus add 
void virusadd(int idx, int cnt)
{   // 바이러스를 다 써버리면 
    if(cnt == m)
    {
        virus();
        bool flag = 0;
        int tmp = 0;
        for(auto &el : check)
        {
            int ff = el.first;
            int ss = el.second;
            if(visited[ff][ss] == 0)
            {
                flag = 1;
                break;
            }
            else
                tmp = max(visited[ff][ss], tmp);
        }
        if(!flag)
            ans = min(ans, tmp);
        // cout << " ---- " << endl;
        // for(int i=0; i < n; i++)
        // {
        //     for(int j=0; j < n; j++)
        //         cout << visited[i][j] << " ";
        //     cout << endl;
        // }
        // cout << ans << endl;
        return;
    }
    for(int i=idx; i < VirusPos.size(); i++)
    {
        if(combi[i])
            continue;
        else
        {
            combi[i] = 1;
            buff.push_back({VirusPos[i].first, VirusPos[i].second});
            virusadd(i, cnt+1);
            buff.pop_back();
            combi[i] = 0;
        }
    }
}

int main()
{
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
    cin >> n >> m;
    for(int i=0; i < n; i++)
        for(int j=0; j < n; j++)
        {
            cin >> map[i][j];
            if(map[i][j] == 2)
                VirusPos.push_back({i, j});
            if(map[i][j] == 0 || map[i][j] == 2)
                check.push_back({i, j});
        }
    virusadd(0, 0);
    if(ans == 987654321)
        cout << -1 << '\n';
    else
        cout << ans-1 << '\n';
    return 0;
}

SOL

문제를 풀기 전 경우의 수를 생각해 보아야 한다.

만약 맵이 아래와 같이 이루어져 있다면,

7 3
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2

바이러스를 심을 수 있는 공간은 총 5개 그리고 심을 수 있는 바이러스이 개수는 3개라고 할 수 있는데 이를 통해 우린 5Combination2 즉 10개의 경우가 있다는 것을 알 수 있다.

따라서 코드를 통해 Combination을 구현 하여 해결 하였다.

 void virusadd(int idx, int cnt)
{   // 바이러스를 다 써버리면 
    if(cnt == m)
    {
        virus();
        bool flag = 0;
        int tmp = 0;
        for(auto &el : check)
        {
            int ff = el.first;
            int ss = el.second;
            if(visited[ff][ss] == 0)
            {
                flag = 1;
                break;
            }
            else
                tmp = max(visited[ff][ss], tmp);
        }
        if(!flag)
            ans = min(ans, tmp);
        return;
    }
    for(int i=idx; i < VirusPos.size(); i++)
    {
        if(combi[i])
            continue;
        else
        {
            combi[i] = 1;
            buff.push_back({VirusPos[i].first, VirusPos[i].second});
            virusadd(i, cnt+1);
            buff.pop_back();
            combi[i] = 0;
        }
    }
}

Reference & 다른 PS 모음집

BOJ - 4963 - 섬의 개수

Wed, 05 Oct 2022 04:07:40 GMT

BOJ - 4963 - 섬의 개수

문제

4963번: 섬의 개수

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

구현

#include 
#include 

using namespace std;

// map
int n, m;
int map[55][55];
bool visited[55][55];
// joy 대각선 
int dy[] = {-1, 0, 1, 0, -1, -1, 1, 1};
int dx[] = {0, 1, 0, -1, 1, -1, -1, 1};

// ans 
int ans;

void dfs(int y, int x)
{
    visited[y][x] = 1;
    for(int i=0; i < 8; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 || nx < 0 || ny >= n || nx >= m)
            continue;
        if(!visited[ny][nx] && map[ny][nx])
            dfs(ny, nx);

    }
    return;
}

int main()
{
    while(1)
    {
        cin >> m >> n;
        if(!n && !m)
            break;
        else
        {
            ans = 0;
            for(int i=0; i < n; i++)
                for(int j=0; j < m; j++)
                    cin >> map[i][j];

            for(int i=0; i < n; i++)
                for(int j=0; j < m; j++)
                    if(!visited[i][j] && map[i][j])
                    {
                        ans++;
                        dfs(i, j);
                    }
            cout << ans << endl;
            fill(&visited[0][0], &visited[n][m], 0);
            fill(&map[0][0], &map[n][m], 0);
        }
    }
    return 0;
}

SOL

dfs로 풀 수 있는 문제로 기존과 다르게 대각선 방향의 dy, dx를 추가하면 된다.

Reference & 다른 PS 모음집

BOJ - 14620 - 꽃길

Tue, 04 Oct 2022 07:36:49 GMT

BOJ - 14620 - 꽃길

문제

14620번: 꽃길

문제

2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다.

진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다.

하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다.

꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수 있다. 꽃의 씨앗은 그림 (a)처럼 심어지며 1년 후 꽃이 피면 그림 (b)모양이 된다.

꽃을 심을 때는 주의할 점이있다. 어떤 씨앗이 꽃이 핀 뒤 다른 꽃잎(혹은 꽃술)과 닿게 될 경우 두 꽃 모두 죽어버린다. 또 화단 밖으로 꽃잎이 나가게 된다면 그 꽃은 죽어버리고 만다.

그림(c)는 세 꽃이 정상적으로 핀 모양이고 그림(d)는 두 꽃이 죽어버린 모양이다.

하이테크 앞 화단의 대여 가격은 격자의 한 점마다 다르기 때문에 진아는 서로 다른 세 씨앗을 모두 꽃이 피게하면서 가장 싼 가격에 화단을 대여하고 싶다.

단 화단을 대여할 때는 꽃잎이 핀 모양을 기준으로 대여를 해야하므로 꽃 하나당 5평의 땅을 대여해야만 한다.

돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자!

입력

입력의 첫째 줄에 화단의 한 변의 길이 N(6≤N≤10)이 들어온다.

이후 N개의 줄에 N개씩 화단의 지점당 가격(0≤G≤200)이 주어진다.

출력

꽃을 심기 위한 최소 비용을 출력한다.

구현

#include 

using namespace std;

// map
int map[11][11];
bool visited[11][11];
int n;

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

// ans
int cnt;
int ans = 999999999;
// check 
bool check(int y, int x)
{
    if(visited[y][x])
        return 0;
    for(int i=0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 || ny >= n || nx < 0 || nx >= n)
            return 0;
        if(visited[ny][nx])
            return 0;
    }
    return 1;
}

// seed 
int seed(int y, int x)
{
    visited[y][x] = 1;
    int tmp = map[y][x];
    for(int i=0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        visited[ny][nx] = 1;
        tmp += map[ny][nx];
    }
    return tmp;
}

void delseed(int y, int x)
{
    visited[y][x] = 0;
    for(int i=0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        visited[ny][nx] = 0;
    }
}
void solution(int cnt, int money)
{
    if(cnt == 3)
    {
        ans = min(money, ans);
        return;
    }
    for(int i=0; i < n; i++)
        for(int j=0; j < n; j++)
        {
            if(check(i, j))
            {
                solution(cnt+1, money + seed(i, j));
                delseed(i, j);
            }
        }
}

int main()
{
    cin >> n; 
    for(int i=0; i < n; i++)
        for(int j=0; j < n; j++)
            cin >> map[i][j];

    solution(0, 0);
    cout << ans << endl;

    return 0;
}

SOL

꽃을 심을 수 있는지 판단하고

심을 수 있다면
씨앗을 심고, 최솟 값을 구한 뒤

아님말고를 시전한다. (심었던 씨앗을 다시 뽑는다. )


  for(int i=0; i < n; i++)
    for(int j=0; j < n; j++)
    {
        if(check(i, j))
        {
            solution(cnt+1, money + seed(i, j));
            delseed(i, j);
        }
    }

Reference & 다른 PS 모음집