기록을

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

모든 점을 방문할 수 있는지 확인하면 되는 문제이므로 bfs / dfs로 기본적으로 접근할 수 있다.

또한 n이 작기 때문에 플로이드 와샬도 가능하다. 가중치는 모두 1로 두면 되겠다.

이러한 문제를 풀 때 신경써줄 부분은, 자기 자신을 곧바로 방문할 수 있는지 확인하는 것이다.

이 문제에서는 노드1->노드1 이런식으로 곧바로 자기 자신을 방문할 수 없고, 1->2->3->1 이런식으로 사이클을 거쳐서 root(자기 자신)을 방문할 수 있다.

따라서 플로이드 와샬 알고리즘을 적용할 때, 비용을 무한대로 초기화 하는 과정에서, 자기 자신으로 가는 비용도 무한대로 초기화해주고 시작해야 한다.

비슷한 맥락으로, DFS로 문제를 풀이할 때, 보통 시작점을 방문처리하고 알고리즘을 시작한다.

하지만 시작점을 방문처리하고, 미방문한 지점을 이어서 방문하도록 알고리즘을 구현하면

1-> 2-> 3-> 1  이 과정에서, 마지막에 3->1을 방문할 수가 없다. 초기에 시작 지점인 1을 방문처리 했기 때문이다.

따라서 이것을 방지하기 위해서 시작지점을 방문처리하지 않는다. 3->1을 거쳐서 시작 지점에서 다시 for 문을 돌면 어짜피 갈 수 있는 곳이 없으므로 재귀를 탈출하게 된다.

1. DFS

2. 플로이드 와샬

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GOPPaAeMDFAXB&categoryId=AV7GOPPaAeMDFAXB&categoryType=CODE

모든 정점을 시작점으로 dfs를 돌려주면 된다.

방문 처리를 조금 더 직관적으로 하면 다음과 같이 구현할 수 있다.

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

그래프 정보를 배열로 받아주고, DFS를 돌려주면 된다.

DFS를 실행할 때, 방문한 지점을 다시 방문하는 것이 base condition이므로, DFS가 끝날 때 마다 사이클의 개수가 하나씩 늘어난다.

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

5 * 5의 격자판이 주어진다.

그 격자판에 있는 정수들을 활용해서 길이 6의 수열을 만들어야 한다.

이 때 사용했던 숫자라도 중복해서 사용할 수 있다.

또한, 숫자는 직전에 선택했던 숫자의 동서남북 방향에 위치한 숫자중에 하나로 선택해야 한다.

중복 제거를 간편하게 하기 위해서 set을 사용했다.

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/16234

bfs 혹은 dfs를 활용하여 해결할 수 있다.

인구이동 조건과, 방문 여부가 탐색 진행의 기준이 된다.

for(for(bfs)) 구조로 해결할 수 있다.

for(for 을 완전히 탈출할 때 까지가 한 번의 인구이동 날이라고 할 수 있다.

따라서 이를 무한루프로 감싸서, 인구의 이동이 없는 경우 무한루프를 탈출하는 구조로 해결하면 된다.

그런데, 인구 이동 조건을 만족하더라도, 그 자리에서 인구수를 바로 갱신할 수가 없다.

일단 국경을 개방할 수 있는 지점을 모두 찾아내야 하기 때문에, 일단 한 번의 bfs가 다 종료되어야 인구수를 갱신할 수 있다. 방문처리된 지점들(큐에 삽입된 적이 있는 지점들)이 갱신의 대상이기 때문에, 이 좌표들을 차례로 백터에 저장해준다.

이후에 벡터의 크기가 연합국의 숫자이고, 인구수의 합은 큐에 삽입하면서 기억해 둘 것이다.

한번의 인구 이동이 모두 끝났는데, 변화가 없다면 무한 루프를 종료하고, 그렇지 않다면 방문처리 배열을 초기화해준 이후에 인구이동을 다시 시작해주면 된다.

#include<iostream>
#include<queue>
#include<math.h>
#include<vector>
using namespace std;
int N, L, R, m[51][51];
bool bor[51][51]; //방문 처리 배열
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };

