JArchive 프로그래밍 일기

문제

단지 번호 붙이기 백준 2667번

리뷰

오늘의 교훈. 문제를 정독하자. 조급해지면 지는건데...

마지막에 단지 마다의 집 개수를 sort 해서 출력하라는 것을 빼먹고 왜틀렸나 헤맸다 ㅠㅠ

그리고 처음에 시작점을 큐에 푸시할 때도 A와 D 배열을 갱신해줘야 한다.
A에는 방문했으니까 0, D에는 단지 숫자를 써줘야 한다.

배열 A는 주어진 배열이고,

배열 D는 단지를 채운 결과를 저장할 배열이다.

main 함수에서는 배열 A를 순회해서 1을 만나면 BFS 탐색을 시작한다.

BFS는 A배열이 1이고, D배열이 0 인 경우에 house 개수를 센다. 단지의 집이 몇개인지 세는것이다.

if(in_boundary(xx, yy)){

     if(A[xx][yy] == 1 && D[xx][yy] == 0){
         A[xx][yy] = 0; // 방문표시  
         D[xx][yy] = danzi; // 단지표시 
         q.push({xx, yy});
         house_num++;
     }
}

A배열에서 방문한 곳은 다시 방문 안하도록 0 으로 변경한다.

D배열에는 단지 번호를 써준다.

BFS가 끝나면 house 개수를 리턴한다.

상하좌우가 A배열 인덱스 범위 안에 있는지는 in_boundary함수를 이용해서 true/false 확인해줬다.

int dx[5] = {-1, 1, 0, 0}; // 상하좌우 
int dy[5] = {0, 0, -1, 1};  

bool in_boundary(int x, int y){
    return (x >= 0 && x < N && y >= 0 && y < N) ? 1:0;
}

마지막에 단지의 집 개수를 오름차순으로 정렬하여 출력한다.

    // 답 출력  
    cout << danzi << '\n'; // 단지의 총 개수 

    sort(house.begin(), house.end());  // 오름차순 정렬해서 출력 !

    for(int i =0 ; i<house.size(); i++){
        cout << house[i] << '\n'; // 출력 
    }

코드

#include <iostream> 
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int N;
int A[27][27]; 
int D[27][27];

int dx[5] = {-1, 1, 0, 0}; // 상하좌우 
int dy[5] = {0, 0, -1, 1};  

 // 단지번호붙이기  2667 

bool in_boundary(int x, int y){
    return (x >= 0 && x < N && y >= 0 && y < N) ? 1:0;
}

int BFS(int i, int j, int danzi){

    queue<pair<int,int> > q;
    int house_num = 1;

    q.push({i, j});
    A[i][j] = 0;
    D[i][j] = danzi;

    while(!q.empty()){

        pair<int,int> now = q.front();
        int x = now.first;
        int y = now.second;
        q.pop();

        for(int i = 0; i < 4; i++ ){ // 상하좌우 탐색 
             int xx = x + dx[i];
             int yy = y + dy[i];

             if(in_boundary(xx, yy)){

                 if(A[xx][yy] == 1 && D[xx][yy] == 0){
                     A[xx][yy] = 0; // 방문표시  
                     D[xx][yy] = danzi; // 단지표시 
                     q.push({xx, yy});
                     house_num++;
                }
            }
        }
    }

    return house_num;
} 

int main(void){

    cin >> N;

    int danzi = 0;
    vector<int> house;

    for(int i = 0; i < N; i++){

        string st; 
        cin >> st;

        for(int j = 0; j < N; j++){
            A[i][j] = st[j] - 48;
        }
    } // 입력받기 끝  

    // 탐색 시작  
     for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(A[i][j] == 1) {
                int house_num = BFS(i, j, ++danzi); 
                house.push_back(house_num);
            }
        }
    }

    // 답 출력  
    cout << danzi << '\n';

    sort(house.begin(), house.end());  // 오름차순 정렬해서 출력 !!

    for(int i =0 ; i<house.size(); i++){
        cout << house[i] << '\n';
    }

    return 0;    
}

문제

미로 탐색 백준 2178번

리뷰

오늘의 교훈. 문제를 정독하자..!!!

미로의 시작은 (0, 0) 끝은 (N-1, M-1) 로 정해져있다.

최단 경로를 구하는 거니까 BFS로 탐색했다.

토마토 문제와 비슷하게, 현재칸에 숫자를 저장할 때 큐에서 꺼낸 숫자 + 1을 해줬다.

        for(int i = 0; i < 4; i++){ // 상하좌우 살핀다 

            int xx = x + dx[i];
            int yy = y + dy[i];

            if(A[xx][yy] == 1 && boundary(xx, yy)){ // 범위 내에 있고, 이동가능한 1이라면. 
                q.push(make_pair(xx, yy));
                A[xx][yy] = A[x][y] + 1;  // 큐에서 꺼낸 칸 숫자 + 1
            }
        }

