백준, BOJ, 2178번 C++ [CPP]

 

경로 탐색의 핵심은 탐색 방법이다.

그 중 얘는 BFS다.

 

www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

 

---

 

왜 BFS일까?는

최단경로를 찾아야하기 때문이다.

DFS는 최단경로를 보장하는 방법이 아니다.

 

어떠한 경우에 대해서도 최단경로를 찾기 위해서는 BFS를 쓸 수 있다.

일반적으로 메모리는 DFS보다 BFS가 많이 먹을 수 있는..가능성이 높다

 

나는 이것을 논리가 맞다고 생각하고도 엄청 많이 틀렸다.

 

바로 입력에 대해서 확인을 소홀히 해서 그렇다.

이 문제에서 입력은 공백없이 주어졌다.

 

---

 

#1 맞는 풀이 

틀린 부분에 대한 주석 달았음

 

#include <iostream>
#include <queue>

#define X first
#define Y second

using namespace std;

int visit[102][102];

string maze[102];
int n,m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int min = 0;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    queue<pair<int,int>> Q;
    
    cin >> n >> m; 
    
    for(int i = 0; i< n; i++){
        //cin >> maze[i][j]; // -> 이렇게 받을 수 없음 공백이 없어서
        cin >> maze[i];
    }
    
    //거리 초기화
    for(int i = 0; i< n; i++){
        for(int j = 0; j<m; j++){
            visit[i][j] = -1;
        }
    }
    
    
    visit[0][0] = 0;
    Q.push({0,0});
    
    while(!Q.empty()){
        pair<int,int> cur = Q.front();
        Q.pop();
        
        for(int dir = 0; dir < 4; dir++){
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if(nx< 0 || nx >= n || ny <0 || ny >=m)
                continue;
            if(visit[nx][ny] >= 0 || maze[nx][ny] != '1') // 문자로 받았음.
                continue;
            visit[nx][ny] = visit[cur.X][cur.Y] + 1;
            Q.push({nx,ny});
        }
    }
    cout << visit[n-1][m-1] + 1;
}

 

 

처음의 접근법은

큐에있는 데이터의 양에 따라서 거리가 바뀌지 않을까?? 라고 생각했지만

방향이 4개인.. 여기에서는 활용하는 것이 직감적으로 비효율적이라고 생각해서 패스.

만약 이진 탐색이라도 비효율적임... ㅎ

 

그래서 어떻게할까...?

어떻게 해야 BFS의 단계가 넘어갔다는 것을 알까?

즉, 이전 단계와 현재 단계를 어떻게 구분할까?

최초의 단계를 저장한다면 그 다음 단계는 이전 단계의 + 1 이다.

여기서 visit에 방문을 함과 동시에

어느 단계에 visit을 했는지 저장하는 방법을 썼다.

 

** 이게 핵심이고 언제든지 많이 쓰일 수 있는 포인트다.

 

그래서 임의로 단계를 -1로 초기화시켜서 visit을 할 때 현재 단계를 저장하면서 탐색하게 만들었다.

이 문제의 의미는

BFS의 가장 기본적이면서 중요한 BFS의 최소 경로를 다뤄봤다.