[ 백준 ] 1261번 - 알고스팟 (C++)

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

1261번: 알고스팟

 

 

[ 문제풀이 ]

 

1. visited [ 100 ][ 100 ] 배열을 만들어서 방문 여부를 저장합니다.

 

2. 0-1 너비 우선 탐색을 통해 빈 에 들어가면 deque의 front에 push 하고, 벽을 부시면 deque의 back에 push 하고 cnt + 1을 해줍니다.

 

3. (N - 1,M - 1) 좌표에 도착하면 cnt를 출력합니다.

 

[ 소스코드 ]

#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
char arr[101][101];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int visited[100][100];
 
struct node {
    int y;
    int x;
    int cnt;
};
 
int main()
{
    deque<node> deq;
    scanf("%d %d", &M, &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%s", &arr[i]);
    }
 
    deq.push_back({ 0,0,0 });
    visited[0][0] = 1;
 
    while (!deq.empty()) {
        const int y = deq.front().y;
        const int x = deq.front().x;
        const int cnt = deq.front().cnt;
        deq.pop_front();
 
        if (y == N - 1 && x == M - 1) {
            printf("%d", cnt);
            return 0;
        }
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
                if (visited[yy][xx] != 1) {
                    visited[yy][xx] = 1;
                    if (arr[yy][xx] == '0') {
                        deq.push_front({ yy,xx,cnt });
                    }
                    else {
                        deq.push_back({ yy,xx,cnt + 1 });
                    }
                }
            }
        }
    }
}