상하좌우가 N, M 행렬 인덱스 범위 안에 있는지는 boundary 함수를 이용해서 true/false 확인해줬다.

int N, M;  // 행, 열  

// 상하좌우 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1}; 


bool boundary(int i, int j){
    return (i >= 0 && i < N && j >=0 && j < M) ? 1:0;
}

코드

#include <iostream> 
#include <queue>
#define MAX 101
using namespace std;

int N, M;  // 행, 열  
int A[MAX][MAX];

// 상하좌우 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1}; 


bool boundary(int i, int j){
    return (i >= 0 && i < N && j >=0 && j < M) ? 1:0;
}

void BFS(){

    queue<pair<int,int> > q;

    q.push(make_pair(0, 0));

    while(!q.empty()){

        pair<int,int> now = q.front();
        q.pop();

        int x = now.first; // 큐에서 꺼낸 칸의 좌표 (행x 열y)
        int y = now.second;

        for(int i = 0; i < 4; i++){ // 상하좌우 살핀다 

            int xx = x + dx[i];
            int yy = y + dy[i];

            if(A[xx][yy] == 1 && boundary(xx, yy)){ // 범위 내에 있고, 이동가능한 1이라면. 
                q.push(make_pair(xx, yy));
                A[xx][yy] = A[x][y] + 1;  // 큐에서 꺼낸 칸 숫자 + 1
            }
        }
    }

    cout << A[N-1][M-1];
}  

int main(void){

    cin >> N >> M ; // 행, 열  

     for(int i = 0 ; i < N; i++){

         char ch[MAX];
         scanf("%s", &ch);

         for(int j = 0; j < M; j++){
             A[i][j] = ch[j]-48;  
        } 
    }  

    BFS();

    return 0;    
}

문제

토마토 백준 7576번

리뷰

토마토가 최소 몇 일이 지나야 다 익을 수 있는지 출력하는 문제다.

익은 토마토가 1개로 시작하는 줄 착각하고서 헤맸다. 진짜... 문제를 정독해야겠다.

시작점이 반드시 하나라고 생각해서 1시간 동안 붙잡고있었는데 계속 틀렸다.

시작점을 큐에 push 하고 시작하고나서야 맞출 수 있었다.

처음에 토마토 값들을 (0 , -1, 1 ) 입력받을 때, 1이면 이미 익은 것이니까 이 지점들을 시작으로 상하좌우가 익어간다.

그래서 큐에 BFS 시작점으로써 넣어준다.

boundary 함수는 M * N 상자 범위를 벗어나는지 여부를 1 / 0 으로 알려준다.

큐에서 하나씩 꺼내서 상하좌우를 살피는데, 범위 안에 있고 아직 안익었다면( 0이라면 ) ripe 익혔다고 세준다.

그리고 만약 day 가 증가됬다면 갱신해준다.

day를 그냥 출력하면 맞출 줄 알았는데, 처음에 시작점은 이미 값을 1로 갖고 있으니까, 하루가 지나도 2가 되버린다.

M * N 크기의 A 배열이 어떻게 변해가는지 출력해보면서 발견했다.

그래서 마지막에 day - 1 을 해준다.

코드

#include <iostream> 
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 1000+1 

using namespace std;

int M, N; // 가로, 세로 
int A[MAX][MAX];
int zero_cnt, ripe, day;

queue<pair<int,int> > q;

// 상 하 좌 우
int diff_x[4] = {-1, 1, 0, 0};  // N  
int diff_y[4] = {0, 0, -1, 1};  // M


bool boundary(int x, int y){ // M * N 범위 초과 하는지 확인 
    bool res = (x < N && x >= 0 && y < M && y >= 0) ? 1 : 0;
    return res;
}

void BFS(){

    while(!q.empty()){

        pair<int,int> now = q.front();
        q.pop();

        for(int i = 0; i < 4; i ++){ // 상하좌우 확인 

            int x = now.first + diff_x[i];
            int y = now.second + diff_y[i];

            if(boundary(x, y) && A[x][y] == 0){ // 범위 안에 있고, 안 익었으면. 
                A[x][y] = A[now.first][now.second] + 1; 
                q.push(make_pair(x, y));
                ripe++; // 익은 개수 
                day = max(A[x][y], day); // day 증가됬다면 갱신 
            }
        }

    }

    if(zero_cnt > ripe) { // 모두 익지 못한다. 
        cout << -1; 
    }else{
        cout << day-1;
    }

}

