백준 : DFS, BFS 기본문제

1260. (DFS와 BFS) 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
vector<int>graph[1001];
int n, m, v;
bool visited1[1001];
bool visited2[1001];
void dfs(int x) {
	visited1[x] = 1;
	cout << x << ' ';
	for (int i = 0; i < graph[x].size(); i++)
	{
		int y = graph[x][i];
		if (!visited1[y])
			dfs(y);
	}
}
void bfs(int start) {
	queue <int> q;
	q.push(start);
	visited2[start] = 1;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		cout << x << ' ';
		for (int i = 0; i < graph[x].size(); i++)
		{
			int y = graph[x][i];
			if (!visited2[y]) {
				visited2[y] = 1;
				q.push(y);
			}
		}
	}
}

int main() {
	cin >> n >> m >> v;	
	
	for (int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	for (int i = 1; i <= n; i++)
	{
		if (graph[i].size() > 0) {
			sort(graph[i].begin(), graph[i].end());
		}
	}
	dfs(v);
	cout << '\n';
	bfs(v);
}

dfs, bfs를 공부했다면 간단하게 풀 수 있는 문제이다. 

https://shine-slowly.tistory.com/48

알고리즘 : DFS와 BFS (1) - DFS (C++로 구현)

DFS와 BFS에 대한 이해가 부족하다고 느낀다면 위 포스팅을 추천합니다.

 

 

 

1303. (전쟁 - 전투) 전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다. N명이 뭉쳐있을 때는 N2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
char graph[101][101];
int n, m;
bool visited[101][101];
int result;
void reset() {
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			visited[i][j] = 0;
		}
	}
}
void dfs(int row, int col, char color) {
	if (row <= 0 || row > m || col <= 0 || col > n)
		return;
	if (graph[row][col] != color)
		return;
	if (visited[row][col] == 0) {
		visited[row][col] = 1;
		result++;
		dfs(row - 1, col, color);
		dfs(row + 1, col, color);
		dfs(row, col - 1, color);
		dfs(row, col + 1, color);
		return;
	}
	return;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		string map;
		cin >> map;
		for (int j = 0; j < map.length(); j++)
		{
			graph[i + 1][j + 1] = map[j];
		}
	}
	int sumW = 0;
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			dfs(i, j, 'W');
			sumW += result * result;
			result = 0;
		}
	}
	reset();
	int sumB = 0;
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			dfs(i, j, 'B');
			sumB += result * result;
			result = 0;
		}
	}
	cout << sumW << ' ' << sumB;
}

connected component를 찾는 문제이다. 

https://shine-slowly.tistory.com/50

알고리즘 : DFS와 BFS (3) - 기초 문제 풀이 (C++로 구현)

비슷한 문제가 위 포스트에 자세히 설명되어져 있다.

 

 

 

2178. (미로 탐색) N×M크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int graph[101][101];
int n, m;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
void bfs(int row, int col) {
	queue <pair<int, int> > q;
	q.push({ row, col });
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		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 (graph[nx][ny] == 1) {
				graph[nx][ny] = graph[x][y] + 1;
				q.push({ nx, ny });
			}
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		string map;
		cin >> map;
		for (int j = 0; j < map.length(); j++)
		{
			graph[i + 1][j + 1] = map[j] - '0';
		}
	}
	bfs(1, 1);
	cout << graph[n][m];
}

최단거리 문제는 bfs로 풀면 된다.

https://shine-slowly.tistory.com/50

알고리즘 : DFS와 BFS (3) - 기초 문제 풀이 (C++로 구현)

위 포스트의 2번이 이 문제랑 완전 똑같다. 풀이 과정을 자세히 설명해뒀다.

 

 

 

1743. (음식물 피하기) 통로에 떨어진 음식물을 피해가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다. 

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int n, m, k;
int r, c;
int graph[101][101];
int count_t, max_t;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
bool dfs(int x, int y) {
	if (x <= 0 || x > n || y <= 0 || y > m)
		return false;
	if (graph[x][y] == 1) {
		graph[x][y] = 0;
		count_t++;
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			dfs(nx, ny);
		}
		return true;
	}
	return false;
}
int main() {
	cin >> n >> m >> k;
	while(k--) {
		cin >> r >> c;
		graph[r][c] = 1;
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (dfs(i, j) && count_t > max_t) {
				max_t = count_t;
			}
			count_t = 0;
		}
	}
	cout << max_t;
}

