JArchive 프로그래밍 일기

문제

알고스팟 백준 1261번

리뷰

"맞았습니다!" 를 보고 나서야 후련했다.

자꾸 틀렸던 이유는 boundary_check 함수에서 x는 N보다 작고, y는 M보다 작은지 확인해야 하는데,

y도 N보다 작다고 코딩해서 계속 틀렸었다....

deque를 써서 벽을 부순 경우에는 push_back , 빈 방에 온 경우 벽은 안부숴도 되니까 push_front 로 해결했다.

방문 표시를 하는 배열을 써도 되고, 안써도 된다.

구글링을 해보면 다익스트라를 쓴 코드도 있었다.

그리고 배운 점은, 정수1개를 입력 받을 때는 1d를 쓴다는 것이다.

for(int i = 1; i <= N; i++){     //map 입력받기
    for(int j = 1; j <= M; j++){
        scanf("%1d", &map[i][j]);  // 정수 1개를 입력 받을 때는 1d 를 쓴다. 
        broken_cnt[i][j] = -1;  // 전부 -1로 초기화 
    }
} 

변수명, 함수명도 약어 없이 짓고 누구나 이해할 수 있도록 직관적이고 자세하게 적는게 좋다는데.

알고리즘 문제를 풀 때는 자꾸 짧게만 쓰게 된다. 마음이 급해서 그런가보다.

백준 문제 중에 BFS 가 필요한 숨바꼭질, 숨바꼭질3을 풀어본게 도움이 됬던 것 같다.

코드 1

main() 함수는 최대한 간결해야 한다는 글을 읽어서 Input 과 Solve 로 코드를 분리해 보았다.

#include <iostream>
#include <algorithm> 
#include <vector>
#include <deque>
#include <utility>
#define MAX 101
using namespace std;

int N, M, answer;  // 세로 N, 가로M

int map[MAX][MAX]; // 지도  
int broken_cnt[MAX][MAX] = {-1, }; // // 현재 지점에서 벽을 부순 횟수
bool visit[MAX][MAX]; // 방문 여부 

int xx[5] = {0, 0, -1, 1};
int yy[5] = {-1, 1, 0, 0};

deque<pair<int, int> > de;

bool check_boundary(int x, int y){
    return (x <= N && x >= 1 && y <= M && y >= 1 );
}

void BFS(int x, int y){ // (1,1)에서 시작해서 (N,M)에 도착해야 한다.  

    de.push_back( {x, y});
    broken_cnt[x][y] = 0;
    visit[x][y] = true;

    while(!de.empty()){  

        int now_x = de.front().first;
        int now_y = de.front().second;
        de.pop_front();

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

            int next_x = now_x + xx[i];
            int next_y = now_y + yy[i];

            if(check_boundary(next_x, next_y) == false) continue; // 좌표 범위 체크  

            if(true == visit[next_x][next_y]) continue; // 이미 방문했다면 지나간다. 

            if(map[next_x][next_y] == 1){  // 벽이면 뚫는다.  
                broken_cnt[next_x][next_y] = broken_cnt[now_x][now_y]+1; 
                visit[next_x][next_y] = true;
                de.push_back({next_x, next_y});

            }else if(map[next_x][next_y] == 0){ // 빈방이면 안 뚫어도 된다. 
                broken_cnt[next_x][next_y] = broken_cnt[now_x][now_y];
                visit[next_x][next_y] = true;
                de.push_front({next_x, next_y});

            }
        }

    }
}

void Solve(){
    BFS(1, 1);
     cout << broken_cnt[N][M];
}

void Input(){
    cin >> M >> N ; // 가로M, 세로 N

    for(int i = 1; i <= N; i++){     //map 입력받기
        for(int j = 1; j <= M; j++){
            scanf("%1d", &map[i][j]);  // 1개의 정수를 입력받을 때 1d 
         }
    } 
}

int main(void){

    Input();

    Solve();   

    return 0;
} 

코드2

#include <iostream>
#include <algorithm> 
#include <vector>
#include <deque>
#include <utility>
#define MAX 101
using namespace std;


int N, M, answer;
int map[MAX][MAX]; // 지도  
int broken_cnt[MAX][MAX] = {-1, }; // // 현재 지점에서 벽을 부순 횟수

int xx[5] = {0, 0, -1, 1};
int yy[5] = {-1, 1, 0, 0};

deque<pair<int, int> > de;

bool check_boundary(int x, int y){ // 좌표 범위 체크  
    return (x <= N && x >= 1 && y <= M && y >= 1 );
}

void BFS(){ // (1,1)에서 시작해서 (N,M)에 도착해야 한다.  

    de.push_back( {1, 1});
    broken_cnt[1][1] = 0; // 일단 방문하면 0 

    while(!de.empty()){  

        int now_x = de.front().first ;
        int now_y = de.front().second;
        de.pop_front();

        int now_cnt = broken_cnt[now_x][now_y]; // 현재 지점에서 벽을 부순 횟수  

        for(int i=0; i < 4; i++){
            int next_x = now_x + xx[i];
            int next_y = now_y + yy[i];

            if(check_boundary(next_x, next_y) == false) continue; // 좌표 범위 체크  

            if(broken_cnt[next_x][next_y] != -1) continue; // 이미 방문했다면 지나간다. 

            if(map[next_x][next_y] == 1){  // 벽이면 뚫는다.  
                broken_cnt[next_x][next_y] = now_cnt+1; 
                de.push_back({next_x, next_y});

            }else if(map[next_x][next_y] == 0){ // 빈방이면 안뚫어도 된다  
                broken_cnt[next_x][next_y] = broken_cnt[now_x][now_y];
                de.push_front({next_x, next_y});
            }
        }

    }
}

void Solve(){

    BFS();
     cout << broken_cnt[N][M];
}

void Input(){

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

    for(int i = 1; i <= N; i++){     //map 입력받기
        for(int j = 1; j <= M; j++){
            scanf("%1d", &map[i][j]);  // 정수 1개를 입력 받을 때는 1d 를 쓴다. 
            broken_cnt[i][j] = -1;  // 전부 -1로 초기화 
        }
    } 
}

int main(void){

    Input();

    Solve();   

    return 0;
}