queue<pair<int, int> > q;
bool updated = false;
int idxSum = 0;
vector<pair<int, int> > v;
void bfs(pair<int, int> start) {
	q.push(start);
	bor[start.first][start.second] = true;

	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 || bor[nr][nc])
				continue;
			if (abs(m[nr][nc] - m[cur.first][cur.second]) >= L &&
				abs(m[nr][nc] - m[cur.first][cur.second]) <= R) {
				q.push({ nr, nc });
				bor[nr][nc] = true; 
				
				v.push_back({ nr, nc });
				idxSum += m[nr][nc];
			}
		}
	}
}
void init() {
	for (int i = 0; i < N; i++) 
		for (int j = 0; j < N; j++) 
			bor[i][j] = 0;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> L >> R;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> m[i][j];

	int res = 0;
	while (1) {
		updated = false;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!bor[i][j]) {
					v.clear();
					v.push_back({ i,j }); 
					idxSum = m[i][j];
					bfs({ i, j });
				}
				//열린 국경이 있으면
				if (v.size() >= 2) { //한 연합 내의 국가 개수
					updated = true;
					int val = idxSum / v.size();
					for (int i = 0; i < v.size(); i++) {
						m[v[i].first][v[i].second] = val;
					}
				}
			}
		}
		if (updated) res++;
		else break;
		init();
	}
	cout << res << '\n';
	return 0;
}

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

dfs와 bfs를 모두 활용한다.

dfs를 통해서 섬의 개수를 파악하고, 섬마다 index를 할당해준다.

이후에는 섬으로부터 바다로 탐색을 수행하고, 이때 bfs를 활용한다.

거리를 측정하기 시작한 섬에 대한 정보를 idx 배열에 저장해준다.

즉 i행 j열이 바다라고 한다면, 섬이 아니기 때문에 index가 할당되어있지 않은데, 

어느 섬으로부터 측정한 거리라는 것을 idx 배열에 명시해준다.

이를 통해서 다른섬이 만났을 때, 그 지점까지의 거리가 만들 수 있는 다리의 최소 거리인지 판단해준다.

#include<iostream>
#include<queue>
using namespace std;
int m[100][100], n, dis[100][100], idx[100][100];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
int Min = -2;

queue <pair<int, int> > q;
void init() {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			dis[i][j] = -1;
	while (!q.empty()) q.pop();
}
void minCal(int val) { //최소 거리인지 판단
	if (Min == -2) { //최솟값이 갱신된 적이 없다면
		Min = val;
		return;
	}
	else {
		if (Min > val) Min = val;
		else
			return;
	}
}
bool boundCheck(int r, int c) {
	return r < 0 || c < 0 || r >= n || c >= n;
}
void dfs(int row, int col, int landCnt) {
	dis[row][col]++;
	idx[row][col] = landCnt; //섬의 index 지정
	for (int i = 0; i < 4; i++) {
		int nr = row + dr[i];
		int nc = col + dc[i];
		if (boundCheck(nr, nc) || m[nr][nc] == 0 || dis[nr][nc] >= 0) continue;
		dfs(nr, nc, landCnt);
	}
}
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 (boundCheck(nr, nc) || dis[nr][nc] >= 0) continue;
			if (m[nr][nc] == 1) {
				//섬을 만났을 때
				if (idx[nr][nc] == idx[cur.first][cur.second]) continue;
				else {
					//출발한 섬과 다른 섬을 만났을 때
					minCal(dis[cur.first][cur.second]);
					init();
					return;
				}
			}
			q.push({ nr, nc });
			dis[nr][nc] = dis[cur.first][cur.second] + 1;
			idx[nr][nc] = idx[cur.first][cur.second];
			//어느 섬에서 측정한 거리라는 것을 명시
		}
	}
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> m[i][j];
	init();
	
	int landCnt = 0; // 섬 번호
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (dis[i][j] < 0 && m[i][j] == 1) {
				landCnt++;
				dfs(i, j, landCnt);
			}
		}
	}
	init(); //방문처리 배열 초기화

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (dis[i][j] < 0 && m[i][j] == 1) {
				bfs({ i, j });
			}
		}
	}
	cout << Min << '\n';
	return 0;
}
//섬과 섬을 잇는 가장 짧은 다리
//1에서 시작해서 0으로 퍼져나가게
//퍼져나가기 시작한 점이 어느 섬인지 확인하면서 비교

