[2021.03.29] 코딩테스트 연습

DFS & BFS 강의

• isVisit처리 중요.
• DFS 스택을 사용해도 좋지만, 재귀함수를 이용하는 것이 생각이 편함.
• BFS는 Queue를 사용해, Queue가 빌때까지 동작...

음료수 얼려먹기 문제 풀이

DFS

#include <iostream>

using namespace std;

#define MAX_SIZE 5

int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
bool isVisit[MAX_SIZE][MAX_SIZE];
int map[MAX_SIZE][MAX_SIZE] = {
    {1, 1, 1, 1, 1},
    {0, 0, 1, 1, 0},
    {0, 0, 0, 1, 1},
    {1, 1, 1, 1, 1},
    {0, 0, 0, 0, 0},
};

bool isValidXY(int x, int y)
{
    if (x < 0)
        return false;
    if (y < 0)
        return false;
    if (x >= MAX_SIZE)
        return false;
    if (y >= MAX_SIZE)
        return false;

    if (map[x][y] == 1)
        return false;

    return true;
}

void dfs(int x, int y)
{
    isVisit[x][y] = true;
    int nx, ny;

    for (int i = 0; i < 4; i++) {
        nx = x + dx[i];
        ny = y + dy[i];
        if (isValidXY(nx, ny)) {
            if (isVisit[nx][ny] == false) {
                dfs(nx, ny);
            }
        }
    }
}

int main()
{
    int cnt = 0;
    for (int x = 0; x < MAX_SIZE; x++) {
        for (int y = 0; y < MAX_SIZE; y++) {
            if ((isVisit[x][y] == false) && (map[x][y] == 0)){
                cnt++;
                dfs(x, y);
            }
        }
    }

    cout << cnt << endl;

    return 0;
}

BFS

#include <iostream>
#include <queue>

using namespace std;

#define MAX_SIZE 5

int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
bool isVisit[MAX_SIZE][MAX_SIZE];
int map[MAX_SIZE][MAX_SIZE] = {
        {1, 1, 1, 1, 1},
        {0, 0, 1, 1, 0},
        {0, 0, 0, 1, 1},
        {1, 1, 1, 1, 1},
        {0, 0, 0, 0, 0},
};

bool isValidXY(int x, int y)
{
    if (x < 0)
        return false;
    if (y < 0)
        return false;
    if (x >= MAX_SIZE)
        return false;
    if (y >= MAX_SIZE)
        return false;

    if (map[x][y] == 1)
        return false;

    return true;
}

struct Point {
    int x, y;
};

void bfs(int x, int y)
{
    queue<Point> q;

    isVisit[x][y] = true;
    q.push({ x, y });

    while (q.empty() == false) {
        Point p = q.front();
        q.pop();

        int nx, ny;
        for (int i = 0; i < 4; i++) {
            nx = p.x + dx[i];
            ny = p.y + dy[i];
            if (isValidXY(nx, ny)) {
                if (isVisit[nx][ny] == false) {
                    isVisit[nx][ny] = true;
                    q.push({ nx, ny });
                }
            }
        }
    }
}

int main()
{
    
    int cnt = 0;
    for (int x = 0; x < MAX_SIZE; x++) {
        for (int y = 0; y < MAX_SIZE; y++) {
            if ((isVisit[x][y] == false) && (map[x][y] == 0)) {
                cnt++;
                bfs(x, y);
            }
        }
    }

    cout << cnt << endl;

    return 0;
}