백트래킹을 공부하며 N과M 시리즈 중 (1) - (8) 까지 풀어보았다.

 

 

[N과 M(1)]

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

 

15649번: N과 M (1)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

#include <bits/stdc++.h>
using namespace std;
 

int n,m;
int arr[10];
bool visited[10];

void func(int k){
    if(k==m){
        for(int i=0; i<m; i++){
            cout<<arr[i]<<" ";
        }
        cout<<'\n';
        return;
    }

    for(int i=1; i<=n; i++){
        if(!visited[i]){
            arr[k] = i;
            visited[i] = 1;
            func(k+1);
            visited[i] = 0;
        }
    }
}

int main(void) {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    func(0);
    
 }

[N과 M(2)]

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

 

15650번: N과 M (2)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

#include <bits/stdc++.h>
using namespace std;
 

int n,m;
int arr[10];
bool visited[10];

void func(int k,int index){
    if(k==m){
        for(int i=0; i<m; i++){
            cout<<arr[i]<<" ";
        }
        cout<<'\n';
        return;
    }

    for(int i= index; i<n; i++){
        if(!visited[i]){
            arr[k] = i+1;
            visited[i] = 1;
            func(k+1,i+1);
            visited[i] = 0;
        }
    }
}

int main(void) {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    func(0,0);
    
 }

[N과M(3)]

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

 

15651번: N과 M (3)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

#include <bits/stdc++.h>
using namespace std;
 

int n,m;
int arr[10];
bool visited[10];

void func(int k){
    if(k==m){
        for(int i=0; i<m; i++){
            cout<<arr[i]<<" ";
        }
        cout<<'\n';
        return;
    }

    for(int i=0; i<n; i++){
        
        arr[k] = i+1;
        visited[i] = 1;
        func(k+1);
        visited[i] = 0;
        
    }
}

int main(void) {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    func(0);
    
 }

[N과M(4)]

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

 

15652번: N과 M (4)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

#include <bits/stdc++.h>
using namespace std;
 

int n,m;
int arr[10];
bool visited[10];

void func(int k,int index){
    if(k==m){
        for(int i=0; i<m; i++){
            cout<<arr[i]<<" ";
        }
        cout<<'\n';
        return;
    }

    for(int i=index; i<=n; i++){
        
        arr[k] = i;
        visited[i] = 1;
        func(k+1,i);
        visited[i] = 0;
        
    }
}

int main(void) {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    func(0,1);
    
 }

[N과M(5)]

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

 

15654번: N과 M (5)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열

www.acmicpc.net

#include <bits/stdc++.h>
using namespace std;
 

int n,m;
int arr[10];
bool visited[10];
int input[10]; 

void func(int k){
    if(k==m){
        for(int i=0; i<m; i++){
            cout<<arr[i]<<" ";
        }
        cout<<'\n';
        return;
    }

    for(int i=0; i<n; i++){
        if(!visited[i]){
            visited[i] = 1;
            arr[k] = input[i];
            func(k+1);
            visited[i] =0;
        }
        
        
    }
}

int main(void) {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(int i= 0; i<n;i++){
        cin>>input[i];
    }
    sort(input, input+n);
    func(0);
    
 }

[N과M(6)]

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

 

15655번: N과 M (6)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열

www.acmicpc.net

 

#include <bits/stdc++.h>
using namespace std;
 

int n,m;
int arr[10];
bool visited[10];
int input[10]; 

void func(int k,int index){
    if(k==m){
        for(int i=0; i<m; i++){
            cout<<arr[i]<<" ";
        }
        cout<<'\n';
        return;
    }

    for(int i=index; i<n; i++){
        if(!visited[i]){
            visited[i] = 1;
            arr[k] = input[i];
            func(k+1,i+1);
            visited[i] =0;
        }
        
        
    }
}

int main(void) {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(int i= 0; i<n;i++){
        cin>>input[i];
    }
    sort(input, input+n);
    func(0,0);
    
 }

[N과M(7)]

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

 

15656번: N과 M (7)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열

www.acmicpc.net

 

#include <bits/stdc++.h>
using namespace std;
 

int n,m;
int arr[10];
bool visited[10];
int input[10]; 

void func(int k){
    if(k==m){
        for(int i=0; i<m; i++){
            cout<<arr[i]<<" ";
        }
        cout<<'\n';
        return;
    }

    for(int i=0; i<n; i++){
        
        arr[k] = input[i];
        func(k+1);
            
        
        
    }
}

int main(void) {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(int i= 0; i<n;i++){
        cin>>input[i];
    }
    sort(input, input+n);
    func(0);
    
 }

[N과M(8)]

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

 

15657번: N과 M (8)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열

www.acmicpc.net

 

#include <bits/stdc++.h>
using namespace std;
 

int n,m;
int arr[10];
bool visited[10];
int input[10]; 