connected component를 찾는 문제이다. 

 

 

 

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

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int n, m, k;
int r, c;
vector<int>graph[101];
bool visited[101];
int result = -1;
void dfs(int x) {
	visited[x] = 1;
	result++;
	for (int i = 0; i < graph[x].size(); i++)
	{
		int y = graph[x][i];
		if (!visited[y]) {
			dfs(y);
			
		}
	}
}
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	dfs(1);
	cout << result;
}

connected component를 찾는 문제이다. 

 

 

 

16953. (A -> B) A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
long long a, b;
int bfs(int x) {
	queue <pair <int, int>> q;
	q.push({ x, 1 });
	while (!q.empty()) {
		long long y = q.front().first;
		long long score = q.front().second;
		q.pop();
		if (y == b) {
			return score;
		}
		if (y * 2 <= b) {
			{
				q.push({ y * 2, score + 1 });
			}
		}
		if (y * 10 + 1 <= b) {
			{
				q.push({ y * 10 + 1, score + 1 });
			}
		}
	}
    return -1;
}
int main() {
	cin >> a >> b;
	cout << bfs(a);
}

bfs로 풀었다. dfs로도 풀 수 있다.

 

 

 

12851.  (숨바꼭질 2) 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

#include<iostream>
#include<queue>
using namespace std;
int n, k;
int way; // 방법의 개수
int minTime; // 최소 시간
bool visited[100001];
void bfs(int x) {
	queue < pair<int, int> > q;
	q.push({ x, 0 });
	visited[x] = 1;
	while (!q.empty()) {
		int location = q.front().first;
		int time = q.front().second;
		q.pop();
		visited[location] = 1;
		// 이미 방문했으나 다른 방법이 있는 경우
		if (way > 0 && time == minTime && location == k) {
			way++;
		}
		// 처음 방문
		if (way == 0 && location == k) {
			minTime = time;
			way++;
		}

		if (time > minTime && way > 0)
			break;
		if (location - 1 >= 0 && visited[location - 1] == 0) {
			q.push({ location - 1, time + 1 });
		}
		
		if (location + 1 <= 100000 && visited[location + 1] == 0) {
			q.push({ location + 1, time + 1 });
		}
		if (location * 2 <= 100000 && visited[location * 2] == 0) {
			q.push({ location * 2, time + 1 });
		}
	}
}
int main() {
	cin >> n >> k;

	bfs(n);
	cout << minTime << '\n' << way;
}

중요한 부분은 큐에 push할 때 visited를 변경하는 것이 아니라 pop을 한 후에 변경을 해주는 것이 중요하다.

예를 들어 5, 17의 경우 5->4->8->16->17 과 5->10->9->18->17가 있는데, 16에서 17로 넘어갈 때 이미 push를 하고 visited 값 변경을 해버리면 18에서 17로 넘어갈 때 push를 하지 않는 경우가 생긴다.

또 1에서 2로 갈 때 +1과 *2가 있는데 이 경우도 따로 생각을 해주기 위해서는 저렇게 구현을 해주어야 한다.

 

if (time > minTime && way > 0)
	break;

중간에 이 구문을 넣어서 굳이 100000까지 계산하지 않도록 설정하였다.

 

 

 

13549. (숨바꼭질 3) 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

이 문제는 간선의 가중치가 모두 동일하지 않다. 그러므로 deque 또는 prioroty queue를 사용하여 구현할 수 있다.

- Deque 이용

#include<iostream>
#include<deque>
using namespace std;
int n, k;

