[BOJ] 2178 - 미로탐색

Sierra·2022년 1월 7일
0

[BOJ] GraphTheory

목록 보기
14/30
post-thumbnail

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

문제

N×M크기의 배열로 표현되는 미로가 있다.

1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제 입출력

  • 예제 입력 1
4 6
101111
101010
101011
111011
  • 예제 출력 1
15
  • 예제 입력 2
4 6
110110
110110
111111
111101
  • 예제 출력 2
9
  • 예제 입력 3
2 25
1011101110111011101110111
1110111011101110111011101
  • 예제 출력 3
38
  • 예제 입력 4
7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111
  • 예제 출력 4
13

Solution

#include <iostream>
#include <deque>
#define MAX 101
using namespace std;

int N, M;
bool visit[MAX][MAX];
int MATRIX[MAX][MAX];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int BFS(int x, int y){
    deque<pair<int, int>> dq;
    dq.push_back({x, y});
    while(!dq.empty()){
        int X = dq.front().first;
        int Y = dq.front().second;
        dq.pop_front();
        visit[X][Y] = true;
        for(int i = 0; i < 4; i++){
            int nx = X + dx[i];
            int ny = Y + dy[i];
            if(nx >= 0 && nx < N && ny >= 0 && ny < M && !visit[nx][ny]){
                visit[nx][ny] = true;
                dq.push_back({nx, ny});
                MATRIX[nx][ny] = MATRIX[X][Y] + 1;
            }
        }
    }
    return MATRIX[N-1][M-1] + 1;
}

int main(){
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        string tmp;
        cin >> tmp;
        for(int j = 0 ; j < M; j++){
            if(tmp[j] == '1') visit[i][j] = false;
            else visit[i][j] = true;
        }
    }
    int result = BFS(0, 0);
    cout << result << '\n';
}

전형적인 BFS 문제다. 최단거리를 찾는 데 다양한 방법들이 있겠지만, DFS와는 다르게 BFS는 정해진 방향들을 하나하나 찾아내는 방식이다. 너비 우선탐색이라는 말 처럼, 그 시점의 주변 노드들을 먼저 탐색하는 방법.

#include <iostream>
#include <deque>
#define MAX 101
using namespace std;

int N, M;
bool visit[MAX][MAX];
int MATRIX[MAX][MAX];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

방문 했던 곳을 기록 할 bool 형 2차원배열, 이동 거리를 기록 할 int 형 2차원 배열이 필요하다. MATRIX라고 선언한 이 배열에서 입력받은 값들을 저장해서 마치 게임의 미니 맵 처럼 활용할 수도 있겠지만, 이미 visit으로 충분히 해결할 수 있어서 그렇게 하지 않았다. 대신 이 배열에는 한 칸씩 이동할 때마다 + 1씩 값을 저장하는 용도로 사용했다.
구현하는 방법은 사실 다양하다. Deque에 데이터 형태를 pair<pair<int, int>, int> 이런 식으로 선언해서 이동 거리까지 저장하는 방법도 있겠지만, 이 문제는 그렇게까지 어려운 문제는 아니니까 그렇게 하지는 않았다.

int main(){
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        string tmp;
        cin >> tmp;
        for(int j = 0 ; j < M; j++){
            if(tmp[j] == '1') visit[i][j] = false;
            else visit[i][j] = true;
        }
    }
    int result = BFS(0, 0);
    cout << result << '\n';
}

입력 데이터가 전부 붙어서 입력되기 때문에 총 입력은 N번 일어난다. 구현하기 나름이고 방법은 사람마다 다르지만 난 복잡하게 생각하기가 싫어서 그냥 string 변수에 입력받고 인덱스 하나하나 비교하며 이동할 수 있는 곳인지 아닌 지 확인 후 visit 배열에 갱신했다. 1은 이동가능, 0은 이동 불가능이다. 즉 0이 발견되면 해당 좌표는 방문 한 것으로 간주하는 것이다.
이 과정이 끝나면 visit 배열에 입력 받은 그대로 미로가 복사될것이다.

그리고 0, 0(문제에서는 1, 1이라고 적혀있지만 입력 받을 때 0부터 입력받았으므로) 부터 BFS를 시작한다.

int BFS(int x, int y){
    deque<pair<int, int>> dq;
    dq.push_back({x, y});
    while(!dq.empty()){
        int X = dq.front().first;
        int Y = dq.front().second;
        dq.pop_front();
        visit[X][Y] = true;
        for(int i = 0; i < 4; i++){
            int nx = X + dx[i];
            int ny = Y + dy[i];
            if(nx >= 0 && nx < N && ny >= 0 && ny < M && !visit[nx][ny]){
                visit[nx][ny] = true;
                dq.push_back({nx, ny});
                MATRIX[nx][ny] = MATRIX[X][Y] + 1;
            }
        }
    }
    return MATRIX[N-1][M-1] + 1;
}

사실 deque를 쓰든 queue를 쓰든 체감 성능차는 크게 없다. 습관적으로 deque를 사용하는 데 queue로 선언해도 문제 풀이에 아무런 지장이 없다.
0, 0부터 deque에 입력 후 deque에 저장되는 데이터를 하나 씩 꺼내 가며 탐색을 실시한다. BFS에 대해서도 한번 글을 남길 예정.
미리 선언 해 둔 가능한 네 가지 방향에 대해 탐색을 실시하되, 방문하지 않은 곳(방문할 수 있는 곳)에 각각 마커 처리를 한 후 MATRIX 배열의 해당 인덱스에 기존의 인덱스의 값 + 1을 더한다.
전역변수에 선언 해 두었기 때문에 MATRIX 배열의 모든 값은 처음에는 0이다. 즉 이동을 하면 할 수록 +1 씩 저장되며, 얼마나 멀리 이동했는지를 기록하는 셈이다.
모든 탐색이 끝나면 N-1, M-1 인덱스의 MATRIX값에 +1을 한 것이 정답이 된다. 시작점의 값을 따로 처리해주지 않아서 +1을 해주어야한다. 코딩하는 사람의 자유지만 탐색을 시작할 때 초기값 x, y에 대한 MATRIX 배열의 값을 1로 대입해준 후 탐색을 해도 무관하다. 그러면 굳이 return값에 +1 을 해줄 필요는 없을 것이다.

전형적인 BFS 연습문제. 실버1이라는 난이도 치고는 어렵지는 않지만, BFS의 특징 상 이런 상황에서 최단거리를 도출해낼 수 있다는 점을 이해해야 하는 문제였다.

물론 어지간한 최단거리 구하는 문제가 이렇게 단순하지는 않지만...

profile
블로그 이전합니다 : https://swj-techblog.vercel.app/

0개의 댓글