int main(void){

    cin >> M >> N; // 가로, 세로  

    for(int i = 0; i < N; i++){ // 세로 N

        for(int j = 0; j < M; j++){ // 가로 M 

            scanf("%d", &A[i][j]);
            if(A[i][j] == 0) zero_cnt++; // 안익은 토마토 개수 센다  
            else if(A[i][j] == 1) {
                q.push(make_pair(i, j)); // 가능한 시작점 모두 넣는다  
            }
        } 
    } // 입력받기 끝

    if(zero_cnt == 0) cout << 0; // 저장될 때부터 모든 토마토가 익어있는 상태
    else{ // 탐색시작 
        BFS(); 
    }

    return 0;    
}

문제

이분 그래프 백준 1707번

리뷰

이분 그래프는 정점이 전부 RED, BLUE 2가지 색상으로만 구성됬다고 했을 때, 인접 정점 끼리는 다른 색깔을 가지는 그래프다.

이분 그래프가 뭔지 헷갈려서 여러 포스팅을 찾아봤다.

참고. DFS로 이분그래프를 구현한 코드

코드는 BFS로 짰고, 시작정점 색을 RED로 시작했다.

시작정점의 인접한 정점들은 전부 BLUE로 칠한다. (시작정점이 BLUE라면, 인접한 것들은 RED로.)

BFS 탐색으로 모든 정점색을 정해주고나면, is_bipartite 함수로 이분 그래프인지 판단한다.

기준은 특정 정점을 기준으로 인접한 정점들이 전부 다른 색을 갖는지 확인한다.

즉, i 를 정점이 RED라면, i의 인접 정점들은 전부 BLUE 여야만 한다.

그게 아니라면, 이분그래프의 조건을 만족하지 않는다.

연결 그래프가 아닐 수 있으므로 BFS탐색은 모든 정점을 시작점으로 해서 확인해야 한다.

코드

#include <iostream> 
#include <vector>
#include <queue>
#include <cstring> // memset()
#include <algorithm>
#define MAX_SIZE 20000+1
#define RED 1
#define BLUE 2
using namespace std;


int K, V, E;
vector<int> M[MAX_SIZE];
int check[MAX_SIZE]; // 미방문 0 , RED 1 , BLUE 2  

void BFS(int v){ // 시작노드와 인접한 노드들은 시작노드와 반대되는 색으로 칠한다.  

    queue<int> q;

    int color = RED; // 시작 노드 RED
    bool is_bipartite = true;

    check[v] = color;
    q.push(v);

    while(!q.empty()){

        int now = q.front();
        q.pop();

        if(check[now] == RED){  // 현재노드와 다른 색깔로 정한다
            color = BLUE;  
        }else{
            color = RED;
        }

        int adj_size = M[now].size();

        for(int i = 0; i < adj_size; i++){

            int next = M[now][i];

            if(!check[next]){ 
                check[next] = color;
                q.push(next);
            }
        }
    }

}

bool is_bipartite(){ // 이분 그래프인지 확인 

    for(int i = 1; i <= V; i++ ){ // 모든 정점 확인 

        int adj_size = M[i].size();
        for(int j = 0; j < adj_size; j++ ){
            int next = M[i][j];
            if(check[i] == check[next]){
                return 0;  // 인접 정점끼리 같은 색깔이면 이분 그래프가 아니다. 
            }
        }
    }

    return 1;
}

int main(void){

    int st, end = 0;

    cin >> K;

    while(K--){

        cin >> V >> E;

        while(E--){ // 간선         
            cin >> st >> end;
            M[st].push_back(end);
            M[end].push_back(st);
        } // 입력받기 끝  

        for(int i = 1; i <= V; i++){ // 모든 정점에서 시작해본다. 연결 그래프가 아닐수 있기 때문이다.
            if(!check[i]){ // 미방문이라면, 탐색시작 
                BFS(i);
            }
        }

        string answer = (is_bipartite()) ? "YES" : "NO";
        cout << answer << '\n';

        memset(check, 0, sizeof(check)); // 초기화  
        for(int i = 0; i <= V; i++){ // 초기화  
            M[i].clear();
        }
    }

    return 0;    
}

문제

ABCDE 백준 13023번

리뷰

N명이 캠프를 가는데, 친구관계가 ABCDE 가 존재하는지 확인하는 문제다.

N명이 모두 친구인건지 확인하는 건줄 착각하고 처음에 틀리게 풀었다.

그러니까 DFS로 풀면, depth가 4인지만 확인하면 되는 것이다.

인접리스트로 간선을 구현하고, DFS에서 노드 방문 여부를 표시하기 위해 check 배열을 만들었다.

DFS로 탐색 하되, 여기서는 0,1,2,3,4 의 depth 4 를 만족하면 바로 종료시킨다.

코드

