BOJ : 2178 미로탐색 (C++)

김정욱·2020년 10월 27일
0

Algorithm - 문제

목록 보기
24/249
post-custom-banner

문제

Code

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

char board[102][102];
int dist[102][102];
#define X first
#define Y second
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    queue<pair<int,int>> Q;
    cin >> N >> M;

    for(int i=0;i<N;i++)
    {
        cin >> board[i];
        fill(dist[i],dist[i]+M,-1);
    }
    dist[0][0] = 1;
    Q.push({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];
            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;
            Q.push({nx,ny});
        }
    }
    cout << dist[N-1][M-1];
}
  • 방문을 표시하는 vis[][] 대신 거리를 계산하는 dist[][]사용
  • dist[][]를 최초 -1로 초기화 하기 위해 for문 + fill 사용
  • pair<int,int> cur; --> auto cur; 로 사용 가능
profile
Developer & PhotoGrapher
post-custom-banner

0개의 댓글