기록을

문제 링크

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

섬의 개수를 파악한다고 자주 기술했었는데, 간단하게 floodfill을 수행해주면 된다.

그림의 수를 파악하고, 그림의 넓이를 담아둘 때는 방문 처리 배열을 사용한다.

#include<iostream>
#include<queue>
using namespace std;

int map[500][500], dist[500][500];
int row, col;

queue<pair<int, int> > q;
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0, };

int cnt = 0;
void bfs(pair<int, int> start) {
	cnt++; //섬개수 확인
	q.push(start);
	dist[start.first][start.second]++; 
	int di = 2; //위에서 시작점 방문하면 거리 1이니까, 다음으로 들어갈 거리는 2

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

		for (int i = 0; i < 4; i++) {
			int nr = cur.first + dr[i];
			int nc = cur.second + dc[i];

			if (nr < 0 || nc < 0 || nr >= row || nc >= col || map[nr][nc] == 0 || dist[nr][nc] > 0)continue;

			q.push({ nr, nc });
			dist[nr][nc] = di;
			di++;
			
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> row >> col;
	for(int i = 0 ; i < row ; i++)
		for (int j = 0; j < col; j++) {
			cin >> map[i][j];
		}

	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++) {
			if (map[i][j] == 1 && dist[i][j] == 0)
				bfs({ i, j });
		}
	//방문처리 배열에 카운트를 해뒀기때문에 그 안에서 최댓값을 구하면 된다.
	int Max = -1;
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			if (dist[i][j] > Max)
				Max = dist[i][j];
		}
	}
	cout << cnt << '\n' << Max << '\n';
	return 0;
}

문제링크

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

섬의 개수를 확인하는 방식으로 전형적인 bfs를 사용해서 풀이가 가능하다.

bfs 함수가 실행되는 횟수를 확인하면 된다.

방문하지 않았으면서 배추가 있는 곳이 bfs의 시작점이 된다.

범위 밖을 나가는 요소와 이미 방문한 지점, 방문할 필요가 없는 지점을 제외하면 되는 간단한 bfs이다.

#include<iostream>
#include<queue>
using namespace std;
int map[51][51], vis[51][51];
int m, n, k;

int cnt = 0;
queue<pair<int, int> > q;
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };
void bfs(pair<int, int> start) { //전형적인 bfs
	cnt++; //섬 개수 추가
	q.push(start);
	vis[start.first][start.second] = 1;
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nr = cur.first + dr[i];
			int nc = cur.second + dc[i];
			//범위 나가거나 배추가 없는 곳이거나 이미 방문한 곳이면 continue
			if (nr < 0 || nc < 0 || nr >= n || nc >= m || vis[nr][nc] == 1 || map[nr][nc] == 0)continue;
			
			q.push({ nr, nc });
			vis[nr][nc] = 1;

		}
	}

}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tc;
	cin >> tc;
	while (tc--) {

		cin >> m >> n >> k;

		int n1, n2;
		while (k--) {
			cin >> n1 >> n2;
			map[n2][n1] = 1;
		}

		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (map[i][j] == 1 && vis[i][j] == 0)
					bfs({ i, j }); //1인 지점 넘겨줘야함

		cout << cnt << '\n';

		//이후로 초기화
		for (int i = 0; i < n; i++) 
			for (int j = 0; j < m; j++) {
				map[i][j] = 0;
				vis[i][j] = 0;
			}
		cnt = 0;
	}

	return 0;
}

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

bfs에서 방문 처리를 거리 배열을 활용하여 수행하는 문제이다.

c++에서 c의 std io함수들과의 동기화를 끊어주는 ios::sync_with_stdio(false);

이것을 적어둔 상태로 scanf를 사용해서 맞왜틀을 반복했다.

visual studio에서는 알아서 잡아주는데, 백준 채점 환경에선 그렇지 않다.

#pragma warning(disable : 4996)
#include<iostream>
#include<queue>
using namespace std;
int n, m, map[101][101], dis[101][101];

queue<pair<int, int> > q;
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };
void bfs(pair<int, int> start) {
	q.push(start);
	dis[start.first][start.second]++;
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nr = cur.first + dr[i];
			int nc = cur.second + dc[i];

			if (nr < 0 || nc < 0 || nr >= n || nc >= m || map[nr][nc] == 0 || dis[nr][nc] > 0) continue;

			q.push({ nr, nc });
			dis[nr][nc] = dis[cur.first][cur.second] + 1;
		}
	}
}
int main(void) {
	//ios::sync_with_stdio(false); 이거 적어두고 아래에서 scanf 쓰면 gcc에선 틀린다
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf("%1d", &map[i][j]);


	bfs({ 0, 0 });
	cout << dis[n - 1][m - 1] << '\n';
	return 0;
}

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

