JArchive 프로그래밍 일기

문제

토마토 백준 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;    
}

문제

퇴사 백준 14501번

리뷰

완전 탐색으로 풀었다.

오늘 상담을 한다/안한다를 구분해서 재귀를 두 번 호출한다.

advice(day + T[day], sum + P[day]); // 오늘 상담한다  

advice(day + 1, sum);  // 오늘 상담 안하고 다음날로 지나간다  

코드

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

// 퇴사  

int N;
int T[16];
int P[16]; 
int max_sum;

void advice(int day, int sum){

    if(N == day){ // 종료 
        max_sum = max(max_sum, sum);
        return;
    }

    if(N < day){ // 제한 날짜 초과  
        return;
    }

    advice(day + T[day], sum + P[day]); // 오늘 상담한다  
    advice(day + 1, sum);  // 오늘 상담 안하고 다음날로 지나간다  
}

int main(void){

    freopen("input.txt", "rt", stdin);

    cin >> N;

     for(int i = 0; i < N; i++){
         scanf("%d %d", &T[i], &P[i]);
    }  // 입력받기 끝  

    advice(0, 0);

    cout << max_sum;

    return 0;    
}

문제

차이를 최대로 백준 10819번

리뷰

do while 문을 이용해서 next_permutation 함수가 false를 반환하기 전까지 계속 출력시킨다.

abs 함수를 검색해보면서 새로운 걸 배웠다.

#include <cstdlib>
int abs(int a)

#include <cmath>
double abs(double a)

int 형의 절대값 함수는 cstdlib 에 있고,

double, float 형의 절대값 함수는 cmath에 있다.

참고로 C언어 에서 int형 절대값 함수는 stdlib.h 에 속하고 double형 절대값 함수 abs는 math.h 에 있다.

#include <stdlib.h>
int abs(int a)

#include <math.h>
double fabs(double a)

next_permutation() 함수

혼자 푸는데 자꾸 틀려서 다른 분들 코드를 봤는데, 순열함수 전에 sort() 를 한 것이 내 코드와의 차이였다.

#include <algorithm>

bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

이 함수는 주어진 수열의 다음순열이 없으면 false 를 반환해준다.

'다음' 순열의 기준은 현재 순열보다 내림차순된 순열이 있느냐/없느냐다.

예를 들어, 1234 의 다음 순열은 1243

1234 -> 1243 -> 1324 -> 1342 ... -> 4321 이처럼 첫 수열은 오름차순이고 맨 마지막 수열은 내림차순임을 이용하여 구현된 함수다.

따라서 처음에 next_permutation 에 4321 을 넣고 실행하면, 이미 전부 내림차순이므로( == 다음순열이 없다고 판단) false 반환하고 종료한다.

cplusplus.com 의 next_permutation 예시는 아래와 같다.

// next_permutation example
#include <iostream>     // std::cout
#include <algorithm>    // std::next_permutation, std::sort

int main () {
  int myints[] = {1,2,3};

  std::sort (myints,myints+3);

  std::cout << "The 3! possible permutations with 3 elements:\n";
  do {
    std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
  } while ( std::next_permutation(myints,myints+3) );

  std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';

  return 0;
}

// output 
The 3! possible permutations with 3 elements:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
After loop: 1 2 3

코드

#include <iostream>
#include <cstdlib> // abs()
#include <algorithm> //  next_permutation( )
using namespace std;

// 차이를 최대로  

int N;
int a[10];

int main(void){

    int max_value = 0;

    cin >> N;

     for(int i = 0; i < N; i++){
         scanf("%d", &a[i]);
    }  // 입력받기 끝  

    sort(a, a+N); // 정렬 

     do{
         int max_tmp = 0;

         for(int i = 0; i < N-1; i++){
             max_tmp += abs(a[i]-a[i+1]);
        } 

        max_value = max(max_tmp, max_value);

    }while(next_permutation(a, a+N));

    cout << max_value;

    return 0;    
}