#include <iostream> 
#include <vector>
#include <cstring> // memset()
#include <algorithm>
#define MAX 2000
using namespace std;

int N, M;
int answer = 0;
vector<int> V[MAX];
int visited[MAX+1];

void DFS(int idx, int depth){

    if(depth == 4){ //  0,1,2,3,4 로 이어진 depth 4 라면 answer 1 로 갱신 
        answer = 1;
        return;
    }

    visited[idx] = 1; // 현재 노드 방문 표시 

    for(int i = 0; i < V[idx].size(); i ++){

        int next = V[idx][i]; // 다음 노드 

        if(!visited[next]){ // 다음 노드가 안가본 노드라면, 가본다. 
            visited[next] = 1;
            DFS(next, depth+1);
            visited[next] = 0;
        }
    }
}

int main(void){

    cin >> N >> M; // 노드, 간선 개수  

     int start=0, end=0;

     for(int i = 0; i < M; i++){ // 간선 개수 만큼 입력
        cin >> start >> end;
        V[start].push_back(end);
        V[end].push_back(start); 
    } // 입력받기 끝  

    // 시작 노드를 바꿔가며 0,1,2,3,4 로 이어진 depth 있는지 확인  
    for(int i = 0; i < N; i++){

        memset(visited, 0, sizeof(visited)); // 방문 배열 초기화  
        visited[i] = 1;
        DFS(i, 0); 

        if(answer == 1) break; 
    }

     cout << answer;

    return 0;    
}

문제

연결 요소의 개수 백준 11724번

리뷰

연결 요소의 개수를 구하는 문제다.

인접리스트 형식으로 간선 정보를 입력받았다.

DFS, BFS 중에서 BFS를 선택해서 풀었다.

첫 방문이라면 answer 를 1로 만들고 BFS를 시작한다.

만약, 정점을 다르게 해서 check 배열을 확인했을 때 미방문 노드가 있다면, 다른 클러스터의 노드들이 있다는 것이다.

answer 가 1인채로 프로그램이 종료 된다면, 하나로 시작해서 모든 정점을 방문했다는 뜻이니까 모든 노드가 하나의 클러스터 안에 있다는 것이다.

코드

#include <iostream> 
#include <vector>
#include <queue>
#include <cstring> // memset()
#include <algorithm>
using namespace std;

int N, M;
int answer;
vector<int> V[1001];
int check[1001];

void BFS(int idx){

    queue<int> qu;

    check[idx] = 1; // 첫 노드부터, 방문하고 큐에 푸시  
    qu.push(idx);

    while(!qu.empty()){

        int x = qu.front();
        qu.pop();

        int togo_size =  V[x].size(); // x와 인접한 노드 개수 (==방문 확인할 노드)

        for(int i = 0; i < togo_size; i++){
            int next = V[x][i];

            if(!check[next]){ // 미방문이라면, 방문하고 큐에 푸시  
                check[next] = 1; 
                qu.push(next);
            } 
        }
    }

}

int main(void){

    cin >> N >> M; // 노드, 간선 개수  

     int st, end;

     for(int i = 0; i < M; i++){

         cin >> st >> end;    
        V[st].push_back(end);
        V[end].push_back(st);
    } // 입력받기 끝


    // 모든 정점을 시작으로 탐색  
    for(int i = 1; i <= N; i++){

         if(!check[i]){ // 첫 방문이면  
             answer++; 
             BFS(i);
        }
    } 

    cout << answer;

    return 0;    
}

문제

로또 백준 6603번

리뷰

next_permutation 으로 모든 순열을 구해서 풀었다.

k 개 중에 반드시 6개만 선택해서 가능한 순열을 전부 출력한다.

k는 최대 50이고, 주어진 k 중에 처음에는 0 으로 6개 뽑을 것을 표시하고 , 나머지들은 선택 안할거니까 1로 표시한다.

next_permutation 으로 순열을 출력하는데, 0으로 뽑힌것만 출력한다.

코드

#include <iostream> 
#include <vector>
#include <algorithm>
using namespace std;

void lotto(vector<int> &A, int N){

    int ch[50] = {0, }; 

    // 6부터 나머지는 1 
    for(int i = 6; i < N ; i++){
        ch[i] = 1;
    }

    do{

        for(int i = 0; i < N; i++){
            if(!ch[i]) cout << A[i] << ' ';
        }
        cout << '\n';
    }while(next_permutation(ch, ch+N));

    cout << '\n';

    return;
}

int main(void){

    int k = 1;
    int N = 0;
    vector<int> A;

    while(1){

        scanf("%d", &N);
        if(N == 0) break;

        for(int i = 0; i < N; i++){
            int num = 0;
            cin >> num;
            A.push_back(num);
        }

        lotto(A, N);
        A.clear();
    } 

    return 0;    
}