[코드트리] BFS 탐색 / 갈 수 있는 곳들

갈 수 있는 곳들

숫자 0, 1로만 이루어진 n * n 격자가 주어졌을 때, k개의 시작점으로부터 상하좌우 인접한 곳으로만 이동하여 도달 가능한 칸의 수를 구하는 프로그램을 작성해보세요. 숫자 0은 해당 칸이 이동할 수 있는 곳임을, 숫자 1은 해당 칸이 이동할 수 없는 곳임을 의미합니다.

입력 형식

첫 번째 줄에는 격자의 크기를 나타내는 n과 시작점의 수를 나타내는 k 값이 공백을 사이에 두고 주어집니다.

두 번째 줄 부터는 n개의 줄에 걸쳐 각 행에 해당하는 n개의 숫자가 순서대로 공백을 사이에 두고 주어집니다.

그 다음 줄 부터는 k개의 줄에 걸쳐 각 시작점의 위치 (r, c)가 공백을 사이에 두고 주어집니다. (r, c)는 r행 c열 위치가 시작점 중 하나임을 의미합니다. 모든 시작점의 위치에 적혀있는 숫자는 0이고, 시작점끼리 서로 겹치지 않게 주어진다고 가정해도 좋습니다. (1 ≤ r ≤ n, 1 ≤ c ≤ n)

• 1 ≤ n ≤ 100
• 1 ≤ k ≤ n * n

출력 형식

시작지점으로부터 방문이 가능한 서로 다른 칸의 수를 출력합니다.

---

나의 풀이

#include <iostream>
#include <queue>
using namespace std;

int n; int k;
int mat[101][101]={0,};
int visited[101][101] = {0,};
int cnt=0;

bool CanGo(int r, int c){
    if(r>n || c>n || r<1 || c<1) return false;
    if(visited[r][c]==1) return false;
    if(mat[r][c]==1) return false;
    return true;
}

int bfs(int r, int c){
    int dx[4] = {1,0,-1,0};
    int dy[4] = {0,1,0,-1};
    queue<pair<int,int> > q;
    q.push(make_pair(r,c));
    if(visited[r][c]==0) cnt++;
    visited[r][c]=1;
    while(!q.empty()){
        pair<int,int> a = q.front(); // 여기서 큐의 첫 pair를 저장해놓고
        q.pop();
            for(int i=0; i<4; ++i){
                int nr = a.first +dx[i]; // 첫 pair였던 값에서 이동시켜야함.!!
                int nc = a.second +dy[i];
                if(CanGo(nr, nc)){
                    q.push(make_pair(nr,nc));
                    visited[nr][nc] = 1;
                    cnt++;
                }
            }
    }

}

int main() {
    cin >> n>>k;
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=n; ++j) cin>>mat[i][j];
    }
    int r; int c;
    for(int i=0; i<k; ++i){
        cin>>r>>c;
        bfs(r, c);
    }
    cout << cnt;
    return 0;
}

 

해설 안보고 풀어냈따