궁수 세 명을 최적의 위치에 배치해서, 가장 많은 적을 죽이도록 하는 문제이다.

따라서 열의 길이를 이용해서, 궁수가 위치할 수 있는 세 곳을 먼저 조합으로 뽑는다.

각각의 궁수에 대해 bfs를 돌린다. 앞에서부터 멀리있는 곳까지 확인할 것이다.

이때 중요한 것이 몇가지 있다.

궁수들은 같은 거리라면 왼쪽에 있는 적부터 공격한다. 따라서 bfs를 수행할 때, 탐색의 순서를 좌, 상, 우 이렇게 해줘야 한다.

또한 궁수들은 동시에 같은 적을 공격할 수 있다고 했기 때문에, 하나의 궁수를 가지고 탐색을 하다가 적을 발견했을 때에, 바로 그 적을 없애면 안 된다.

그걸 없애버리면 동시에 같은 적을 공격할 수 있다는 조건에 위배되기 때문이다.

set에 추가만 해주고, 이번 턴에 죽일 적을 찾았으므로, 바로 현재 궁수의 bfs를 종료해주면 된다.

세 궁수의 탐색이 사정거리만큼 모두 이루어지고 나면 set을 활용해서 지도에서 적을 지우고, set을 비워준다.

시기적절하게 초기화를 해주고, 적들을 지도에서 제거하고, 적들을 이동시키는 잔처리가 중요한 문제였다.

문제 링크

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

섬의 개수를 파악한다고 자주 기술했었는데, 간단하게 floodfill을 수행해주면 된다.

그림의 수를 파악하고, 그림의 넓이를 담아둘 때는 방문 처리 배열을 사용한다.

#include<iostream>
#include<queue>
using namespace std;

int map[500][500], dist[500][500];
int row, col;

queue<pair<int, int> > q;
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0, };

int cnt = 0;
void bfs(pair<int, int> start) {
	cnt++; //섬개수 확인
	q.push(start);
	dist[start.first][start.second]++; 
	int di = 2; //위에서 시작점 방문하면 거리 1이니까, 다음으로 들어갈 거리는 2

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

		for (int i = 0; i < 4; i++) {
			int nr = cur.first + dr[i];
			int nc = cur.second + dc[i];

			if (nr < 0 || nc < 0 || nr >= row || nc >= col || map[nr][nc] == 0 || dist[nr][nc] > 0)continue;

			q.push({ nr, nc });
			dist[nr][nc] = di;
			di++;
			
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> row >> col;
	for(int i = 0 ; i < row ; i++)
		for (int j = 0; j < col; j++) {
			cin >> map[i][j];
		}

	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++) {
			if (map[i][j] == 1 && dist[i][j] == 0)
				bfs({ i, j });
		}
	//방문처리 배열에 카운트를 해뒀기때문에 그 안에서 최댓값을 구하면 된다.
	int Max = -1;
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			if (dist[i][j] > Max)
				Max = dist[i][j];
		}
	}
	cout << cnt << '\n' << Max << '\n';
	return 0;
}

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

오답에서 적었듯이, 일반적인 dfs로는 해결하기 까다로운 문제이다.

우선, 들어오는 입력만으로는 (y/s)여부 만으로는 그 성분의 자리가 어디인지 알 수 없다.

따라서 자리번호를 매겼다.

그리고 그 자리번호를 7개 선택해서, 뽑힌 7개의 자리번호가 인접한 상태이고, S를 4개 이상 포함한다면 카운트를 해주었다.

순서가 구분이 안 되서 생기는 문제는, 자리번호를 조합으로 뽑으면 순서에 상관없이 하나만 뽑히기 때문에 해결된다.

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

육지가 될 수 있는 땅 한 칸 한 칸에 대해 개별적으로 bfs를 수행해주면 된다.

방문처리를 거리 측정으로 하면서 최댓값을 구해주면 된다.

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

조합과 bfs가 합쳐진 문제인 연구소 시리즈의 첫번째 문제이다.

다른 연구소 문제를 해결했다면, 비슷한 아이디어로 무난하게 해결할 수 있다.

알고리즘은 다음과 같다.

1. 빈 공간(0인 위치)를 벡터에 모두 담아놓고 그 중 세개를 조합으로 뽑는다.

2. 조합으로 뽑은 곳의 값을 1로 (벽으로) 변경해준 이후에 bfs를 수행한다.

3. 방문되지 않은 지점(바이러스가 퍼지지 않은 지점)이면서 빈 공간인 부분의 수를 계산한다.