void func(int k,int index){
    if(k==m){
        for(int i=0; i<m; i++){
            cout<<arr[i]<<" ";
        }
        cout<<'\n';
        return;
    }

    for(int i=index; i<n; i++){
        
        arr[k] = input[i];
        func(k+1,i);
            
        
        
    }
}

int main(void) {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(int i= 0; i<n;i++){
        cin>>input[i];
    }
    sort(input, input+n);
    func(0,0);
    
 }

'Algorithm > BOJ' 카테고리의 다른 글

[c++] 백준 10814 나이순 정렬  (0) 2021.01.03
[c++] 백준 6603 로또 + 풀이추가(2021.03.04)  (0) 2020.12.31
[c++] 백준 7569 토마토 (3차원)  (0) 2020.12.28
[c++] 백준 7576 토마토  (0) 2020.12.28
[c++] 백준 2667 단지번호 붙이기  (0) 2020.12.27

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

 

7569번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100,

www.acmicpc.net

BFS 이용하여 구현 

3차원 배열로 구성되어 있는 것 외에는 7576번 토마토 문제 코드와 유사하게 구현

#include <bits/stdc++.h>
using namespace std;
 
int board[101][101][101];
int dist[101][101][101];

int h,n,m;
int dx[6] = {1,-1,0,0,0,0};
int dy[6] ={0,0,1,-1,0,0};
int dz[6] = {0,0,0,0,1,-1};

struct Que
{
    int x;
    int y;
    int z;
    /* data */
};


int main(void) {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cin>>m>>n>>h;
    queue<Que> Q;
    for(int i = 0; i<h; i++){
        for(int j=0; j<n; j++){
            for(int k=0; k<m; k++){
                cin>>board[i][j][k];

                if(board[i][j][k]== 1){
                    Q.push({i,j,k});
                }
                if(board[i][j][k]==0){
                    dist[i][j][k] = -1;
                }
            } 
        }
    }
    while(!Q.empty()){
        auto cur = Q.front();
        Q.pop();

        for(int i=0; i<6; i++){
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            int nz = cur.z + dz[i];

            if( nx <0|| nx>= h || ny <0 || ny>=n || nz <0 || nz>=m) continue;
            if( dist[nx][ny][nz] >=0 ) continue;
            dist[nx][ny][nz] = dist[cur.x][cur.y][cur.z] +1;
            Q.push({nx,ny,nz});
        }
    }

    int ans =0;
    for(int i=0; i<h; i++){
        for(int j=0; j<n; j++){
            for(int k =0; k<m; k++){
                if(dist[i][j][k]== -1){
                    cout<< -1;
                    return 0;
                }
            
                ans = max(ans,dist[i][j][k]);
            }
        }
    }
    cout<<ans;

 }

 

'Algorithm > BOJ' 카테고리의 다른 글

[c++] 백준 6603 로또 + 풀이추가(2021.03.04)  (0) 2020.12.31
[c++] 백준 15649 - 15657 N과M (1) - (8)  (0) 2020.12.31
[c++] 백준 7576 토마토  (0) 2020.12.28
[c++] 백준 2667 단지번호 붙이기  (0) 2020.12.27
[c++] 백준 10026번 적록색약  (0) 2020.12.27

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

 

7576번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토

www.acmicpc.net

 

BFS 사용 2차원 배열 탐색 

#include <bits/stdc++.h>
using namespace std;
 
int board[1002][1002];
int dist[1002][1002];
int dx[4] ={1,0,-1,0};
int dy[4] = {0,1,0,-1};
int n,m;

int main(void) {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cin>>m>>n;
    
    queue<pair<int, int>> Q;

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

            if(board[i][j]==1){
                Q.push({i,j});
            }
            if(board[i][j]==0){
                dist[i][j] = -1;
            }
        }
    }
    while(!Q.empty()){
        auto cur = Q.front();
        Q.pop();
        for( int i =0; i<4; i++){
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            if( nx<0 || nx >=n || ny <0 || ny>= m) continue;
            if(dist[nx][ny] >=0 ) continue;
            dist[nx][ny] = dist[cur.first][cur.second]+1;
            Q.push({nx,ny});

        }
    }
    int ans = 0;
    for(int i=0; i<n; i++){
        for( int j=0; j<m; j++){
            if(dist[i][j]==-1){
                cout<< -1;
                return 0;
            }
            ans = max(ans, dist[i][j]);
        }
    }
    
    cout<<ans;
}

'Algorithm > BOJ' 카테고리의 다른 글

[c++] 백준 6603 로또 + 풀이추가(2021.03.04)  (0) 2020.12.31
[c++] 백준 15649 - 15657 N과M (1) - (8)  (0) 2020.12.31
[c++] 백준 7569 토마토 (3차원)  (0) 2020.12.28
[c++] 백준 2667 단지번호 붙이기  (0) 2020.12.27
[c++] 백준 10026번 적록색약  (0) 2020.12.27