bool visited[100001];
void bfs(int x) {
	deque<pair<int, int>> dq;
	dq.push_back({ x, 0 });
	while (!dq.empty()) {
		int location = dq.front().first;
		int time = dq.front().second;
		dq.pop_front();
		visited[location] = 1;
		if (location == k) {
			cout << time;
			break;
		}
		if (location * 2 <= 100000 && visited[location * 2] == 0) {
			dq.push_front({ location * 2, time });
		}
		if (location + 1 <= 100000 && visited[location + 1] == 0)
		{
			dq.push_back({ location + 1, time + 1 });
		}
		if (location - 1 >= 0 && visited[location - 1] == 0)
		{
			dq.push_back({ location - 1 , time + 1 });
		}
	}
}
int main() {
	cin >> n >> k;
	bfs(n);
}

 

덱을 사용해서 우선순위가 높을 경우 앞쪽에 push를 해주는 방식이다. 순간이동을 할 경우 덱 앞에, 걷는 이동을 할 경우 덱 뒤에 넣는다. 

이런식으로 넣게되면 time이 적은 순서대로 덱 front에 가까워지게 된다.

 

- Priority Queue 이용

기존 Queue는 FIFO(선입선출) 구조이지만 우선순위 큐는 넣는 것은 동일하지만 pop을 할 경우 최소 또는 최대부터 빠지게 된다. 최대부터 빠지는 것을 Max Heap, 최소부터 빠지는 것을 Min Heap이라고 한다.

# 우선순위를 오름차순
priority_queue<int> q;
priority_queue<int, vector<int>,less<int> > q;

# 우선순위를 내림차순
priority_queue<int, vector<int>,greater<int> > q;

https://rujang.tistory.com/entry/%EB%B0%B1%EC%A4%80-13549%EB%B2%88-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88-3-CC

[백준] 13549번 : 숨바꼭질 3 [C/C++]

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

위 티스토리에서 우선순위 큐를 이용해서 구현했길래 첨부한다. 우선순위 큐를 사용하는 것 외에는 덱과 거의 비슷하다. 다른 점은 push_front와 push_back의 차이가 없다. 또한 pair에서 first를 time으로 설정해주어야 한다.

 

bool compare(pair<int, int> v1, pair<int, int> v2) {
    if (v1.second == v2.second)
        return v1.first < v2.first;
    else
        return v1.second < v2.second;
}

sort(v.begin(), v.end(), compare);

first, second를 보니 sort 함수 사용법이 생각나서 적어보았다.

 

 

 

13913. (숨바꼭질 4) 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

#include<iostream>
#include<queue>
#include<stack>
using namespace std;
int n, k;
bool visited[100001];
int source[100001];
void bfs(int x) {
	queue<pair<int, int>> q;
	q.push({ x, 1 });
	visited[x] = 1;
	while (!q.empty()) {
		int location = q.front().first;
		int time = q.front().second;
		q.pop();
		if (location == k) {
			cout << time - 1 << '\n';
			break;
		}

		if (location - 1 >= 0 && !visited[location - 1]) {
			q.push({ location - 1, time + 1 });
			visited[location - 1] = 1;
			source[location - 1] = location;
		}

		if (location + 1 <= 100000 && !visited[location + 1]) {
			q.push({ location + 1, time + 1 });
			visited[location + 1] = 1;
			source[location + 1] = location;
		}

		if (location * 2 <= 100000 && !visited[location * 2]) {
			q.push({ location * 2, time + 1 });
			visited[location * 2] = 1;
			source[location * 2] = location;
		}
	}
}
int main() {
	cin >> n >> k;
	bfs(n);
	int tracking = k;
	stack <int> path;
	path.push(tracking);
	while (tracking != n) {
		path.push(source[tracking]);
		tracking = source[tracking];
	}
	while (!path.empty()) {
		cout << path.top() << ' ';
		path.pop();
	}
}

source 배열을 통해 이전 위치를 저장하였다. 

 

void dfs(int x, int depth) {
	if (x < 0 || x > 1001)
		return;
	if (x == k) {
		path[depth] = x;
		if (minTime > depth) {
			minTime = depth;
			copy(path, path + (depth + 1), result);
		}
		path[depth] = 0;
		return;
	}
	if (!invited[x]) {
		invited[x] = 1;
		path[depth] = x;
		dfs(x - 1, depth + 1);
		dfs(x + 1, depth + 1);
		dfs(x * 2, depth + 1);
		invited[x] = 0;
		path[depth] = 0;
	}
}

