[BOJ/백준] 2178 미로 탐색

● [문제번호 2178] 미로 탐색

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

2178번: 미로 탐색

 

● 알아야 할 것

: vector 자료구조와 메소드

: pair 자료구조와 메소드

: BFS

: DFS (재귀, 비재귀)

 

● 풀이 과정

: 보통 visited 배열원소에 bool값으로 방문여부를 저장했다면

이 문제에서는 (1, 1)부터 현재 위치까지 최단 거리를 저장한다.

 

: BFS, DFS (비재귀)로 구현하면

미로의 좌표를 이용해서 구현해야하므로

pair 자료구조를 이용한다.

 

: BFS, DFS (재귀, 비재귀) 를 구현할 때,

다음에 방문할 (상, 하, 좌, 우) 위치가

 

1. 방문한 적 없는 경우 (visited의 값이 0인 경우)

→ 현재 위치의 최단거리 + 1

 

2. 방문한 적 있는 경우 (visited의 값이 1 이상인 경우)

→ min(다음 방문할 위치의 기존 최단거리 , 현재 위치의 최단거리 + 1)

 

의 큰 틀을 벗어나지 않게 구현한다.

 

● 주의 할 것

: 미로의 시작은 (1, 1) 이다.

(0, 0) 이 아니다.

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// controlX : 지도에서 움직일 때 쓰는 상, 하, 좌, 우
// controlY : 지도에서 움직일 때 쓰는 상, 하, 좌, 우
// islandMap : 미로 입력
// visited : (1, 1)로 부터 최단거리
int controlX[4] = {-1, 1, 0, 0};
int controlY[4] = {0, 0, -1, 1};
int maze[101][101];
int visited[101][101];
int N, M;

// 넓이 우선 탐색
// 기본적인 작성 형태로 구현 + pair 사용
void bfs()
{
    // 미로의 좌표를 저장하기 위해 pair 사용
    queue<pair<int, int>> q;
    
    // BFS 함수 진입 전에 실행했기에 방문 체크인 불필요
    // visited[1][1] = 1;
    q.push(pair<int, int>(1, 1));
    
    while(!q.empty())
    {
        int fromRow = q.front().first;
        int fromCol = q.front().second;
        
        q.pop();
        
        // 상, 하, 좌, 우
        for(int i = 0; i < 4; i++)
        {
            int row = fromRow + controlX[i];
            int col = fromCol + controlY[i];
            
            // 방문하면 안되는 4가지
            // 1. 미로의 X축을 벗어난 경우
            if(row < 1 || N < row)
                continue;
            // 2. 미로의 Y축을 벗어난 경우
            else if(col < 1 || M < col)
                continue;
            // 3. 방문한 적이 있을 때 기존보다 최단 거리인 경우
            else if(visited[row][col] != 0 && visited[row][col] <= visited[fromRow][fromCol] + 1)
                continue;
            // 4. 이동할 수 없는 칸인 경우
            else if(maze[row][col] == 0)
                continue;
            else
            {
                visited[row][col] = visited[fromRow][fromCol] + 1;
                q.push(pair<int, int>(row, col));
            }
        }
    }
}

// 깊이 우선 탐색 (비재귀)
// 기본적인 작성 형태로 구현 + pair 사용
void dfs()
{
    // 미로의 좌표를 저장하기 위해 pair 사용
    stack<pair<int, int>> s;
    
    // DFS 함수 진입 전에 실행했기에 불필요
    // visited[1][1] = 1;
    s.push(pair<int, int>(1, 1));
    
    while(!s.empty())
    {
        int fromRow = s.top().first;
        int fromCol = s.top().second;
        
        s.pop();
        
        // 상, 하, 좌, 우
        for(int i = 0; i < 4; i++)
        {
            int row = fromRow + controlX[i];
            int col = fromCol + controlY[i];
            
            // 방문하면 안되는 4가지
            // 1. 미로의 X축을 벗어난 경우
            if(row < 1 || N < row)
                continue;
            // 2. 미로의 Y축을 벗어난 경우
            else if(col < 1 || M < col)
                continue;
            // 3. 방문한 적이 있을 때 기존보다 최단 거리인 경우
            else if(visited[row][col] != 0 && visited[row][col] <= visited[fromRow][fromCol] + 1)
                continue;
            // 4. 이동할 수 없는 칸인 경우
            else if(maze[row][col] == 0)
                continue;
            else
            {
                visited[row][col] = visited[fromRow][fromCol] + 1;
                s.push(pair<int, int>(row, col));
            }
        }
    }
}

// 깊이 우선 탐색 (재귀)
// 기본적인 작성 형태로 구현
void dfs_recursive(int fromRow, int fromCol)
{
    // 상, 하, 좌, 우
    for(int i = 0; i < 4; i++)
    {
        int row = fromRow + controlX[i];
        int col = fromCol + controlY[i];
        
        // 방문하면 안되는 4가지
        // 1. 미로의 X축을 벗어난 경우
        if(row < 1 || N < row)
            continue;
        // 2. 미로의 Y축을 벗어난 경우
        else if(col < 1 || M < col)
            continue;
        // 3. 방문한 적이 있을 때 기존보다 최단 거리인 경우
        else if(visited[row][col] != 0 && visited[row][col] <= visited[fromRow][fromCol] + 1)
            continue;
        // 4. 이동할 수 없는 칸인 경우
        else if(maze[row][col] == 0)
            continue;
        else
        {
            visited[row][col] = visited[fromRow][fromCol] + 1;
            dfs_recursive(row, col);
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N >> M;
    
    // 미로 입력
    for(int r = 1; r <= N; r++)
    {
        for(int c = 1; c <= M; c++)
        {
            char input;
            cin >> input;
            
            maze[r][c] = input - '0';
        }
    }
    
    // (1, 1) 방문 체크인
    visited[1][1] = 1;
    // {DFS재귀, DFS비재귀, BFS} 중 1개 선택
    dfs_recursive(1, 1);
    // dfs();
    // bfs();
    
    // 도착지점까지 최단 거리 출력
    cout << visited[N][M];
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [600 - 그래프 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	13023	ABCDE	https://pirateturtle.tistory.com/269
2	1260	DFS와 BFS	https://pirateturtle.tistory.com/270
3	11724	연결 요소의 개수	https://pirateturtle.tistory.com/271
4	1707	이분 그래프	https://pirateturtle.tistory.com/272
5	2667	단지번호붙이기	https://pirateturtle.tistory.com/273
6	4963	섬의 개수	https://pirateturtle.tistory.com/274
7	2178	미로 탐색	https://pirateturtle.tistory.com/275
8	7576	토마토	https://pirateturtle.tistory.com/276
9	7562	나이트의 이동	https://pirateturtle.tistory.com/277