문제

• n*m 크기의 미로에서 1은 이동가능 0은 이동불가능이다.
• 해당 미로가 주어졌을 떄 (1,1)에서 출발하여 (N,M)의 위치로 이도앟ㄹ 떄 지나야 하는 최소 칸의 개수를 구하여라.

예제 입력

4 6
101111
101010
101011
111011

예제 출력

15

풀이

풀이 1

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
2. 큐에서 원소를 꺼내어 그 칸에 인접한 상하좌우 칸에 대해 3번을 진행
3. 해당 칸을 이전에 방문했다면 continue, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
4. 큐가 빌 때까지 2번 반복

** 문제에서 미로의 수가 붙어서 입력으로 주어진다는 것을 간과했다.
각 int형으로 입력되는 것이 아니기 때문에 연속된 string으로 입력을 받아 하나씩 잘라서 써야한다.

입력을 int형 pair에서 string한줄로 바꿨다.

이전에 중첩 for문을 돌려서 i, j 인덱스에 접근했는데, string으로 입력을 받았기 때문에 바로 원하는 인덱스에 접근할 수 있다.
또한 이전 문제(1926 그림)는 모든 인덱스에 접근하면서 연결되어있는 1의 개수를 더하는 문제, 즉 넓게 퍼져가는 문제였다면 이 미로탐색 문제는 최단거리, (n,m)에 도달하면 되는, 최소
아 차이점을 알듯말듯 아리송

이 문제는 방문 여부만을 활용하는 문제인 반면 그림문제는 방문여부를 활용하여 그림의 크기와 그림의 개수를 구하는 문제이기 때문에 중첩 for문을 돌리지 않는것

101111
101010
101011
111011 => 15

101111
111010
101011
111011 => 11

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

string board[102]; //미로
int dist[102][102]; //거리 저장

//아래 오른쪽 위 왼쪽
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);
    
    int n, m;
    cin >> n>>m;
    
    for(int i=0; i<n; i++)
        cin >> board[i];
   
   //1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김 = 거리를 남김
    queue<pair<int, int>> Q;
    Q.push({0,0}); //첫시작 큐에 집어넣기
    dist[0][0]=1; //첫번째 인덱스 거리를 시작점으로부터 1로 설정 
    //왜? 방문을 아예 안한 0이랑 구분하기 위해서
    
    while(!Q.empty()){
        //큐에서 원소를 꺼내서 그 칸에 인접한 상하좌우 칸에 대해 3번 진행
        auto current = Q.front(); //{0,0}
        Q.pop();
        
        for(int dir = 0; dir<4; dir++){
            int next_x = current.X + dx[dir];
            int next_y = current.Y + dy[dir];
            
            if(next_x <0 || next_x>=n|| next_y<0 || next_y>=m) continue;
            if(dist[next_x][next_y] || board[next_x][next_y]!='1')continue;
            dist[next_x][next_y] = dist[current.X][current.Y]+1;
            
            Q.push({next_x, next_y});
        }
    }
    cout << dist[n-1][m-1];
}