문제

Two Dots 백준 16929번

리뷰

처음에 BFS로 시도했는데, 문제의 에제 입출력 4개중에 3개만 맞아서 멘붕이 왔다.

3 4
AAAA
ABCA
AADA // 이건 사이클이 없는데. "Yes"를 출력한다... 

그래서 사이클 관련 질문게시판 글을 읽고 DFS로 시도해봤다.

시작지점을 목적지점 삼아서 탐색을 했다.

사이클은 시작점과 끝점이 같다고 생각할 수 있다.

그런데, 시작점 부터 방문 배열에 1로 체크해두면, 방문 안 해본 곳을 찾아서 탐색하기에는 시작점이자 끝점에 되돌아갈 수 없다. 그래서 이미 방문했더라도, 목적지인지 검사했다. 

 

일단 시작할 때 시작점 자체가 cnt 1개니까 1로 시작한다.

for(int i = 0; i  < N ; i++){  // 모든 지점에서 DFS 시작
    for(int j = 0; j < M ; j++){

        start_x = i; // 목적지 설정  
        start_y = j;

        DFS(i, j, 1); // 시작점에서 이미 cnt = 1 로 시작 

        if(stop_flag) break;
    }
} 

DFS를 시작하면, 방문 표시를 해두고, 상하좌우 4방향을 검사한다.

이 때, 아래의 3가지 조건을 만족하면 다음 칸으로 이동한다.

if(!boundary(next_x, next_y)) continue;  // 범위 내 인지  

if(B[start_x][start_y] != B[next_x][next_y]) continue; // 색깔이 같은지  

if(check[next_x][next_y] == 0){ // 미방문인지  

만약, 세번째 if 문에서 조건을 만족시키지 않고, 방문 했더라도, 목적지라면 탐색을 끝내야한다.

여기서 중요한 건 cnt가 4 이상인지도 함께 확인해야 한다는 것이다.

    if(check[next_x][next_y] == 0){ // 미방문인지  

        check[next_x][next_y] = 1;
        DFS(next_x, next_y, cnt+1); // 방문한다  
        check[next_x][next_y] = 0;

    }else{ // 목적지인지

        if(next_x == start_x && next_y == start_y && cnt >= 4){  // 4번 이상 움직여서 목적지 도달 
        stop_flag = true; // 탐색 끝!
        return;
    }
} 

맞는데 왜틀리지 ㅠㅠ 하고 골머리썩다가 BOJ 질문게시판에 글올려서 고수분들의 도움을 받았다. 정말 감사했다.

속시원했다.

코드

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

int N, M;   // 행, 열  
char B[51][51]; //지도  
int check[51][51]; //방문 표시 지도

bool stop_flag = false;
int start_x, start_y; // 시작점을 '목적지'로 이용한다.  

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


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

void DFS(int now_x, int now_y, int cnt){ 

    if(stop_flag) return;

    check[now_x][now_y] = 1; // 방문  

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

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

        if(!boundary(next_x, next_y)) continue;  // 범위 내 인지  

        if(B[start_x][start_y] != B[next_x][next_y]) continue; // 색깔이 같은지  

        if(check[next_x][next_y] == 0){ // 미방문인지  

            check[next_x][next_y] = 1;
            DFS(next_x, next_y, cnt+1); // 방문한다  
            check[next_x][next_y] = 0;

        }else{
            // 목적지인지  
            if(next_x == start_x && next_y == start_y && cnt >= 4){  // 4번 이상 움직여서 목적지 도달 
                stop_flag = true;
                return;
            }
        } 

    }

} 

int main(void){
     // freopen("input.txt", "rt", stdin);
     cin >> N >> M; 

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

    string res = "";


    for(int i = 0; i  < N ; i++){  // 모든 지점에서 DFS 시작
        for(int j = 0; j < M ; j++){

            start_x = i; // 목적지 설정  
            start_y = j;

            DFS(i, j, 1); // 시작점에서 이미 cnt = 1 로 시작 

            if(stop_flag) break;
        }
    } 

    if(stop_flag) cout << "Yes";
    else cout << "No";

    return 0;    
}
728x90

'알고리즘 > 백준' 카테고리의 다른 글

팩토리얼 백준 10872번  (0) 2020.09.12
스타트와 링크 백준 14889번  (0) 2020.09.10
섬의 개수 백준 4963번  (0) 2020.09.08
나이트의 이동 백준 7562번  (0) 2020.09.08
사탕게임 백준 3085번 c++  (0) 2020.09.07

문제

섬의개수 백준 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;    
}
728x90

'알고리즘 > 백준' 카테고리의 다른 글

스타트와 링크 백준 14889번  (0) 2020.09.10
Two Dots 백준 16929번  (0) 2020.09.09
나이트의 이동 백준 7562번  (0) 2020.09.08
사탕게임 백준 3085번 c++  (0) 2020.09.07
후위표기식2 백준 1935번 c++  (0) 2020.09.07

문제

나이트의 이동 백준 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;    
}
728x90

'알고리즘 > 백준' 카테고리의 다른 글

Two Dots 백준 16929번  (0) 2020.09.09
섬의 개수 백준 4963번  (0) 2020.09.08
사탕게임 백준 3085번 c++  (0) 2020.09.07
후위표기식2 백준 1935번 c++  (0) 2020.09.07
단지 번호 붙이기 백준 2667번 c++  (0) 2020.09.07

문제

사탕게임 백준 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;    
}
728x90

'알고리즘 > 백준' 카테고리의 다른 글

섬의 개수 백준 4963번  (0) 2020.09.08
나이트의 이동 백준 7562번  (0) 2020.09.08
후위표기식2 백준 1935번 c++  (0) 2020.09.07
단지 번호 붙이기 백준 2667번 c++  (0) 2020.09.07
미로탐색 백준 2178번  (0) 2020.09.07

문제

후위표기식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;    
}
728x90

'알고리즘 > 백준' 카테고리의 다른 글

나이트의 이동 백준 7562번  (0) 2020.09.08
사탕게임 백준 3085번 c++  (0) 2020.09.07
단지 번호 붙이기 백준 2667번 c++  (0) 2020.09.07
미로탐색 백준 2178번  (0) 2020.09.07
토마토 백준 7576번  (0) 2020.09.06

문제

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

'알고리즘 > 백준' 카테고리의 다른 글

사탕게임 백준 3085번 c++  (0) 2020.09.07
후위표기식2 백준 1935번 c++  (0) 2020.09.07
미로탐색 백준 2178번  (0) 2020.09.07
토마토 백준 7576번  (0) 2020.09.06
이분 그래프 백준 1707  (0) 2020.09.06

문제

미로 탐색 백준 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;    
}
728x90

'알고리즘 > 백준' 카테고리의 다른 글

후위표기식2 백준 1935번 c++  (0) 2020.09.07
단지 번호 붙이기 백준 2667번 c++  (0) 2020.09.07
토마토 백준 7576번  (0) 2020.09.06
이분 그래프 백준 1707  (0) 2020.09.06
ABCDE 백준 13023 c++  (0) 2020.09.06

+ Recent posts