dfs로 구현해보려고 했었다. result에는 지금까지 지나온 길들이 저장이 된다. 재귀함수라서 큰 수에서는 불가능했다.

 

 

 

14226. (이모티콘) 영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

#include<iostream>
#include<queue>
#include<stack>
using namespace std;
int s;
bool visited[1001];
void bfs(int x) {
	// 2배 or 저장 or -1
	priority_queue < pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
	pq.push({ 0, {x, 0} });
	visited[x] = 1;
	while (!pq.empty()) {
		int time = pq.top().first;
		int screen = pq.top().second.first;
		int clipboard = pq.top().second.second;
		pq.pop();
		visited[screen] = 1;
		if (screen == s) {
			cout << time;
			return;
		}

		if (screen - 1 >= 0 && !visited[screen - 1]) {
			pq.push({ time + 1, {screen - 1, clipboard} });
			
		}
		if (clipboard!=0 && screen + clipboard < 1001 && !visited[screen + clipboard]) {
			pq.push({ time + 1, {screen + clipboard, clipboard} });
			
		}
		if (screen * 2 < 1001 && screen != 0 && !visited[screen * 2]) {
			pq.push({ time + 2, {screen * 2, screen} });
			
		}
	}
}
int main() {
	cin >> s;
	bfs(1);
}

나는 visited을 1차원 배열로 만들어서 우선순위 큐를 사용했지만 visited을 2차원으로 구현하면 우선순위큐로 구현하지 않아도 된다.

https://luv-n-interest.tistory.com/1365

백준, BOJ, 14226번, 이모티콘 C++ [CPP] ★★★

https://jdselectron.tistory.com/57

[백준 14226, c++] 이모티콘(bfs)

 

 

 

17086. (아기 상어 2) 어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다. 안전 거리가 가장 큰 칸을 구해보자.

#include<iostream>
#include<queue>
using namespace std;
int n, m;
int graph[51][51];
int dx[] = {-1, 1, 0, 0, 1, -1, 1, -1};
int dy[] = {0, 0, -1, 1, 1, -1, -1, 1};

int bfs(int row, int col) {
	if (graph[row][col] == 1)
		return 0;
	int path[51][51] = { 0, };
	queue<pair<int, int>> q;
	q.push({ row, col });
	path[row][col] = 1;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		if (graph[x][y] == 1) {
			return path[x][y] - 1;
		}
		for (int i = 0; i < 8; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && nx < n && ny >= 0 && ny < m && path[nx][ny] == 0) {
				q.push({ nx, ny });
				path[nx][ny] = path[x][y] + 1;
			}
		}
	}
	return 0;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> graph[i][j];
		}
	}
	int maxPath = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			int temp = bfs(i, j);
			if (maxPath < temp) {
				maxPath = temp;
			}
		}
	}
	cout << maxPath;
}

상어가 없는 칸에서 bfs를 돌리면서 각 위치에서의 안전거리 최소값을 구해주면 된다. 

 

 

 

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

#include<iostream>
#include<queue>
using namespace std;
int n, m;
int graph[1001][1001];
int path[1001][1001];
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1 ,1 };
int minDay = 10001;
void bps() {
	queue <pair<int, int>> q;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (graph[i][j] == 1) {
				q.push({ i, j });
				path[i][j] = 1;
			}
		}
	}
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		if (graph[x][y] == -1) {
			path[x][y] = -1;
			continue;
		}
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && nx < m && ny >= 0 && ny < n && path[nx][ny] == 0) {
				q.push({ nx, ny });
				path[nx][ny] = path[x][y] + 1;
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> graph[i][j];
		}
	}
	bps();
	
	int max = 0;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (path[i][j] == 0 && graph[i][j] == 0) {
				cout << -1;
				return 0;
			}
			if (path[i][j] > max) {
				max = path[i][j];
			}
		}
	}
	cout << max - 1;
}

bfs로 풀 수 있는 문제였다. 최소거리 = 최소 날이므로 이를 이용하면 된다.