무르르릉

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

코드

#include <iostream>
#include <cmath>
#include <queue>
#include <cstring>

#define MAX 101
#define X first
#define Y second

using namespace std;

char board[MAX][MAX];
bool visited[MAX][MAX];

int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };

int N, M;				// 가로, 세로
char color;				// 병사의 옷 색 
int white, blue, cnt;	// 해당 색상 병사의 위력, 병사의 수

queue<pair<int, int>> q;

int Bfs(int x, int y, char color)
{
	cnt = 1;
	q.push({ x, y });
    visited[x][y] = true;

	while (!q.empty())
	{
		pair<int, int> cur = q.front();
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = cur.X + dx[i];
			int ny = cur.Y + dy[i];

			if (nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
			if (board[nx][ny] != color || visited[nx][ny]) continue;

			q.push({ nx, ny });
			visited[nx][ny] = true;
			cnt++;
		}
	}
	
	// 병사의 수를 제곱하여 위력을 구하여 반환
	int power = pow(cnt, 2);
	return power;
}

int main()
{
    cin >> N >> M;

	for (int i = 0; i < M; i++)
	{
		cin >> board[i];
	}

	for (int i = 0; i < M; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (board[i][j] == 'W' && !visited[i][j])
			{
				color = board[i][j];
				white += Bfs(i, j, color);
			}
			
			else if (board[i][j] == 'B' && !visited[i][j])
			{
				color = board[i][j];
				blue += Bfs(i, j, color);
			}
		}
	}
	cout << white << ' ' << blue;
}

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

• memset(메모리, 변경하고 싶은 값, 길이): 메모리 초기화 함수로 어떤 메모리의 첫 위치에서부터 지정한 길이를 원하는 값으로 바꾼다. ex. 배열을 전부 초기화하고 싶을 때 sizeof(배열) 함수와 함께 사용

#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    int arr[5] = { 1,2,3,4,5 };

	for (int i = 0; i < 5; i++)
	{
		cout << arr[i] << " ";		// 1 2 3 4 5
	}

	cout << endl;

	memset(arr, 0, sizeof(arr));

	for (int i = 0; i < 5; i++)
	{
		cout << arr[i] << " ";		// 0 0 0 0 0
	}
}

코드

#include <iostream>
#include <queue>
#include <cstring>

#define X first
#define Y second
#define MAX 51

using namespace std;

int board[MAX][MAX];
bool visited[MAX][MAX];

int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };

// T: 테스트 케이스 개수, M: 가로, N: 세로, K: 배추 개수
int T, M, N, K;

queue<pair<int, int>> q;

void Bfs(int x, int y)
{
    q.push({ x, y });
    visited[x][y] = true;

    while (!q.empty())
    {
        pair<int, int> cur = q.front();
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = cur.X + dx[i];
            int ny = cur.Y + dy[i];

            // 배열 벗어나면 탐색 안 함
            if (nx < 0 || nx >= N || ny < 0 || ny >= M)
                continue;
            
            // 배추 없거나 이미 방문한 곳은 탐색 안 함
            if (board[nx][ny] != 1 || visited[nx][ny]) 
                continue;

            // 그 외 인접한 공간에 배추 있으면 큐에 넣고 방문 처리
            q.push({ nx, ny });
            visited[nx][ny] = true;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> T;
    
    for (int i = 0; i < T; i++)
    {
        cin >> M >> N >> K;
        // 배열 초기화
        memset(board, 0, sizeof(board));
        memset(visited, false, sizeof(visited));

        // 배추가 있는 좌표값 입력 받기
        for (int i = 0; i < K; i++)
        {
            int x, y;
            cin >> x >> y;
            board[y][x] = 1;
        }

        // 지렁이의 수
        int cnt = 0;

        // 배열 탐색하며 배추가 있고 방문하지 않았다면 BFS 실행
        for (int n = 0; n < N; n++)
        {
            for (int m = 0; m < M; m++)
            {
                if (board[n][m] == 1 && !visited[n][m])
                {
                    Bfs(n, m);
                    cnt++;  // 한 배추 구역의 탐색이 종료되면 지렁이 수 1 증가
                }
            }
        }

        /*for (int n = 0; n < N; n++)
        {
            for (int m = 0; m < M; m++)
            {
                cout << board[n][m] << ' ';
            }
            cout << endl;
        }*/

        // 구역의 수 출력
        cout << cnt << "\n";
    }
}

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

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;
#define MAX 1001

int N, M, V;            // N: 정점, M: 간선, V: 시작 정점 번호
vector<int> vec[MAX];   // 인접 리스트
bool visited[MAX];      // 정점 방문 체크
queue<int> q;
stack<int> s;

// 재귀 함수 사용
void DFS_Recursion(int v)
{
    visited[v] = true;
    cout << v << " ";

    // vec[v]와 연결된 수만큼 반복
    for (int i = 0; i < vec[v].size(); i++)
    {
        int next = vec[v][i];
        if (visited[next] == false)
        {
            DFS_Recursion(next);
        }
    }
}

// 스택 사용
void DFS(int v)
{
    s.push(v);

    while (!s.empty())
    {
        // 가장 위에 있는 요소 저장하고 빼기
        v = s.top();
        s.pop();

        if (visited[v]) continue;
        visited[v] = true;
        cout << v << " ";  

        // vec[v]와 연결된 수만큼 반복
        for (int i = 0; i < vec[v].size(); i++)
        {
            // 스택의 선입후출 특징 때문에 역순으로 넣어주기 
            int next = vec[v][vec[v].size() - 1 - i];
            if (visited[next] == false)
            {
                if (visited[next]) continue;
                s.push(next);
            }
        }
        
    }
}

void BFS(int v)
{
    // 현재 정점을 큐에 넣고 방문처리
    q.push(v);
    visited[v] = true;

    while (!q.empty())
    {
        // 가장 앞에 있는 요소 저장하고 빼기
        v = q.front();
        q.pop();
        cout << v << " ";  

        for (int i = 0; i < vec[v].size(); i++)
        {
            int next = vec[v][i];
            if ( visited[next] == false)
            {
                q.push(next);
                visited[next] = true;
            }
        }
    }
}

// 방문 처리 초기화 함수
void ResetVisited()
{
    for (int i = 1; i <= N; i++)
        visited[i] = false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M >> V;

    for (int i = 0; i < M; i++)
    {
        int from, to;
        cin >> from >> to;
        vec[from].push_back(to);
        vec[to].push_back(from);
    }

    // 오름차순 정렬 - 작은 숫자부터 방문해야 하기 때문이다
    for (int i = 1; i <= N; i++)
        sort(vec[i].begin(), vec[i].end());

    ResetVisited();
    DFS(V);

    cout << '\n';

    ResetVisited();
    BFS(V);
}