무르르릉

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

9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

3

9
8 6
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

-1

풀이

• 그래프가 연결되어 있을 경우 dfs를 실행하고 찾으려고 한 정점에 다다랐을 때 실행횟수를 저장하여 출력

코드

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

#define MAX 101

vector<int> vec[MAX];
bool visited[MAX];

int n, m, person1, person2;
int result = -1;

void Dfs(int vertex1, int vertex2, int cnt)
{
	visited[vertex1] = true;

	// 찾으면 횟수 저장
	if (vertex1 == vertex2)
	{
		result = cnt;
		return;
	}

	for (int i = 0; i < vec[vertex1].size(); i++)
	{
		int next = vec[vertex1][i];
		
		if (!visited[next])
		{
			Dfs(next, vertex2, cnt + 1);
		}
	}
}

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

	cin >> n >> person1 >> person2 >> m;

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

	memset(visited, 0, sizeof(visited));
	Dfs(person1, person2, 0);
	cout << result;

	return 0;
}

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

4 6
101111
101010
101011
111011

15

4 6
110110
110110
111111
111101

9

2 25
1011101110111011101110111
1110111011101110111011101

38

7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

13

풀이

• 미로가 주어졌을 때 갈 수 있는 곳이 있을 때마다 이동 횟수를 증가시키면 되는 문제이다.
• 시작점이 주어져있기 때문에 가장 첫 번째 칸의 좌표를 넘겨 BFS 탐색을 진행한다.

코드

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

using namespace std;

#define MAX 101
#define _X first
#define _Y second

int maze[MAX][MAX];
int visited[MAX][MAX];

int N, M;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
queue<pair<int, int>> q;

void Bfs(int x, int y)
{
	visited[x][y] = 1;

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

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

			// 범위 벗어나거나 지나갈 수 없는 곳, 방문한 곳은 처리 X
			if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
			if (maze[nx][ny] == 0 || visited[nx][ny] != 0) continue;
			q.push({ nx, ny });
			visited[nx][ny] = visited[curX][curY] + 1;
		}
	}

	// (N, M)에 도달했을 때의 값 출력
	cout << visited[N - 1][M - 1];
}

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

	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		string str;
		cin >> str;
		for (int j = 0; j < M; j++)
		{
			maze[i][j] = str[j] - '0';
		}
	}

	memset(visited, 0, sizeof(visited));

	q.push({ 0, 0 });
	Bfs(0, 0);

	return 0;
}

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

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

7
6
1 2
2 3
1 5
5 2
5 6
4 7

4

풀이

• 벡터 이용하여 인접리스트 구현 후 DFS 실행

코드

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

#define MAX 101

vector<int> vec[MAX];	// 인접리스트
bool visited[MAX];		// 방문처리 배열

int comp, edge, cnt;

// 재귀 DFS 사용
void Dfs(int v)
{
	visited[v] = true;	// 방문처리
	
	// 컴퓨터와 연결되어 있는 수만큼 반복하고 카운트 증가
	for (int i = 0; i < vec[v].size(); i++)
	{
		int next = vec[v][i];

		if (visited[next] == false)
		{
			Dfs(next);
			cnt++;
		}
	}
}

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

	cin >> comp;
	cin >> edge;

	// 인접 리스트에 값 집어넣기
	for (int i = 0; i < edge; i++)
	{
		int from, to;
		cin >> from >> to;

		vec[from].push_back(to);
		vec[to].push_back(from);
	}

	// 방문 배열 초기화 후 DFS 실행
	memset(visited, 0, sizeof(visited));
	Dfs(1);
	cout << cnt;;

	return 0;
}

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

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

5 3 1
0 -1 0 0 0
-1 -1 0 1 1
0 0 0 1 1

-1

5 3 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0

4

4 3 2
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
-1 -1 -1 -1
1 1 1 -1

0

코드

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

using namespace std;

#define MAX 101

#define _X first.first	
#define _Y first.second
#define _Z second

int board[MAX][MAX][MAX];

int M, N, H;	// 가로, 세로, 높이
int temp = 0;
int day = 0;

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

queue<pair<pair<int, int>, int>> q;		// {{M, N}, H} 저장

void Bfs()
{
	while (!q.empty())
	{
		pair<pair<int, int>, int> cur = q.front();
		int x = cur._X;
		int y = cur._Y;
		int z = cur._Z;
		q.pop();

		for (int i = 0; i < 6; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			int nz = z + dz[i];

			// 범위를 벗어나거나, 토마토가 존재하지 않을 경우 무시
			if (nx < 0 || nx >= N || ny < 0 || ny >= M || nz < 0 || nz >= H) continue;
			if (board[nx][ny][nz] == -1) continue;

			// 익은 토마토 근처에 익지 않은 토마토가 존재할 경우 큐에 담고 
			if (board[nx][ny][nz] == 0)
			{
				q.push({ {nx, ny}, nz });
				board[nx][ny][nz] = board[x][y][z] + 1;
			}
		}
	}
}