4. 수정한 map과 방문처리 배열을 초기화 시켜준다.

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

연구소 3을 해결했다면 거저 먹을 수 있는 문제이다.

기본적으로 바이러스의 후보지들을 가지고 조합을 구해야 한다.

바이러스 후보지가 5곳이고 m = 3으로 주어진다면, 5Cm만큼의 경우의 수를 확인해보면 답을 찾을 수 있다.

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

문제 설명

1. 비활성 바이러스의 위치가 여러곳 주어진다.

2. 그 중에서 M개를 선택해서 확산 바이러스로 만들고, 바이러스의 확산을 시작한다.

(확산 바이러스는 비활성 바이러스를 만나면 그 비활성 바이러스를 확산 바이러스로 바꾼다)

3. 바이러스가 전부 퍼질 때까지 걸린 시간의 최솟값을 구하여라.

문제를 시작하기 전에 몇가지 표현을 잘 이해하고 들어가야한다.

먼저 문제가 구하라고 한 것은, 바이러스가 다 퍼질 때까지 걸린 최소 시간이다. 퍼지는 바이러스가 활성 바이러스여야 한다는 말은 없다.

테스트케이스를 좋게 주지 않았더라면 괴랄한 정답률을 보여주지 않았을까 생각한다.

아래쪽에 있는 테스트 케이스를 활용하면 대부분의 엣지 케이스에 대한 감을 잡을 수 있을 것이다.

[알고리즘]

1. 백트레킹을 활용해서 전체 바이러스 중에서 m개를 선택한다.

2. 선택한 m개의 바이러스를 큐에 넣고 BFS를 돌린다.

3. 빈칸과 비활성 바이러스가 있으면서 방문하지 않은 지점이면 바이러스를 확산시키고, 시간을 기록한다.

4. 시간이 얼마 걸렸는지 파악하기 위해 방문처리 배열 내에서 최댓값을 찾는다. 이 때 최댓값을 선택할 때 그 지점이 바이러스가 위치하고 있는 지점이라면 최댓값으로 보지 않는다.

마지막 테스트 케이스에서와 같이, 이미 바이러스로 채워져있는 곳은 사실 방문할 필요가 없었던 지점이다. 하지만 거쳐가면서 확산이 이루어져야 하기 때문에 일단 채택은 하고, 바이러스가 전체로 퍼지는 시간에는 영향을 끼치면 안되기 때문에 제외해준다.

5. 위에서 구한 최댓값(시간)의 최솟값을 답으로 정한다.

#include<iostream>
#include<vector>
#include<queue>
#include<limits.h>
using namespace std;

int n, m, map[51][51], dis[51][51], arr[11], st = 0; //연구소 크기, 바이러스 개수
bool isused[11];
struct VIRUS {
	int r;
	int c;
};
vector<VIRUS> v;
queue<pair<int, int> > q;
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
int res = INT_MAX;

void bfs() {
	
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();
		
		for (int i = 0; i < 4; i++) {
			int nr = cur.first + dr[i];
			int nc = cur.second + dc[i];
			if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
			if (dis[nr][nc] >= 0 || map[nr][nc] == 1) continue;
			
			q.push({ nr, nc });
			dis[nr][nc] = dis[cur.first][cur.second] + 1;
		}
	}
}
void init() {
	for(int i = 0 ; i < n ; i++)
		for (int j = 0; j < n; j++) 
			dis[i][j] = -1;
}
bool isDone(){
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (dis[i][j] == -1 && map[i][j] != 1)
				return false;
		}
	}
	return true;
}
void findMax() {
	int Max = 0;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) 
			if (Max < dis[i][j] && map[i][j] != 2) 
				Max = dis[i][j];

	if (res > Max) res = Max;
}
void func(int k) {
	if (k == m) {

		for (int i = 0; i < m; i++) {
			int r = v[arr[i]].r;
			int c = v[arr[i]].c;
			q.push({ r, c });
			dis[r][c]++;
		}
		bfs();

		if (isDone()) 
			findMax();
		
		init();

		return;
	}

	if (k == 0) st = 0;
	for (int i = st; i < v.size(); i++) {
		if (!isused[i]) {
			arr[k] = i;
			st = i;
			isused[i] = true;
			func(k + 1);
			isused[i] = false;
		}
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			dis[i][j] = -1;
			if (map[i][j] == 2) { //바이러스 위치 저장
				VIRUS tmp;
				tmp.r = i;
				tmp.c = j;
				v.push_back(tmp);
			}
		}

	func(0);

	if (res == INT_MAX) cout << -1 << '\n';
	else
		cout << res;
	return 0;
}