[코드트리 챌린지] 2주차 BFS - BFS 탐색 / 갈 수 있는 곳들

 

https://www.codetree.ai/missions/2/problems/places-can-go/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드:

#include <bits/stdc++.h>
using namespace std;

int n, k;
int arr[105][105]; // 영역 저장
bool visited[105][105]; // 방문 확인
queue <pair<int, int>> q; // BFS용 큐
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int cnt;

bool InRange(int nx, int ny) {
    return (0 <= nx && nx < n && 0 <= ny && ny < n);
}

bool Cango(int nx, int ny) {
    if (!InRange(nx, ny)) return false;
    if (arr[nx][ny] == 1) return false;
    if (visited[nx][ny]) return false;

    return true;
}

void BFS() {
    // 큐에서 차례대로 빼내어 인접한 부분을 다시 큐에 넣음
    // 큐가 빌 때 까지 반복한다.
    while (!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();

        int x = p.first;
        int y = p.second;
        for (int dirNum = 0; dirNum < 4; dirNum++) {
            int nx = x + dx[dirNum];
            int ny = y + dy[dirNum];

            if (Cango(nx, ny)) {
                visited[nx][ny] = true;
                q.push(make_pair(nx,ny));
            }
        }
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }

    int x, y;
    for (int i = 0; i < k; i++) {
        cin >> x >> y;
        if (Cango(x-1, y-1)) {
            visited[x - 1][y - 1] = true;
            q.push(make_pair(x - 1, y - 1));
            BFS();
        }
    }
    
    cout << cnt;
}

기존과 BFS 진행 자체는 동일합니다.

x,y를 입력 받을 때 마다 이 위치가 갈 수 있는 곳인지, 이미 방문한 곳인지 꼭 체크합니다.

Cango()가 true라면 visited를 true로 만들고 pair를 만들어 큐에 삽입시킨 후 BFS를 실행합니다.

입력받은 곳을 모두 큐에 넣고 이후에 BFS를 하지 않는 이유는 먼저 입력받은 위치에 의해
나중에 입력받은 위치가 이미 방문한 곳일 경우 cnt가 중복으로 올라갈 수 있기 때문입니다.