//dfs로 섬 개수 파악하고 번호 매김
//섬이면서 방문 안 한 곳 bfs -> 주변이 바다인 곳 방문(거리측정)
//가다가 섬이면서 내 섬이 아닌 곳을 만나면 중지 -> 길이 최소 비교

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

floodfill을 통해서 빙산이 두 개가 될 때까지 빙산이 녹는 과정을 구현하면 된다. 

빙산이 녹는 것을 구현할 때 주의할 사항은, 녹아서 0이 된 빙산을 같은 해야 원래 녹아있던 것으로 보지 않는 것이다.

이는 방문 처리 배열을 통해서 처리해주면 된다. 녹아서 바다가 되버린 빙산이라도, 방문처리가 되어있기 때문에, 방문 처리가 되지 않은 바다만 빙산을 녹이는 데에 영향을 끼칠 수 있게 구현을 하면 된다.

또 유의할 것은 방문처리 배열의 초기화이다. 빙산을 녹이는 과정과, 빙산의 개수를 파악하기 위해서 floodfill을 하는 과정은 모두 방문처리 배열을 이용한다. 이때 한 번 방문처리 배열을 사용했으면, 바로 초기화를 해줘야 한다.

#include<iostream>
using namespace std;
int R, C, m[300][300];
bool vis[300][300];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
void dfs(int row, int col) {
	vis[row][col] = true;
	
	for (int i = 0; i < 4; i++) {
		int nr = row + dr[i];
		int nc = col + dc[i];
		
		if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
		if (vis[nr][nc] || m[nr][nc] == 0) continue;
		dfs(nr, nc);
	}
}
int Flood() {
	int res = 0;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (m[i][j] != 0 && !vis[i][j]) {
				res++;
				if (res > 1) break;
				dfs(i, j);
			}
		}
	}
	return res;
}
void init() {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			vis[i][j] = false;
		}
	}
}
void Melt(int row, int col) {
	vis[row][col] = true;
	int cnt = 0;
	for (int i = 0; i < 4; i++) {
		int nr = row + dr[i];
		int nc = col + dc[i];

		if (nr < 0 || nc < 0 || nr >= R || nc >= C || vis[nr][nc]) continue;
		if (m[nr][nc] == 0) cnt++;
		else if (m[nr][nc] == 1) Melt(nr, nc);
	}
	if (m[row][col] - cnt <= 0) m[row][col] = 0;
	else
		m[row][col] = m[row][col] - cnt;
}

int main() {
	cin >> R >> C;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> m[i][j];
		}
	}

	int year = 0;
	while (1) {
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (m[i][j] != 0 && !vis[i][j]) {
					Melt(i, j);
				}
			}
		}
		year++;
		init();
		if (Flood() > 1) {
			cout << year << '\n';
			break;
		}
		init();
		if (Flood() == 0) {
			cout << 0 << '\n';
			break;
		}
		init();
	}
	return 0;
}

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

입력을 받으면서, 입력받는 높이의 최소와 최대를 구해둔다.

1부터 100까지 다 해볼 필요 없이 필요한 것만 해보는 것이다. 문제에서 아무 곳도 잠기지 않는 경우도 있다고 명시했기 때문에 높이 제한의 최소-1부터 최대까지를 물의 높이 변화로 정해주면 된다.

#include<iostream>
using namespace std;
int N, m[102][102];
bool vis[102][102];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
void dfs(int row, int col, int H) {
	vis[row][col] = true;
	for (int i = 0; i < 4; i++) {
		int nr = row + dr[i];
		int nc = col + dc[i];
		if (nr < 0 || nc < 0 || nr >= N || nc >= N) continue;
		if (vis[nr][nc] || m[nr][nc] <= H) continue;
		dfs(nr, nc, H);
	}
}
void init() {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			vis[i][j] = false;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	int hMin = 110, hMax = -1;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> m[i][j];
			if (m[i][j] > hMax) hMax = m[i][j];
			if (m[i][j] < hMin) hMin = m[i][j];
		}
	}
	
	int cntMax = 0;
	for (int h = hMin - 1; h <= hMax ; h++) {
		int cntH = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (m[i][j] > h && !vis[i][j]) {
					dfs(i, j, h);
					cntH++;
				}
			}
		}
	
		if (cntH > cntMax) cntMax = cntH;
		init();
	}
	cout << cntMax << '\n';
	return 0;
}