// 현재 배열에 담긴 토마토의 상태를 확인한다.
// 배열에 0이 있을 경우에 익지 않은 토마토가 존재한다는 뜻이다.
// 그 외는 일수를 출력한다.
void CheckBoard()
{
	for (int h = 0; h < H; h++)
	{
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				// 만약 익지 않은 토마토가 존재할 경우 -1을 출력한다.
				if (board[i][j][h] == 0)
				{
					cout << -1;
					return;
				}

				// 현재 배열의 값 저장하여 최소 일수를 저장한 값과 비교
				// 만약 현재 배열 값(temp)가 크면 day에 값 덮어씌움
				temp = board[i][j][h];

				if (day < temp)
					day = temp;
			}
		}
	}
	// 익은 토마토가 1이기 때문에 일수를 구하기 위해서는 1을 빼줘야 한다.
	cout << day - 1;
}

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

	cin >> M >> N >> H;

	// 3차원 배열 입력
	for (int h = 0; h < H; h++)
	{
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				cin >> board[i][j][h];
			}
		}
	}

	// 익은 토마토가 있으면 해당 위치값을 큐에 저장한다.
	for (int h = 0; h < H; h++)
	{
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				if (board[i][j][h] == 1)
				{
					q.push({ { i, j }, h });
				}
				
			}
		}
	}

	Bfs();
	CheckBoard();

	return 0;
}

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

풀이

• bfs를 실행하게 되면 배열을 해당 모습으로 값이 변한다.

• 1(익은 토마토)가 담겨있는 곳을 큐에 담는다.
• 주변에 0(익지 않은 토마토)이 존재할 때  하루 지났다는 의미로 해당 위치에 1을 증가시킨 값을 집어넣는다.
• 배열에 있는 최대값을 저장하여 1을 빼준 값이 토마토가 모두 익은 날이 된다.

코드

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

using namespace std;

#define MAX 1001
#define _X first
#define _Y second

int board[MAX][MAX];

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

int M, N;	// 가로, 세로
int maxDay = 0;
int day = 0;

queue<pair<int, int>> q;

void Bfs()
{
	while (!q.empty())
	{
		pair<int, int> cur = q.front();
		int x = cur._X;
		int y = cur._Y;

		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;	// 범위를 벗어났다면
			if (board[nx][ny] == -1) continue;						// 토마토가 없다면

			// 익지 않은 토마토가 있을 경우, 
			if (board[nx][ny] == 0)
			{
				board[nx][ny] = board[x][y] + 1;
				q.push({ nx, ny });
			}
		}
	}
}

// 익지 않은 토마토가 있는지 확인하고 모두 익었으면 일수 출력
void CheckBoard()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			// 익지 않은 토마토가 있을 때는 -1 출력 후 for문 탈출
			if (board[i][j] == 0)
			{
				cout << -1;
				return;
			}
			// 배열의 값을 저장하는 day 변수가 최대 일수보다 크다면 바꿔준다.
			day = board[i][j];
			if (maxDay < day)
				maxDay = day;
		}
	}
	// 익은 토마토가 1이기 때문에 일수를 구하기 위해서는 1을 빼줘야 한다.
	cout << maxDay - 1;
}

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

	// 가로, 세로 입력
	cin >> M >> N;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			// 배열 입력
			cin >> board[i][j];
		}
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (board[i][j] == 1)
			{
				// 익은 토마토가 있으면 큐에 넣음
				q.push({ i, j });
			}
		}
	}

	Bfs();
	CheckBoard();

	return 0;
}

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

10 1 10 2 1

6

100 2 1 1 0

use the stairs

Code

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

using namespace std;

#define MAX 1000001
#define _X first
#define _Y second

int visited[MAX];

int F;		// 꼭대기 층
int S;		// 강호가 있는 층
int G;		// 이동하려는 층
int U, D;	// 위로 몇 층? 아래로 몇 층?

queue<int> q;

void Bfs()
{
	q.push(S);
	visited[S] = 0;

	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		
		// 도착했으면 이동횟수 출력
		if (cur == G)
		{
			cout << visited[cur];
			return;
		}

		for (int i = 0; i < 2; i++)
		{
			// 아래, 위 방향 벡터
			int dir[2] = { -D, U };
			int next = cur + dir[i];

			// 1층 미만/최상층 이상, 방문한 곳이라면 무시한다.
			if (next <= 0 || next > F || visited[next] != -1) continue; 
			// 이동 횟수를 증가시켜 값을 저장시킨다.
			visited[next] = visited[cur] + 1;
			q.push(next);
		}
	}
	// 이동하려는 층에 도달하지 못했을 경우 출력된다.
	cout << "use the stairs";
}

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

	cin >> F >> S >> G >> U >> D;
	
	// 방문 처리를 위해 전부 -1로 초기화한다.
	memset(visited, -1, sizeof(visited));

	Bfs();

	return 0;
}

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

