[백준2178][c++] 미로 찾기

문제 출처:

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

2178번: 미로 탐색

 

소스 코드:

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>

using namespace std;

int n,m;
char map[101][101]; // 미로를 입력받을 배열
bool visited[101][101] = {false,}; // 방문 확인 배열
int check[101][101] = {0,}; // 칸을 세기 위한 배열
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void bfs(int a, int b);

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

  cin >> n >> m;

  for(int i=0; i<n; i++){
    string str="";
    cin >> str;
    for(int j=0; j<m; j++){
      char tmp=str[j];
      map[i][j] = tmp;
    }
  }

  bfs(0,0);

  /*
  //출력 테스트
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      cout << check[i][j] <<" ";
    }cout << "\n";
  }
  */
  int ans= check[n-1][m-1] + 1; // 칸을 셀 때, 시작/도착 위치를 포함해서 세기 때문에 ( )+1
  cout << ans;

  return 0;
}
void bfs(int a, int b){
  visited[a][b] = true; // 시작점인 0,0을 방문
  queue<pair<int, int>> q; // queue 선언

  q.push(make_pair(a,b)); // 시작점(0,0)을 큐에 push

  while(!q.empty()){
    int x = q.front().first;
    int y = q.front().second; // x,y 추출

    q.pop(); // 추출했으니 front q 삭제

    for(int i=0; i<4; i++){ // 인접한 주변 상하좌우 4칸씩 탐색)
      int nx = x+dx[i];
      int ny = y+dy[i];

      if(0<= nx && nx < n && 0<=ny && ny<m){ // 미로를 벗어나지 않는 조건에서
        if (map[nx][ny] == '1' && visited[nx][ny]==0){ // map[][]=='1' "길" 이면서 && 방문하지 않았던 노드면
          check[nx][ny] = check[x][y] + 1; // (x,y) -> (nx,ny) 이동 거리(1)를 현재 탐색 좌표(nx,ny)의 check 배열에 더한다
          visited[nx][ny]=1; // 방문 배열 true

          q.push(make_pair(nx,ny)); // 큐에 현재 칸을 push하기
        }
      }
    }
  }
}

 

 

문제 해결:

맵을 입력받을 때, 공백없이 연속된 수를 입력 받으므로

 

int map[101][101] 이 아닌

char map[101][101] 문자형으로 선언 후 

(int )0, 1 이 아닌

(char) '0' , '1' 으로 접근 및 처리해야 한다.

 

이에 대한 시행착오는 아래 스크린샷 첨부