JArchive 프로그래밍 일기

문제

섬의개수 백준 4963번

리뷰

미로 탐색 문제와 비슷했다.

지도에서 땅은 1이고 바다는 0으로 표기되어 있다. 여기서 섬의 개수를 구한다.

이중 for문으로 모든 지점에서 BFS를 시작한다. 땅을 발견할 경우에만 BFS를 시작한다.

핵심은 땅을 발견했을 때, 그 인접한 (가로,세로,대각선) 땅은 전부 바다로 바꾸고 ( 탐색하며 발견한 1은 0으로. ) 끝내는 것이다.

그 지점의 BFS가 종료되면 섬 개수를 하나 센다. cnt + 1

설계 하고 코딩하고 디버깅 하는데 1시간 정도 걸렸다.

코드

#include <iostream> 
#include <queue>
#include <cstring> // memset()
#include <algorithm> // min(), pair STL
#define M_MAX 50
using namespace std;

int M[M_MAX+1][M_MAX+1]; //지도  
int w, h; // 너비, 높이  

// 8방향 
int dx[10] = {-1, -1, -1, 0, 0, 1, 1, 1}; 
int dy[10] = {-1, 0, 1, -1, 1, -1, 0, 1};

// 지도 범위 내에 있는지 확인
bool boundary(int i, int j){   
    return (i >= 0 && i < h && j >= 0 && j < w) ? 1:0;
} 

void BFS(int x, int y){  // 시작점 땅 기준으로 근처 땅을 전부 바다로 만든다. 

    queue<pair<int,int>> q;

    q.push({x, y}); // 시작점 푸시  
    M[x][y] = 0; // 방문 표시  

    while(!q.empty()){ // 1 땅  0바다 

        int now_x = q.front().first;
        int now_y = q.front().second;
        q.pop();

        for(int i = 0; i < 8; i++){ // 8방향 검사  

            int next_x = now_x + dx[i];
            int next_y = now_y + dy[i];

            if(boundary(next_x, next_y) ){ // 범위 내부이면  

                if(M[next_x][next_y] == 1){ // 땅이라면 

                    q.push({next_x, next_y}); // 방문한 좌표 큐에 넣기  
                    M[next_x][next_y] = 0; // 바다로 만든다  
                }
            }
        }
    }

}

int main(void){

    while(1){

        // w, h  (열, 행)
        cin >> w >> h;

        if(w==0 && h==0) break;

        // 지도 입력받기  
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                cin >> M[i][j];
            }
        } 

        int cnt = 0; // 섬의 개수  

        for(int i = 0; i < h; i++){  // 시작점 탐색 ( 땅 찾기 )
            for(int j = 0; j < w; j++){

                if(M[i][j] == 1){ // 땅 발견  
                    BFS(i, j); 
                    cnt++;
                } 

             }
        } 
        cout << cnt << '\n';    

        memset(M, 0, sizeof(M)); // M배열 초기화
    }

    return 0;    
}

문제

나이트의 이동 백준 7562번

리뷰

이동 횟수를 체스판 좌표에 저장하려고 한 방식이 실패했다.

왜냐하면 그 좌표를 지나간 경우가 하나가 아니기 때문이다.

큐에는 이동 좌표를 저장했다. 이동 횟수인 int cnt는 따로 관리했다. 범위 내부이고, 안가본 좌표라면, 체스판 해당 좌표에 cnt를 저장하려고 했다.

int M[M_MAX+1][M_MAX+1]; // 체스판  - 0이 아니면 (미방문시) cnt값을 저장

int cnt = 0; 

queue<pair<int,int>> q;    //좌표를 저장하는 큐 
M[tmpX][tmpY] = cnt;

그래서 큐에 좌표와 cnt를 함께 저장했다.

int M[M_MAX+1][M_MAX+1]; // 체스판   - 방문1 미방문0 만 구분 
int cnt = 0; 

// q : 현재 좌표{a,b}와 이동 횟수cnt 저장  
queue<pair<pair<int,int>,int>> q;    

q.push({{a, b}, cnt} ); // 현재좌표와 이동횟수 0 푸시  
M[a][b] = 1; // 현재좌표 방문표시

범위 내부이고, 안가본 좌표라면, 이동한 좌표 tmpX tmpY 이동횟수+1 을 큐에 푸시했다.

// 8 방향 확인  
for(int i = 0; i < 8; i++){ 

    int tmpX = nx + dx[i]; // 가볼 좌표  
    int tmpY = ny + dy[i];

    if(boundary(tmpX, tmpY)){ // 범위 내부이면 

        if(M[tmpX][tmpY] == 0){ // 안가봤다면 

            q.push({ {tmpX, tmpY}, cnt+1} ); // 큐에 이동한 좌표와 이동횟수+1 해서  푸시 
            M[tmpX][tmpY] = 1; //방문표시   
        }
    }
} 

