작은시작

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

코드 설명

BFS 기본문제 입니다.

BFS를 반복적으로 사용하여 거리가 가장 긴 구간을 완전탐색하여 구하는 문제였습니다.

가장 긴 거리를 재기위해 result라는 또하나의 map을 만들어주어서 거리를 기록하였습니다.

코드

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
int N, M;
char map[51][51];
bool visited[51][51];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };
int result[51][51];
int maxx;
void bfs(int y, int x) {
	queue<pair<int, int>> q;
	q.push({ y,x });
	visited[y][x] = true;

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
			if (!visited[ny][nx] && map[ny][nx]=='L') {
				q.push({ ny,nx });
				visited[ny][nx] = true;
				result[ny][nx] = result[y][x] + 1;
			}

		}



	}
	
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			if (maxx < result[y][x]) maxx = result[y][x];

		}
	}

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

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> map[y][x];


		}


	}
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			if (map[y][x] == 'L'){
				memset(result, 0, sizeof(result));
				memset(visited, false , sizeof(visited));
				bfs(y, x);
			}
		}
	}
	cout << maxx;
	return 0;
}

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

코드 설명

DFS, BFS의 기본을 위해 다시 복습하였다. 아직까지도 vector를 사용하는 것보다 2차원 배열을 사용하는 게 편한 것 같다....

하지만 vector를 사용하여 링크드리스트 형태로 구현하는 것도 연습하자!

코드

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
int N, M, V;
int map[1001][1001];
bool visited[1001];

void DFS(int start) {
	
	
	
	
	for (int i = 0; i <= N; i++) {
		if (map[start][i] == 1 && !visited[i]) {
			visited[i] = true;
			cout << i << " ";
			DFS(i);

		}


	}



}
void BFS(int start) {
	queue<int> q;
	q.push(start);
	visited[start] = true;

	while (!q.empty()) {
		int start = q.front();
		cout << start << " ";
		q.pop();

		for (int i = 0; i <= N; i++) {
			if (!visited[i] && map[start][i]) {
				q.push(i);
				visited[i] = true;
			}


		}

	}

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

	for (int i = 0; i < M; i++) {

		int a, b;
		cin >> a >> b;

		map[a][b] = 1;
		map[b][a] = 1;

	}
	cout << V << " ";
	visited[V] = true;
	DFS(V);
	memset(visited, false, sizeof(visited));
	cout << endl;
	
	
	BFS(V);








	return 0;
}

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

코드 설명

map과 copy_map으로 기존 맵과 다른 맵 하나를 만들어준다. 

map에 완전탐색을 통해 벽을 3개 만든다. 그때마다 copy_map으로 복사해주고 바이러스를 퍼뜨려본다.

그때마다 안전구역을 찾아주고 최대일 때를 저장해둔다.

다시 map으로 돌아와 다음 벽3개를 세워본다.

map에 벽세우기 -> copy_map 복사 -> copy_map 바이러스 감염 -> 안전구역 최대 개수 저장 -> 처음 map으로 돌아가기 

코드

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,1,-1 };
int map[10][10];
int copy_map[10][10];
bool visited[10][10];
int N, M;
int answer;
queue<pair<int, int>> q;
int result;
void bfs() {

	
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
			if (!visited[ny][nx] && copy_map[ny][nx]!=1) {
				q.push({ ny,nx });
				visited[ny][nx] = true;
				copy_map[ny][nx] = 2; //감염 
			}
		}

	}


}

void dfs(int level,int y, int x) {

	if (level == 3) {
		memcpy(copy_map, map, sizeof(map));
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < M; x++) {
				if (copy_map[y][x] == 2) {
					q.push({ y,x });
					
					visited[y][x] = true;
				}

			}
		}
		bfs();
		result = 0;
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < M; x++) {
				if (copy_map[y][x] == 0) {
					result++;
					
				}

			}
		}
		answer = max(answer, result);
		memset(visited, false, sizeof(visited));
		

		return;

	}


	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			if (map[y][x]==0) {
				map[y][x] = 1; //벽세우기
				dfs(level + 1, y, x);
				map[y][x] = 0;
			}
		}
	}

}
int main() {
	cin >> N >> M;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> map[y][x];
		}
	}

	memcpy(copy_map, map, sizeof(map));

	//벽 3개 전부 세워보기
	dfs(0,0, 0);


	cout << answer;

	return 0;
}

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

코드 설명

삼성 기출답게 bfs+구현 문제이다.

문제를 똑바로 읽고 설계를 해야 하는 문제이다. 기본적인 BFS를 이용한 순회 이동 문제이기도 하다.

함정아닌 함정이 많다.  전체 while문을 통해서 한번 인구이동 시켜준 후 다시 map을 전체 탐색하면서 인구이동이 가능한지 탐색해줘야 한다.

즉 , 한번 순회한다고 끝이 아니다

또한 vector하나를 이용하여 인구 이동시켜야 할 좌표를 가져온 후 main문에서 bfs탈출 후 좌표를 바꿔준다.

순회 한 번마다 정답이 +1 씩이라는 것을 잊지 말자

전체 순회를 하였을 때 한 칸도 이동할 칸이 없다면 그제야 break로 탈출시켜준다.

코드

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
int N, L, R;
int map[51][51];
bool visited[51][51];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };
int change_map[51][51];
	bool flag = false;
	int aanswer;

vector<pair<int, int> > a;
void bfs(int y, int x) {
	int sum = 0;
	int cnt = 0;
	queue<pair<int, int>> q;
	q.push({ y,x });
	visited[y][x] = true;
	
	
	a.push_back({ y,x });


	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
			if (!visited[ny][nx]) {
				if (abs(map[y][x] - map[ny][nx]) >= L && abs(map[y][x] - map[ny][nx]) <= R) {
					q.push({ ny,nx });
					visited[ny][nx] = true;
					a.push_back({ ny,nx });
				}
			}
		}
	}
	
	if (a.size() > 1) {
		cnt = a.size();
		for (int i = 0; i < cnt; i++) {
			sum += map[a[i].first][a[i].second];
		}
		for (int i = 0; i < cnt; i++) {
			map[a[i].first][a[i].second] = sum / cnt;
		}
		
		flag = true;

	}

	a.clear();
	
}

int main() {
	cin >> N >> L >> R;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cin >> map[y][x];
		}
	}
	while (1) {
		memset(visited, false, sizeof(visited));
		
		flag = false;
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				//바뀔게 있는가? 
				//이미 바뀐 index인가 
				if (!visited[y][x]) {
					bfs(y, x);
				}


			}
		}
	
		if (flag == false) break;
		else aanswer++;
	}

	cout << aanswer;
	return 0;
}