BFS 사용

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

 

2667번: 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여

www.acmicpc.net

 

 

#include <bits/stdc++.h>
using namespace std;
 

string board[25];
int dist[25][25];
int n;
int dx[4] ={1,0,-1,0};
int dy[4] ={0,1,0,-1};


int main(void) {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    queue<pair<int,int>> Q;
    vector<int> V;
    cin>>n;
    int count =0;
    int area =0;
    for(int i=0; i<n; i++){
        cin>>board[i];
     }

    for(int i=0 ; i<n; i++){
        for(int j=0; j<n; j++){
            if(board[i][j]=='1' && dist[i][j]==0){
                count++;
                dist[i][j] = 1;
                Q.push({i,j});

                while(!Q.empty()){
                    area++;
                    auto cur = Q.front();
                    Q.pop();
                    for(int i=0; i<4; i++){
                        int nx = cur.first +dx[i];
                        int ny = cur.second+dy[i];

                        if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
                        if(dist[nx][ny]==1 || board[nx][ny] == '0') continue;

                        dist[nx][ny] = 1;
                        Q.push({nx,ny});
                    }
                }
            }
            if(area!=0){
                V.push_back(area);
                area =0;
            }
        }
    }
    cout<<count<<"\n";
    sort(V.begin(), V.end());
    for(int i=0; i<V.size(); i++)
        cout<<V[i]<<"\n";
    
    
}

'Algorithm > BOJ' 카테고리의 다른 글

[c++] 백준 6603 로또 + 풀이추가(2021.03.04)  (0) 2020.12.31
[c++] 백준 15649 - 15657 N과M (1) - (8)  (0) 2020.12.31
[c++] 백준 7569 토마토 (3차원)  (0) 2020.12.28
[c++] 백준 7576 토마토  (0) 2020.12.28
[c++] 백준 10026번 적록색약  (0) 2020.12.27

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

 

 

10026번: 적록색약

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)

www.acmicpc.net

 

BFS 사용

#include <bits/stdc++.h>
using namespace std;
 

string board[101];

int dist1[101][101];
int dist2[101][101];
int n;
int dx[4] ={1,0,-1,0};
int dy[4] ={0,1,0,-1};


int main(void) {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cin>>n;
    
    int count =0;
    
    queue<pair<int,int>> Q1;
    queue<pair<int,int>> Q2;
    vector<int> v;
    for(int i=0; i<n; i++){
        cin>>board[i];
    }
    for(int i=0; i<n; i++){
        fill(dist1[i], dist1[i]+n, -1);
        fill(dist2[i], dist2[i]+n, -1);
    }

    for(int i=0 ; i<n; i++){
        for(int j=0; j<n; j++){
            if(dist1[i][j]== -1){
                count++;
                Q1.push({i,j});
                dist1[i][j] = 0;

                while(!Q1.empty()){
                    auto cur = Q1.front();
                    Q1.pop();

                    for(int i=0; i<4; i++){
                        int nx = cur.first + dx[i];
                        int ny = cur.second +dy[i];

                        if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
                        if(dist1[nx][ny]==-1 && board[nx][ny]==board[cur.first][cur.second]) {
                            Q1.push({nx,ny});
                            dist1[nx][ny] =0;
                        }
                    }
                }
            }
            
        }
 
    }
    cout<<count<<" ";


    count = 0;

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(dist2[i][j]==-1){
                count++;
                Q2.push({i,j});
                dist2[i][j] =0;

                while(!Q2.empty()){
                    auto cur = Q2.front();
                    Q2.pop();

                    for(int i=0; i<4; i++){
                        int nx = cur.first + dx[i];
                        int ny = cur.second +dy[i];

                        if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
                        if(board[cur.first][cur.second]=='R' || board[cur.first][cur.second]=='G'){
                            if(dist2[nx][ny]==-1 && (board[nx][ny]=='R' || board[nx][ny]=='G')){
                                dist2[nx][ny] =0;
                                Q2.push({nx,ny});
                            }
                        }
                        else{
                            if(dist2[nx][ny]== -1 && board[nx][ny]== board[cur.first][cur.second]){
                                dist2[nx][ny] =0;
                                Q2.push({nx,ny});
                            }
                        }
                        

                        }
                    }
                }
            }
        }

 
   cout<<count;
}

'Algorithm > BOJ' 카테고리의 다른 글

[c++] 백준 6603 로또 + 풀이추가(2021.03.04)  (0) 2020.12.31
[c++] 백준 15649 - 15657 N과M (1) - (8)  (0) 2020.12.31
[c++] 백준 7569 토마토 (3차원)  (0) 2020.12.28
[c++] 백준 7576 토마토  (0) 2020.12.28
[c++] 백준 2667 단지번호 붙이기  (0) 2020.12.27

+ Recent posts

티스토리툴바