큐에서 pop 했을 때의 좌표가 목적지 좌표라면, 바로 cnt를 return 하게 했다.

어려웠다. 나중에 다시 풀어봐야겠다.

코드

#include <iostream> 
#include <queue>
#include <cstring> // memset()
#include <algorithm> // min(), pair STL
#define M_MAX 300
using namespace std;


int M[M_MAX+1][M_MAX+1]; // 체스판  
int M_LIMIT; // 체스판 크기 
int a,b, x,y; // 현재좌표, 목적좌표  

// 8방향 
int dx[10] = {1, 2, 2, 1, -2, -1, -2, -1}; 
int dy[10] = {2, 1, -1, -2, 1, 2, -1, -2};


// M_LIMIT 범위 내에 있는지 확인
bool boundary(int i, int j){   
    return (i >= 0 && i < M_LIMIT && j >= 0 && j < M_LIMIT) ? 1:0;
} 

int BFS(){

    int cnt = 0;

    // q : 현재 좌표{a,b}와 이동 횟수cnt 저장  
    queue<pair<pair<int,int>,int>> q;    

    q.push({{a, b}, cnt} ); // 현재좌표와 이동횟수 0 푸시  
    M[a][b] = 1; // 현재좌표 방문표시


    while(!q.empty()){

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

        int nx = now.first.first; // 현재 좌표  
        int ny = now.first.second; 
        int cnt = now.second; // 여기까지의 이동횟수 cnt 

        // 목적지라면 종료 
        if(nx == x && ny == y){
            return cnt;
        } 

        // 8 방향 확인  
        for(int i = 0; i < 8; i++){ 

            int tmpX = nx + dx[i]; // 가볼 좌표  
            int tmpY = ny + dy[i];

            if(boundary(tmpX, tmpY)){ // 범위 내부이면 

                if(M[tmpX][tmpY] == 0){ // 안가봤다면 

                    q.push({ {tmpX, tmpY}, cnt+1} ); // 큐에 이동한 좌표와 이동횟수+1 해서  푸시 
                    M[tmpX][tmpY] = 1; //방문표시   
                }
            }
        } 
    }
}

int main(void){

     int TC = 0;
     cin >> TC;

    while(TC--){
        cin >> M_LIMIT; // 체스판 크기(범위)
        cin >> a >> b >> x >> y; // 현재좌표, 목적좌표 
        memset(M, 0, sizeof(M)); // 체스판 0초기화 

         cout << BFS() << '\n';    
     }

    return 0;    
}

문제

사탕게임 백준 3085번

리뷰

기분이 엄청 좋다.

맞는데 왜틀리지.. 맞왜틀 중얼거리다가 드디어 채점창에서 "맞았습니다!" 를 봤다.

고생한 이유는 2가지다.

첫 째, 인접한 칸을 교환 후에, 전체 행, 전체 열을 검사하지 않아서 틀렸었다.

BOJ 질문게시판 글을 보다가 쿵 했다.

오른쪽과 교환한 경우, i행, j열, j+1열 이렇게 3 줄만 검사하면 되는줄 알았었다.

하지만 그게 아니었다. 그림그려보니까 다른 행과 열들도 영향을 받았다.

둘 째, 연속한 사탕개수 cnt를 세는데, max_cnt를 갱신하는 지점이 틀렸었다.

모든 행에서 연속한 사탕개수 cnt를 센다.

여기서 이중 for문 안에서 cnt를 잘 세놓긴 했다.

그런데, cnt 가 증가한 순간마다 max_cnt로 갱신해서 기억해줬어만 한다.

그렇지 않으면( 이중 for문이 끝나고 나서 max_cnt로 갱신하는 경우에는 ) , 똑바로 이중 for문 안에서 최대 cnt를 발견해놓고서도 max_cnt가 알 리가 없다.

읽고 도움을 받은 BOJ 질문게시판 글

인접한 칸을 교환하고 나서, 왜 전체 행, 전체 열을 전부 검사해야 하나?

예시 입력, 출력

질문게시판의 질문과 코드에서 나처럼 고민한 분들의 노고가 느껴졌다.

BOJ질문게시판에 글올리시고 답글 달아주시는 분들 모두 감사드린다. 항상 도움 받고 있다 :)

코드

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

// 사탕게임 (3085)

int N;
char B[51][51];
int max_num;

