[백준/C++] 2178번_미로 탐색

문제는 다음과 같습니다.

이 문제는, bfs로 접근해서
시작점으로부터 길이 있는(a[i][j]==1) 지점까지의 거리를 +1씩 갱신한 후,
도착점까지의 최단 거리를 찾으면 됩니다

그리고 bfs이므로, queue 자료구조를 이용하여 구현하였습니다.
stl의 queue를 가져와서 이용하였구요,
queue에 저장해야하는 값은 2차원 배열의 인덱스 값과 해당 배열까지의 거리, 즉 3가지 입니다.

pair를 중첩해서 이용하였고, 내부의 pair에는 2차원 배열의 인덱스 값을 넣어주었습니다.

➡️pair<pair<int, int>, int>> p;

전체 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int a[102][102]={0, };
    int ch[102][102]={0, };
    queue<pair<pair<int, int>, int>> q;
    int n, m, res, tmp;

    cin>>n>>m;
    for(int i=1; i<=n; i++){
      string s;
      cin>>s;
      for(int j=0; j<s.size(); j++){
        if(s[j]=='0') a[i][j+1]=0;
        else a[i][j+1]=1;
      }
    } // 배열 입력 완료

    tmp=1;
    ch[1][1]=1;
    q.push({{1,1}, tmp});
    
    // bfs 수행
    while(!q.empty()){
      pair<pair<int, int>, int> p = q.front(); q.pop();
      int i = p.first.first; int j = p.first.second;
      tmp = p.second;
      if(i==n && j==m){
        res=p.second;
        break;
      }

      if(a[i+1][j]==1 && ch[i+1][j]==0){
        ch[i+1][j]=1;
        q.push({{i+1, j}, tmp+1});
      }
      if(a[i-1][j]==1 && ch[i-1][j]==0){
        ch[i-1][j]=1;
        q.push({{i-1, j}, tmp+1});
      }
      if(a[i][j+1]==1 && ch[i][j+1]==0){
        ch[i][j+1]=1;
        q.push({{i, j+1}, tmp+1});
      }
      if(a[i][j-1]==1 && ch[i][j-1]==0){
        ch[i][j-1]=1;
        q.push({{i, j-1}, tmp+1});
      }
    }

    cout<<res<<endl;
    return 0;
}

2/19 토요일 복습)

#include <bits/stdc++.h>
using namespace std;

int a[102][102]={0, }; int ch[102][102]={0, };
int n, m, res=200;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin>>n>>m;
  for(int i=1; i<=n; i++){
    string str; cin>>str;
    for(int j=0; j<str.size(); j++){
      if(str[j]=='0') a[i][j+1]=0;
      else a[i][j+1]=1;
    }
  }

  queue<pair<pair<int, int>, int>> q;
  ch[1][1]=1; q.push({{1, 1}, 1});
  while(!q.empty()){
    pair<pair<int, int>, int> p = q.front(); q.pop();
    int t1 = p.first.first; int t2 = p.first.second; int dis = p.second;
    if(t1==n && t2==m) { res=dis; break; }

    if(a[t1+1][t2]==1 && ch[t1+1][t2]==0){
      ch[t1+1][t2]=1; q.push({{t1+1, t2}, dis+1});
    }
    if(a[t1][t2+1]==1 && ch[t1][t2+1]==0){
      ch[t1][t2+1]=1; q.push({{t1, t2+1}, dis+1});
    }
    if(a[t1-1][t2]==1 && ch[t1-1][t2]==0){
      ch[t1-1][t2]=1; q.push({{t1-1, t2}, dis+1});
    }
    if(a[t1][t2-1]==1 && ch[t1][t2-1]==0){
      ch[t1][t2-1]=1; q.push({{t1, t2-1}, dis+1});
    }
  }
  
  cout<<res<<endl;
  return 0;
}