[백준] 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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

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

 

 

범위 설정만 잘 했어도...ㅜㅜ;;;

이문제는 웬지 다른 사람들코드보면 많은 걸 느낄 수 있을 것 같다. 

전에 내 코드르 보니 x좌표랑 y좌표따로 큐에 넣었다. 전 포스팅에서도 말한것 같은데, bfs가 왜 큐로 사용해야하는지 이유를 몰랐기 때문에 문제 푸는데도 많은 어려움이 있었다. 내 눈에는 bfs나 dfs나 똑같아 보였기 때문이다.

아무튼, 내가 이거에 대해 이해 시킬수는 없겠지만, 나는 권오흠 교수님이 유튜브에 올리신 강의 영상을 보고 많이 깨달았다. 잡담은 여기서 그만하고..

 

코드를 보자

#include <bits/stdc++.h>
using namespace std;
int n,m;
string arr[101];

bool visit[101][101];

int dx[] = {1,-1,0,0};
int dy[] = {0,0,-1,1};
int check[101][101];
void bfs(int i,int j) {
  queue<pair<int,int>> q;
  q.push(make_pair(i,j));
  visit[i][j] = true;
  while(!q.empty()) {
    int x = q.front().second;
    int y = q.front().first;
    q.pop();

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

        if( 0 > newX || n <= newX )  {
          continue;
        }

        if (0 > newY || m <= newY) {
          continue;
        }

        if (arr[newX][newY] == '1' && !visit[newX][newY] && check[newX][newY] == 0) {
          check[newX][newY] = check[x][y]  + 1;
          q.push(make_pair(newX,newY));
          visit[newX][newY] = true;
        }
    }
  }
}
int main(void) {
  
  cin >> n >> m;
  for(int i = 0;i<n;i++) {
    cin  >> arr[i];
  }

  bfs(0,0);
  
  cout << check[m-1][n-1] + 1;

}
    

일단 BFS를 안다고 가정하고 설명할 예정이다. 

위에 보면 dx,dy가 보이는데 이건 방향 벡터라고 하는 거다. 물론, 수학적인 방향 백터는 다른 의미로 알고 있지만... 그렇다고 합니다. 이걸 어떻게 구하는지 확인하는 방법은 사분면을 그려보는 거다.

사분면을 그려보면 동서 남북이 나온다. 누가 봐도 북쪽은 위다. 아무튼 잘 생각해 보면 값을 얼마나 증가 시켜 야 할까?

         |

   -     |       +

----------------------         북쪽은 x좌표가 필요하지 않는다. 그래서 0,1 ..이런식으로 풀면

         |

   -     |        +               동 : (1,0) 서 (-1,0) 남(0,-1) 북(0,1) 여기서 벗어나지 않으면 무조건 답은 같게 나온다.

         |

 

이 다음 우리가 생각해야 할 부분은 범위다.

이건 값을 추가하기 때문에 자치하다가는 범위를 벗어날수 있다.

예를들어, n의 최대 값은 5인데, 값을 증가하고 보니 y좌표가 5인 상황일때 값을 증가시켜버리면... y좌표는 6이 되버린다. 6이 되버리면 이 값은 우리가 지정한 값이 아닌 값이다. 아니 정확히 말하면 값이 없던거라 할 수 있다.

그래서 범위 예외처리를 반드시 해야한다.

 

그리고 이게 스트링인 이유가 있다. 물론 스트링으로 해야하는건 아니지만, 이중 포문을 활용해 문제를 풀려고 했지만, 어떤 연유로 되지 않았다. 그래서 그냥 string으로 했다. string의 특징상 줄은 무한정으로 작성될수 있다. 그렇기 때문에 줄만 제어하면 된다고 생각했다. 그래서 string으로 했다.

 

문제를 읽어보면, 값이 1이라면... 지나갈 수 있고, 0이라면 값을 지나갈 수 없다. 이것도, 그냥 값을 -1로 해도 된다. 그렇게 푸는 답도 존재할지도 모른다. (계속 빼기하면 되지 않을까요? 저는 잘 안되서 하진않았지만 이론상 될겁니다. 연구가 필요해 보이네여.) 이제 거의다 끝났다.

 

이제 방문할 차례다. 방문을 하면 방문했다고 false를 true로 바꾸어 주면 된다. 만약 방문을 여러번 해야하는 상활이라면... 아마 int로 해야할지 않을까요? (잘 모르겠지만...ㅎㅎ)  마지막으로 check는 그냥 전의 값을 증가 시켜주면 된다.

 

현재 arr[x][y]인지 정확히는 몰라 설명하기가 애매하군요. 다른 블로그로 참조해서 작성했는데...  아무튼 저도 이거에 대해 많이 생각해 보겠습니다.

 

이거 말안했는지 기억안나는데... pair사용하지 않고, 두 개의 큐에 넣어도 된다.ㅎㅎ

 

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용
string board[102]; // '1'이 파란 칸, '0'이 빨간 칸에 대응
int dist[102][102]; // 해당 칸을 방문했는지 여부를 저장
int n,m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1}; // 상하좌우 네 방향을 의미
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for(int i = 0; i < n; i++)
    cin >> board[i];
  for(int i = 0; i < n; i++) fill(dist[i],dist[i]+m,-1);
  queue<pair<int,int> > Q;
  Q.push({0,0});
  dist[0][0] = 0;
  while(!Q.empty()){
    auto cur = Q.front(); Q.pop();
    for(int dir = 0; dir < 4; dir++){ // 상하좌우 칸을 살펴볼 것이다.
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir]; // nx, ny에 dir에서 정한 방향의 인접한 칸의 좌표가 들어감
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 범위 밖일 경우 넘어감
      if(dist[nx][ny] >= 0 || board[nx][ny] != '1') continue; // 이미 방문한 칸이거나 이동할 수 없는 칸일 경우
      dist[nx][ny] = dist[cur.X][cur.Y]+1; // (nx, ny)의 거리는 현재 보고 있는 위치의 거리 + 1
      Q.push({nx,ny});
    }
  }
  cout << dist[n-1][m-1]+1; // 문제의 특성상 거리+1이 정답
}

 

그렇다고 합니다. 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

[백준] 4963번 섬의 갯수  (0) 2020.05.05
[백준] 14405번 피카츄  (2) 2020.05.04
[백준] 1260번 DFS와 BFS  (0) 2020.05.03
[백준] 9086번 문자열  (0) 2020.04.30
[백준] 2089번 -2진수  (0) 2020.04.29

댓글

Designed by JB FACTORY