맵을 탐색하며 최단 거리를 찾는 문제이다.

이차원 배열로 그래프를 구현한다. 그래프의 가중치가 전부 동일하므로 BFS를 활용해 최단거리를 찾으면된다.

1. 풀이

#include <bits/stdc++.h>

using namespace std;
int a[104][104];
int visited[104][104]; 
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};
int n,m;

void BFS(int y, int x) {
    visited[y][x]=1;
    queue<pair<int,int>> q;
    q.push({y,x});
    int ny,nx;
    while((int)q.size()) {
        tie(y,x)=q.front(); q.pop();
        for(int i=0;i<4;i++) {
            ny = y + dy[i];
            nx = x + dx[i];
            if(ny <0 || nx <0|| ny >= n || nx >= m) continue;
            if(a[ny][nx]==0) continue;
            if(visited[ny][nx]) continue;
            visited[ny][nx] = visited[y][x] + 1;
            q.push({ny,nx});
        }    
    } 
}
int main() {
    string s;
    cin >> n >> m;
    for(int i=0;i<n;i++) { //O(m*n)
        cin >> s;
        for(int j=0;j<m;j++) {
            a[i][j]=s[j]-'0';
        }
    } 
    BFS(0,0);
    cout << visited[n-1][m-1];
    return 0;
}

중요한 것은
(1) queue 에 2차원 좌표 저장을 위해 pair<int,int>를 넣어야한다는 것
(2) a[ny][nx]==0로 인덱스 기반 배열 접근전에 if(ny <0 || nx <0|| ny >= n || nx >= m) continue; 로 인덱스가 지정된 범위를 벗어나는지 확인해줘야한다는 것. (순서가 중요하다는 의미이다)

정도이다.