[백준/boj] 2178번: 미로 탐색 | C++

 

bfs 연습 문제!

---

문제 : https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

문제풀이 핵심

 

bfs 는 먼저 도달한 값이 가장 최단거리 값이므로 같은 목적지에 두번 이상 방문할 것이라는 예외처리 필요없음.

이라는 부분을 인지하지 못해서 헷갈렸었다.

 

bfs를 잘 쓸 수 있는지가 관건!

 

그리고 사소한 거지만 

#define X first
#define Y second

여기에서는 땀흘리면 안되는데 땀흘려서 

X와 Y를 사용한 53-54번째 줄에서 expression result unused 에러가 났다 ㅋㅋ 이 부분도 땀 못봐서 좀 헤멘 부분이었다

---

문제풀이 코드

#include<iostream>
#include<algorithm> //fill 함수, utility 헤더도 포함됨 - pair 사용 
#include<queue>

using namespace std;
//거리같은 경우는 -1 등으로 따로 초기화 해주기 
//이중포문 or fill()  
int digst[102][102]; // 거리 저장할 배열

int board[102][102]; // 입력값 저장할 배열
int vis[102][102];

//define 뒤에는 땀흘리지말것
#define X first
#define Y second

int n,m;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    queue<pair<int,int>> Q; 
    int dx[4] = {1,0,-1,0};
    int dy[4] = {0,1,0,-1};

    cin >> n>>m;

    
    for(int i=0;i<n;i++){
        string a;
        cin >> a;
        
        for(int j=0;j<m;j++){
            int c = a[j] - '0'; //char -> int 해줄때 아스키코드 0 빼줄것 
            board[i][j] =c;

        }
        fill(digst[i],digst[i]+m,-1); //fill 함수를 이용한 값 초기화 

    }

    vis[0][0] =1;
    digst[0][0]=1;
    Q.push({0,0});

    while(!Q.empty()){
        pair<int,int> cur = Q.front();
        Q.pop();

        for(int i = 0; i<4; i++){
            int nx = cur.X + dx[i];
            int ny = cur.Y + dy[i];

            if(nx<0 || nx>=n || ny <0 || ny >=m) continue;
            if(vis[nx][ny] || board[nx][ny] != 1) continue;

            //bfs 는 먼저 도달한 값이 가장 최단거리 값이므로 같은 목적지에 두번 이상 방문할 것이라는 예외처리 필요없음
            digst[nx][ny] = digst[cur.X][cur.Y]+1;
            vis[nx][ny] = 1;
            Q.push({nx,ny});
        }
    }

    cout << digst[n-1][m-1];
    return 0;
}

 

---

로직 설명

그냥 bfs 알고리즘이다! 달달 외워서 숙지하는게 중요~~

---

 

문제풀이에 사용된 함수

algorithm 의 fill 함수와 pair

 

fill함수를 사용한 digst 초기화

for(int i=0;i<n;i++){
        string a;
        cin >> a;
        
        for(int j=0;j<m;j++){
            int c = a[j] - '0'; //char -> int 해줄때 아스키코드 0 빼줄것 
            board[i][j] =c;

        }
        fill(digst[i],digst[i]+m,-1); //fill 함수를 이용한 값 초기화 

    }

 

fill 함수 사용법 

fill(시작 주소, 종료 주소(=시작주소 +m), 초기화 할 값);

 

 

 

pair를 이용한 이중 배열 표현

    queue<pair<int,int>> Q;

 

pair 는  utility에 존재하지만 algorithm 에 utility가 포함되어있으므로 algorithm을 가져와서 사용함

---

실수 포인트

1. 입력을 문자열로 받고 char 를 int 로 고쳐야 함

-> 그냥 받아오면 48, 49(0,1의 아스키코드 값) 들이 가득 차있는 배열을 볼 수 있다

 

2. 따로 목적지에 대한 다중 방문에 대해 고려할 필요가 없다는 것!

 

3. 마지막 줄에 digst 목적지 값 출력할 때 

    cout << digst[n-1][m-1];

 

라는 것! n,m 으로 쓰면 안된다 . 당연하지만 ㅎ

 

---

 

마무리

실수도 실력이다! 실수 없애기!