• *max_element(vector<int> first, vector<int> last): 벡터가 가지고 있는 요소 중 가장 큰 값을 참조한다. 가장 작은 값을 받아오고 싶을 경우 '*min_element'를 사용하면 된다.

사용 예시

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    vector<int> v;

    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);

    int maxIdx = max_element(v.begin(), v.end()) - v.begin();
    int max = *max_element(v.begin(), v.end());

    int minIdx = min_element(v.begin(), v.end()) - v.begin();
    int min = *min_element(v.begin(), v.end());

    cout << "최대값의 인덱스: " << maxIdx << endl;
    cout << "최대값: " << max << endl;
    cout << "최소값의 인덱스: " << minIdx << endl;
    cout << "최소값: " << min << endl;
}

// 결과
//최대값의 인덱스: 4
//최대값: 50
//최소값의 인덱스: 0
//최소값: 10

코드

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAX 100
#define _X first
#define _Y second

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

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

int N;
int maxHeight = -1;     // 최대 높이 초기화

vector<int> vecArea;    // 각 높이에 대한 영역의 수 저장

void Dfs(int x, int y, int h)
{
    visited[x][y] = true;

    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
        if (visited[nx][ny] || board[nx][ny] <= h) continue;
        visited[nx][ny] = true;
        Dfs(nx, ny, h);
    }
}

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

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            // 배열 입력
            cin >> board[i][j];
            
            // 최대 높이 저장
            if (maxHeight < board[i][j])
                maxHeight = board[i][j];
        }
    }

    int area = 0;
    int maxArea = 0;

    // 높이가 1부터 최대 높이의 횟수만큼 물에 잠기지 않는 구역을 탐색
    for (int h = 1; h <= maxHeight; h++)
    {
        // 방문 배열 초기화
        memset(visited, false, sizeof(visited));

        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (board[i][j] > h && !visited[i][j])
                {
                    Dfs(i, j, h);
                    area++;
                }
            }
        }
        
        // 모든 높이에 대해 잠기지 않는 영역을 벡터에 저장
        vecArea.push_back(area);

        // 아무 지역도 물에 잠기지 않았을 경우 1로 세팅
        if (area == 0) vecArea.push_back(1);

        // 영역 초기화
        area = 0;
    }

    // 벡터 컨테이너의 최대값 구함
    int max = *max_element(vecArea.begin(), vecArea.end());
    cout << max;

    return 0;
}

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

• 적록색약인 사람은 붉은색과 초록색을 같은 색으로 보기 때문에 기존에 입력했던 2차원 배열에서 'G' 값을 'R'로 변경하여 한번 더 BFS를 실행하였음

코드

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

using namespace std;

#define MAX 101
#define _X first
#define _Y second

char board[MAX][MAX];
bool visited[MAX][MAX];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

int N;
char color;
int rgbCount, colorBlindCount;

void Bfs(int x, int y, char color)
{
    queue<pair<int, int>> q;
    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 (board[nx][ny] != color || visited[nx][ny]) continue;
            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;

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

// bfs 실행하여 총 그림 영역의 수를 반환하는 함수이다.
int GetCount(char arr[][MAX])
{
    int cnt = 0;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            color = arr[i][j];
            if (!visited[i][j] && arr[i][j] == color)
            {
                Bfs(i, j, color);
                cnt++;  
            }
        }
    }

    return cnt;
}

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

    // 크기 입력
    cin >> N;

    // 그림 입력
    for (int i = 0; i < N; i++)
    {
        string str;
        cin >> str;
        for (int j = 0; j < N; j++)
        {
            board[i][j] = str[j];
        }
    }

    // 적록색약이 아닌 사람이 보는 그림 영역의 수 구하기
    rgbCount = GetCount(board);

    // 방문 배열 초기화
    memset(visited, false, sizeof(visited));

    // 적록색약인 사람은 붉은색=초록색으로 인식하기 때문에
    // 초록색 그림이 위치한 곳을 붉은색 그림으로 변경
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (board[i][j] == 'G')
                board[i][j] = 'R';
        }
    }

    // 적록색약인 사람이 보는 그림 영역의 수 구하기
    colorBlindCount = GetCount(board);

    // 출력
    cout << rgbCount << ' ' << colorBlindCount;
}