[Baekjoon] 백준 2178번: 미로 탐색 (c++)

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

2178번: 미로 탐색

 

쉽게 풀릴 줄 알았는데 실수를,,,많이 한 문제다

먼저 최단거리를 구할 때는 BFS로 탐색해야하는데, DFS를 써 버린 것. DFS는 재귀호출 하는 가지수가 너무 많아서 시간초과가 걸렸다.

DFS	DFS ⚭ BFS	BFS
- 검색 대상 그래프가 큰 경우(정점과 간선의 개수가 많은 경우) - 경로의 특징을 저장해둬야 하는 문제    • ( ex) 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는 데 경로에 같은 숫자가 있으면 안된다 ) - 스택 또는 재귀함수로 구현	모든 정점을 방문하는 문제	- 최단거리 문제 - 큐를 이용해서 구현 - BFS는 경로의 특징을 가지지 못함

 

그리고 BFS로 풀었는데.. 제출하자마자 틀렸다고 나와서 반례를 넣어봤는데도 어디서 틀린거지 한참 생각해봐도..

ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

근데 이부분이 문제였다. 입출력을 빠르게 하려고 넣어둔건데, 

⚠️ ios::sync_with_stdio(false) 를 사용한 뒤에는 C++ 입출력 명령 (cin, cout 등 iostream 헤더 소속) 과 C 입출력 명령 (printf, scanf, getchar 등 cstdio 헤더 소속) 을 섞어서 쓰면 안 된다.

그래서 처음부터 틀렸다고 나왔던것,,,!

 

문제 자체는 BFS 구현 그 자체였다.

미로에서 1인 숫자만 따라 큐에 집어넣고, 가장 먼저 N, M에 도달하면 그때의 cnt값을 출력하면 된다.

 

**주의해야 할 것은, isVisited표시를  q.push(make_pair(dy,dx)); 여기 넣기전에 true로 해줘야, 다른 경로로 들어갔을 때 같은경로를 중복해서 넣는것을 피할 수 있다.

2 2
11
11
이 예시의 경우,

0,0 -> 1,0 / 0,1

1,0 -> 2,0 / 1,1

0,1 -> 1,1 / 0,2 

이므로 만약 q에 push하기 전에 isVisited를 true로 표시하지 않았다면, 똑같은 경로인 (1,1)으로부터 계속 가지가 뻗어나가기 때문에, 메모리 초과가 날 수 있다. 

 

나도 처음에 q.pop()하기전에 isVisited = true로 해줬더니,,, 메모리 초과가 났다😅 

 

 

---

코드(c++)

#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
#define MAX 101

int px[4] = { 0, 0, -1, 1 }; //상 하 좌 우
int py[4] = { -1, 1, 0, 0 };
int map[MAX][MAX] = {0};
bool isVisited[MAX][MAX] = {false,};
int cnt = 0;

void BFS(int x, int y, int N, int M){
   
    queue<pair<int, int>> q;
    
    q.push(make_pair(y, x));
    
    while (!q.empty()) {
        if(x == M-1 && y == N-1) break;
        int q_size = q.size();
        cnt++;
        
        while (q_size--) {
            y = q.front().first;
            x = q.front().second;
            if(x == M-1 && y == N-1) break;
            q.pop();
            
            for(int i=0;i<4;i++){
                int dx = x + px[i];
                int dy = y + py[i];
                if( (dx < 0 || dx >= M || dy < 0 || dy >= N) || map[dy][dx] == 0 || isVisited[dy][dx]) continue;
                isVisited[dy][dx] = true;
                q.push(make_pair(dy, dx));

            }
            
        }
    }
}

int main(){
//    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   
    int N,M;
    cin >> N >> M;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            scanf("%1d", &map[i][j]);
        }
    }
    
    BFS(0, 0, N, M);
   
    cout << cnt;
    return 0;
}

​

 

 

 

 

 

 

 

DFS로 푼 코드. 시간초과가 난다

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

int px[4] = { 0, 0, -1, 1 }; //상 하 좌 우
int py[4] = { -1, 1, 0, 0 };
int map[MAX][MAX] = {0};
bool isVisited[MAX][MAX] = {false,};
int Min = 999999999;
void DFS(int x, int y, int N, int M, int cnt){
    if(isVisited[y][x]) return;
    isVisited[y][x] = true;
    
    cnt++;
    if(x == M-1 && y == N-1) { Min = min(Min, cnt); return; }
    
    for(int i=0;i<4;i++){
        int dx = x + px[i];
        int dy = y + py[i];
        
        if( (dx < 0 || dx >= M || dy < 0 || dy >= N) || map[dy][dx] == 0 || isVisited[dy][dx] == true) continue;
        
        DFS(dx, dy, N, M, cnt);
        isVisited[dy][dx] = false;
        
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   
    int N,M;
    cin >> N >> M;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            scanf("%1d", &map[i][j]);
        }
    }
    
    DFS(0, 0, N, M, 0);
   
    cout << Min;
    return 0;
}

 

참고한 블로그 
https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90