void swap(int i, int j, int d_flag){ // d_flag에 따라 아래 또는 오른쪽과 교환  

    char c = B[i][j];

    if(d_flag){ // 아래와 교환  
        B[i][j] = B[i+1][j];
        B[i+1][j] = c; 

    }else { // 오른쪽과 교환  
        B[i][j] = B[i][j+1];
        B[i][j+1] = c; 
    }
}


void check(int i, int j, int d_flag){

    swap(i, j, d_flag); // 교환 

    int cnt = 1;

    // 모든 행의 가로 확인 
    for(int x = 0; x < N; x++){

        cnt = 1;
        for(int y = 0; y < N-1; y++){

              if(B[x][y] == B[x][y+1]){
                  cnt++;
                  max_num = max(max_num, cnt); // 갱신된 cnt 저장 
            }else{
                cnt = 1;
            }
        }
    }


    // 모든 열의 세로 확인 
    for(int x = 0; x < N; x++){

        cnt = 1;
        for(int y = 0; y < N-1; y++){
              if(B[y][x] == B[y+1][x]){
                  cnt++;
                  max_num = max(max_num, cnt); // 갱신된 cnt 저장 
            }else{
                cnt = 1;
            }
        }
    }

    swap(i, j, d_flag); // 제자리 돌려놓기  

} 

int main(void){

    cin >> N;

     for(int i = 0; i < N; i++){
          for(int j = 0; j < N; j++){
            cin >> B[i][j];
        }    
    } // 입력받음  

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

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

             if(j+1 < N){ // 오른쪽과 교환 가능  
                check(i, j, 0);
            }

            if(i+1 < N){ // 아래와 교환 가능 
                check(i, j, 1);
            }
        }    
    } 

    cout << max_num;    

    return 0;    
}

문제

후위표기식2 백준 1935번

리뷰

문자열을 입력받아서 char C 배열에 넣는다.

A, B, C ... 에 순서대로 대응하는 숫자값을 벡터 v에 넣는다. 여기까지가 주어진 입력받기다.

문자열 C를 순회하는데,

연산자가 나오면 스택 st에서 숫자 2개를 pop 해서 연산하고, 그 연산 결과를 푸시 한다.

숫자 (A, B, C 같은 알파벳) 이 나오면, 스택 st에 푸시한다.

C B A 순으로 입력 들어오지 않으니까, 문자 'A' 에서 65를 빼면 v 의 인덱스가 나온다.

for(int i = 0; C[i] != NULL; i++){   // 문자열 C 순회 

        if(C[i] >= 'A' && C[i] <= 'Z'){ // 숫자면, push

            // C[i]에서 'A' ASCII 65를 뺀다. v의 인덱스 나옴. -> 앒파벳에 대응하는 num  
            st.push( v[C[i]-65] ); 

        }else{ // 연산자 만나면, 숫자 2개 pop 해서 연산   

            double b = st.top(); // 연산 순서에 유의해서 먼저 pop 한 것이 b 다. 
            st.pop();
            double a = st.top();
            st.pop();
            double ans = 0.0; // a와 b의 연산 결과를 저장할 ans 변수 

            if(C[i] == '*'){
                ans = a*b; 
            } // 연산자에 대응해서 연산 
              // ... 

             st.push(ans); // 연산 결과를 푸시  
        }
    } 

답은 계산 결과를 소수점 2째자리 까지 출력하는 것을 유의한다.

코드

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

// 후위표기식2  PostfixNotation2  (지아) 

int N;
char C[101];
vector<double> v;
stack<double> st;

int main(void){

    cin >> N;

     scanf("%s", &C);

     while(N--){ // 알파벳 N개 입력받기  (A부터 순서대로 N개 입력받는다) 
         int num = 0;
         cin >> num;
         v.push_back(num);
    } // 입력받기 끝 


    // 문자열 C 순회
    for(int i = 0; C[i] != NULL; i++){   

        if(C[i] >= 'A' && C[i] <= 'Z'){ // 숫자면, push

            // C[i]에서 'A' ASCII 65를 뺀다. v의 인덱스 나옴. -> 앒파벳에 대응하는 num  
            st.push( v[C[i]-65] ); 

        }else{
            // 연산자 만나면, 숫자 2개 pop 해서 연산   
            double b = st.top();
            st.pop();
            double a = st.top();
            st.pop();
            double ans = 0.0;

            if(C[i] == '*'){
                ans = a*b;
            }else if(C[i] == '/'){
                ans = a/b;
            }else if(C[i] == '+'){
                ans = a+b;
            }else if(C[i] == '-'){
                ans = a-b;
            }

             st.push(ans); // 연산 결과를 푸시  
        }
    } 

     printf("%.2f\n", st.top());  // 소수점 2째 자리까지 출력 유의! 

    return 0;    
}

문제

단지 번호 붙이기 백준 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;    
}