백준 | 2178. 미로 탐색

 

1. idea

• BFS
  • 1이고 방문 안한거면 방문처리, 4방향 중 1이고 방문 안한거면 queue에 담고 방문처리
  • 4군데 다 갔으면 거기서 또 갈 수 있는 곳 찾고 이런 식으로 
• (이게 오류가 나서 다시 idea를 추가한게)
  • maze vector에 그 위치까지 이동하는데 걸린 거리를 저장!

 

• DFS
  • 재귀 활용 탐색 => 거리 +1 해서 저장, 갈수 있으면 재귀
• 이게 잘 작동이 안되가지고 다시 수정한게
  • 돌다가 처음 방문이면 지금까지 온 거리 +1, 방문 했던 곳이면 지금 값보다 크면 다시 탐색
  • 아니면 그 길 pass

 

2 BFS 함수 만들기

void bfs(vector<vector<int>>&maze,vector<vector<bool>>&v, int r, int c, int& cnt){
    int dx[]= {0, 0, -1, 1};
    int dy[]= {1, -1, 0, 0};

    queue<pair<int, int>>q;
    q.push({r,c});
    v[r][c] = true;

    while(!q.empty()){
        auto [y, x] = q.front();
        q.pop();

        for(int i = 0; i<4; ++i){
            int nx = x+dx[i];
            int ny = y+dy[i];

            if(!v[ny][nx] && maze[ny][nx]==1){
                v[ny][nx] = true;
                q.push({ny,nx});
            }
        }
        cnt++;
    }
}​

이거는 그냥 탐색한 횟수를 다 센거라 사실 의미가 없는 행동임.

 

3. 오류 수정

void bfs(vector<vector<int>>&maze,vector<vector<bool>>&v, int r, int c){
    int dx[]= {0, 0, -1, 1};
    int dy[]= {1, -1, 0, 0};

    queue<pair<int, int>>q;
    q.push({r,c});
    v[r][c] = true;

    while(!q.empty()){
        auto [y, x] = q.front();
        q.pop();

        for(int i = 0; i<4; ++i){
            int nx = x+dx[i];
            int ny = y+dy[i];

            if(!v[ny][nx] && maze[ny][nx]==1){
                v[ny][nx] = true;
                maze[ny][nx] = maze[y][x]+1;
                // 방문한 거기에 출발점에서부터의 거리를 계속 저장
                q.push({ny,nx});
            }
        }
    }
}

 

방문한 위치마다 출발점에서부터의 거리를 저장해서 업데이트 해가는 방식 활용 ★★★★★

 

4. DFS 함수 만들기

void dfs(vector<vector<int>>&maze,vector<vector<bool>>&v, int r, int c){
    int dx[]= {0, 0, -1, 1};
    int dy[]= {1, -1, 0, 0};

    v[r][c] = true;

    for(int i = 0; i<4; ++i){
        int nx = r+dx[i];
        int ny = c+dy[i];

        if(!v[ny][nx] && maze[ny][nx]!=0){
            dfs(maze, v, ny, nx);
            maze[ny][nx] = maze[r][c]+1;
        }
    }
}

• 이 방법은 최단거리를 보장하지 않으며 DFS로 최단거리를 구하려면 모든 경로를 탐색하면서 최솟값 갱신을 해줘야함.
• 때문에 이 코드의 문제점은
• maze[ny][nx] = maze[r][c] + 1; 이게 재귀 끝나고 실행됨 → 경로가 끝났을 때만 거리 갱신됨
• 처음 시작점 (1, 1)의 값은 1이지만, maze[r][c] + 1이 반영되기 전에 dfs()가 깊게 들어감
• 그 결과 maze[N][M]은 여전히 1 또는 0으로 남을 수 있음 → 출력 이상하게 됨

 

• 재귀 중 더 짧은 경로로 도착했을 때만 갱신
• 즉, 조건 추가:
  maze[ny][nx] == 1 || maze[ny][nx] > maze[r][c] + 1

void dfs(vector<vector<int>>&maze,vector<vector<bool>>&v, int r, int c){
    int dx[]= {0, 0, -1, 1};
    int dy[]= {1, -1, 0, 0};

    v[r][c] = true;

    for(int i = 0; i<4; ++i){
        int nx = c+dx[i];
        int ny = r+dy[i];

        if(!v[ny][nx] && maze[ny][nx]==1){
            maze[ny][nx] = maze[r][c]+1;
            dfs(maze, v, ny, nx);
            
        } // 최초방문시 dfs

        else if (maze[ny][nx] > maze[r][c] + 1) {
            maze[ny][nx] = maze[r][c] + 1;
            dfs(maze, v, ny, nx);
        } // 최단거리 갱신 추가(방문했던 곳인데 지금 가는 거리보다 오래걸린거면 그쪽방향도 방문해서 탐색)
    }
}

 

이렇게!

 

5. 최종 코드

//BFS
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void bfs(vector<vector<int>>&maze,vector<vector<bool>>&v, int r, int c){
    int dx[]= {0, 0, -1, 1};
    int dy[]= {1, -1, 0, 0};

    queue<pair<int, int>>q;
    q.push({r,c});
    v[r][c] = true;

    while(!q.empty()){
        auto [y, x] = q.front();
        q.pop();

        for(int i = 0; i<4; ++i){
            int nx = x+dx[i];
            int ny = y+dy[i];

            if(!v[ny][nx] && maze[ny][nx]==1){
                v[ny][nx] = true;
                maze[ny][nx] = maze[y][x]+1;
                q.push({ny,nx});
            }
        }
    }
}

int main(){
    int N, M;
    string line;
    cin >> N >> M;
    vector<vector<int>> maze(N+2,vector<int>(M+2, 0));
    vector<vector<bool>>visit(N+2, vector<bool>(M+2, false));

    for(int i =1; i<=N; ++i){
        cin >> line;
        for(int j =1; j<=M; ++j){
            maze[i][j] = int(line[j-1])-'0';
        }
    }

    bfs(maze, visit, 1, 1);

    cout << maze[N][M] << endl;

    return 0;

// DFS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void dfs(vector<vector<int>>&maze,vector<vector<bool>>&v, int r, int c){
    int dx[]= {0, 0, -1, 1};
    int dy[]= {1, -1, 0, 0};

    v[r][c] = true;

    for(int i = 0; i<4; ++i){
        int nx = c+dx[i];
        int ny = r+dy[i];

        if(!v[ny][nx] && maze[ny][nx]==1){
            maze[ny][nx] = maze[r][c]+1;
            dfs(maze, v, ny, nx);
            
        } // 최초방문시 dfs

        else if (maze[ny][nx] > maze[r][c] + 1) {
            maze[ny][nx] = maze[r][c] + 1;
            dfs(maze, v, ny, nx);
        } // 최단거리 갱신 추가(방문했던 곳인데 지금 가는 거리보다 오래걸린거면 그쪽방향도 방문해서 탐색)
    }
}

int main(){
    int N, M;
    string line;
    cin >> N >> M;
    vector<vector<int>> maze(N+2,vector<int>(M+2, 0));
    vector<vector<bool>>visit(N+2, vector<bool>(M+2, false));

    for(int i =1; i<=N; ++i){
        cin >> line;
        for(int j =1; j<=M; ++j){
            maze[i][j] = int(line[j-1])-'0';
        }
    }

    dfs(maze, visit, 1, 1);

    cout << maze[N][M] << endl;

    return 0;
}