[바킹독의 실전 알고리즘] 복습 - 0x09 (1)

오젼·4일 전
알고리즘
0

[바킹독의 실전 알고리즘]

목록 보기
18/19

0x09 Breadth First Search

너비 우선 탐색!

✅ BFS vs DFS 핵심 비교

항목BFS (너비 우선 탐색)DFS (깊이 우선 탐색)
탐색 방향가까운 노드부터 → 너비(가로)로 확장가능한 한 깊이(세로)로 내려감
자료구조큐 (Queue) 사용스택(Stack) 사용 또는 재귀 함수 활용
방문 순서레벨 순서 (거리 순)경로 따라 깊이 우선
주 용도최단 거리 탐색, 레벨 순서 처리경로 탐색, 백트래킹, 조합/순열 생성
시간/공간복잡도둘 다 O(V + E)둘 다 O(V + E)
직관적인 예시미로에서 가장 빠른 길 찾기미로에서 한 방향으로 끝까지 가보다가 돌아오는 방식

✅ 너비 vs 깊이 예시 비유

  • BFS는 마치 수면에 돌을 던졌을 때처럼 동심원으로 퍼지는 느낌이야. 한 칸에서 출발해서 인접한 모든 칸 → 그 다음에 그 칸들의 인접한 칸들... 이런 식.
  • DFS는 굴 파듯이 한 방향으로 쭉 내려갔다가 더 이상 갈 수 없으면 뒤로 돌아오는 느낌이야.

ㅇㅎ BFS는 동심원 DFS는 땅굴
BFS는 그래서 먼저 조건을 만족하는 게 최단 거리다.
DFS는 내가 먼저 조건 만족했다고 최단 거리가 보장 되는 건 아님. 옆으로 굴 파고 내려간 게 더 짧을 수 있으니까.

10026 | 적록색약

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

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

bool vis[100][100];
char board[100][100];

int N, ans1, ans2;

queue<pair<int, int> > q;

int bfs(int x, int y) {
	if (vis[x][y]) return 0;

	q.push({x, y});
	vis[x][y] = 1;

	while (!q.empty()) {
		auto cur = q.front();
		q.pop();
		for (int dir = 0; dir < 4; ++dir) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];

			if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
			if (vis[nx][ny]) continue;
			if (board[cur.X][cur.Y] != board[nx][ny]) continue;

			q.push({nx, ny});
			vis[nx][ny] = 1;
		}
	}
	return 1;
}

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

	cin >> N;

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) cin >> board[i][j];
	}

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) ans1 += bfs(i, j);
	}

	for (int i = 0; i < N; ++i) fill(vis[i], vis[i] + N, 0);
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j)
			if (board[i][j] == 'G') board[i][j] = 'R';
	}

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) ans2 += bfs(i, j);
	}

	cout << ans1 << ' ' << ans2;
}

와~~~ 이제 진짜 혼자 풀 수 있다
큐에 넣을 때 방문 체크 하는 것 주의!!
맨 처음에 큐에 넣을 때도 방문 체크를 해줘야 한다. 큐 push + 방문 true는 세트!!

7569 | 토마토

틀린 버전

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

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

int board[100][100][100];
bool vis[100][100][100];

int N, M, H;

void bfs(int z, int x, int y) {
	if (vis[z][x][y] || board[z][x][y] != 1) return;

	queue<pair<int, pair<int, int> > > q;
	q.push({z, {x, y}});
	vis[z][x][y] = 1;

	while (!q.empty()) {
		auto cur = q.front();
		q.pop();

		for (int dir = 0; dir < 6; ++dir) {
			int nz = cur.X + dz[dir];
			int nx = cur.Y.X + dx[dir];
			int ny = cur.Y.Y + dy[dir];

			if (nz < 0 || nz >= H || nx < 0 || nx >= N || ny < 0 || ny >= M)
				continue;
			if (vis[nz][nx][ny] || board[nz][nx][ny]) continue;
			q.push({nz, {nx, ny}});
			board[nz][nx][ny] = board[cur.X][cur.Y.X][cur.Y.Y] + 1;
			vis[nz][nx][ny] = 1;
		}
	}
}

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

	cin >> M >> N >> H;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < N; ++j) {
			for (int k = 0; k < M; ++k) cin >> board[i][j][k];
		}
	}

	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < N; ++j) {
			for (int k = 0; k < M; ++k) bfs(i, j, k); // 시작점마다 개별 BFS
		}
	}

	int ans = 0;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < N; ++j) {
			for (int k = 0; k < M; ++k) {
                if (board[i][j][k] == 0) {
                    cout << -1;
                    return 0;
                }
				ans = max(ans, board[i][j][k]);
			}
		}
	}
	cout << ans - 1;
}

/*
5 3 1
1  -1 0 0 0
-1 -1 0 1 1
0   0 0 1 1
*/

왜 틀렸냐면! 이 문제는 시작점이 여러 개.
근데 시작점마다 bfs를 해서 문제.

예를 들어

5 3 1
1         -1         0         0         0
-1        -1         0         1(<- 요놈) 1
0          0         0         1         1

인 경우 (0, 1, 3)에서 첫 bfs가 일어날 거고 그 때

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

이렇게 토마토가 전부 익어버릴 거임.

근데 맨 아랫줄 토마토들은 (0, 2, 3) 토마토에 의해서 익는 게 맞는데 먼저 선수를 쳐버리게 되는 거;; 그리고 오른쪽 윗모서리 애도.

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

이렇게 되는 게 맞는 건데..

그래서 처음에 큐에 시작점을 모두 넣은 다음에
한 번만 bfs를 해줘야 됨.

그래야 시작점이 먼저 처리 되고 나서, 시작점을 기준으로 주변부 애들이 처리되면서 퍼져나갈 수 있음.

고친 버전

#include <bits/stdc++.h>
using namespace std;

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

int board[100][100][100];
bool vis[100][100][100];

int N, M, H;
queue<tuple<int, int, int> > q;

void bfs() {
	while (!q.empty()) {
		auto [z, x, y] = q.front();
		q.pop();

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

			if (nz < 0 || nz >= H || nx < 0 || nx >= N || ny < 0 || ny >= M)
				continue;
			if (vis[nz][nx][ny] || board[nz][nx][ny]) continue;
			q.push({nz, nx, ny});
			board[nz][nx][ny] = board[z][x][y] + 1;
			vis[nz][nx][ny] = 1;
		}
	}
}

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

	cin >> M >> N >> H;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < N; ++j) {
			for (int k = 0; k < M; ++k) {
				cin >> board[i][j][k];
				if (board[i][j][k] == 1) q.push({i, j, k});
			}
		}
	}

	bfs();

	int ans = 0;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < N; ++j) {
			for (int k = 0; k < M; ++k) {
				if (board[i][j][k] == 0) {
					cout << -1;
					return 0;
				}
				ans = max(ans, board[i][j][k]);
			}
		}
	}
	cout << ans - 1;
}

5427 | 불

#include <bits/stdc++.h>
using namespace std;

int t, w, h;
char board[1000][1000];
int distF[1000][1000];	// fire
int distP[1000][1000];	// person

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

void solve() {
	queue<pair<int, int> > fire, person;

	cin >> w >> h;

	// 입력 & 초기화
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j) {
			cin >> board[i][j];
			distF[i][j] = distP[i][j] = -1;
			if (board[i][j] == '*') {
				fire.push({i, j});
				distF[i][j] = 0;
			} else if (board[i][j] == '@') {
				person.push({i, j});
				distP[i][j] = 0;
			}
		}
	}

	// 불 bfs
	while (!fire.empty()) {
		auto [x, y] = fire.front();
		fire.pop();
		for (int dir = 0; dir < 4; ++dir) {
			int nx = x + dx[dir], ny = y + dy[dir];

			if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
			if (distF[nx][ny] != -1 || board[nx][ny] == '#') continue;

			fire.push({nx, ny});
			distF[nx][ny] = distF[x][y] + 1;
		}
	}

	// 사람 bfs
	while (!person.empty()) {
		auto [x, y] = person.front();
		person.pop();
		for (int dir = 0; dir < 4; ++dir) {
			int nx = x + dx[dir], ny = y + dy[dir];

			if (nx < 0 || nx >= h || ny < 0 || ny >= w) {
				cout << distP[x][y] + 1 << '\n';
				return;
			}
			if (distP[nx][ny] != -1 || board[nx][ny] == '#') continue;
			if (distF[nx][ny] != -1 && distP[x][y] + 1 >= distF[nx][ny])
				continue;

			person.push({nx, ny});
			distP[nx][ny] = distP[x][y] + 1;
		}
	}
	cout << "IMPOSSIBLE\n";
}

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

	cin >> t;

	while (t--) solve();
}

처음엔 더 깔끔하게 푸는 방법 없을까 고민했는데
불 bfs를 먼저 구하고 사람 bfs를 구하는 방법밖에 없음.

이때! 사람 bfs를 구할 때 가려는 자리에 불이 있다면(-> distF[nx][ny] != -1) 그리고 불이 나보다 먼저 도착했으면(-> distP[x][y] + 1 >= distF[nx][ny]) 그건 q에 넣지 않아야 함.

distP[nx][ny]가 업데이트 된 상태가 아니니까 distP[x][y] + 1 로 조건을 비교해줘야 한다.

그리고 경계조건을 만나면 바로 return 해주면 된다. bfs 특성상 더 진행할 필요가 없음. 처음 경계 조건을 만날 때가 가장 짧은 탈출 거리임.

2206 | 벽 부수고 이동하기

#include <bits/stdc++.h>
using namespace std;

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

char board[1000][1000];
int dist[1000][1000][2];

int n, m;

int bfs() {
	queue<tuple<int, int, int> > q;
	q.push({0, 0, 0});
	dist[0][0][0] = dist[0][0][1] = 1;

	while (!q.empty()) {
		auto [x, y, broke] = q.front();
		q.pop();

		if (x == n - 1 && y == m - 1) return dist[x][y][broke];

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

			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

			// 벽인데 아직 안 부쉈다면
			if (board[nx][ny] && !broke && !dist[nx][ny][1]) {
				dist[nx][ny][1] = dist[x][y][0] + 1;
				q.push({nx, ny, 1});
			}
			// 벽이 아니라면
			if (!board[nx][ny] && !dist[nx][ny][broke]) {
				dist[nx][ny][broke] = dist[x][y][broke] + 1;
				q.push({nx, ny, broke});
			}
		}
	}
	return -1;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> board[i][j];
			board[i][j] -= '0';
		}
	}

	cout << bfs();
}

어렵다....
첨엔 부술 벽을 정해놓고 각 경우마다 bfs를 구한 다음에 min 값을 구했음. 당연히 시간 초과..

모든 벽에 대해서 BFS를 돌리면 O(NM * K)

풀이 핵심은 벽을 부수는 상태를 BFS에서 같이 들고 가는 것.

이를 위해 q에 {x, y, broke} 값을 넣어준다.

q.push({i, j, 0}) // 벽을 부수지 않았을 때
q.push({i, j, 1}) // 벽을 부수고 나서부터 쭉

// 벽인데 아직 안 부쉈다면
if (board[nx][ny] && !broke && !dist[nx][ny][1]) {
	dist[nx][ny][1] = dist[x][y][0] + 1;
	q.push({nx, ny, 1});
}
// 벽이 아니라면
if (!board[nx][ny] && !dist[nx][ny][broke]) {
	dist[nx][ny][broke] = dist[x][y][broke] + 1;
	q.push({nx, ny, broke});
}

그래서 이렇게 해주면 된다.

그리고 dist 배열도 두 버전으로 관리한다.

int dist[1000][1000][2];

dist[x][y][0] → 벽을 부수지 않고 (x, y)에 도달한 최단거리
dist[x][y][1] → 벽을 한 번 부수고 (x, y)에 도달한 최단거리

9466 | 텀 프로젝트

#include <bits/stdc++.h>
using namespace std;

int n, s[100001], state[100001], cnt;

const int NOT_VISITED = -1;
const int IN_CYCLE = 0;

void mark_cycle(int start) {
	int cur = s[start];
	state[cur] = IN_CYCLE;
	++cnt;

	while (cur != start) {
		cur = s[cur];
		state[cur] = IN_CYCLE;
		++cnt;
	}
}

void run() {
	cin >> n;
	cnt = 0;

	for (int i = 1; i <= n; ++i) {
		cin >> s[i];
		state[i] = NOT_VISITED;
	}

	for (int i = 1; i <= n; ++i) {
		if (state[i] != NOT_VISITED) continue;

		int cur = i;
		while (1) {
			state[cur] = i;
			cur = s[cur];

			if (state[cur] == i) {	// 사이클 발견
				mark_cycle(cur);
				break;
			}
			if (state[cur] != NOT_VISITED) break;  // 이전 회차에서 탐색했었다면
		}
	}
	cout << n - cnt << '\n';
}

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

	int T;
	cin >> T;

	while (T--) run();
}

못 풀어서 바킹독님 풀이 보고 아이디어 얻어서 다시 풀었다.
bfs 문제집에 들어있었는데 bfs는 아니다🤔

방문 상태 배열을 사용하는 건 맞지만, 단순히 0과 1로는 부족하다.
이번 탐색이 어떤 탐색에서 시작된 건지, "탐색의 고유 번호"를 저장해야 한다.

예를 들어 i번 학생에서 탐색을 시작하면, state[i] = i로 저장한다.
그다음 지목한 학생을 따라가면서 다음 노드를 확인하는데,
이때 가능한 상황은 두 가지다:

  1. 현재 탐색에서 이미 지나간 노드를 다시 만나게 되면 → 사이클 발생
  2. 이전 탐색에서 이미 처리된 노드를 만나게 되면 → 사이클이 아님 (중단)

state[cur] = i를 쓰는 이유는
"같은 탐색 안에서 다시 만난 노드만 사이클"로 간주하기 위해서다.

사이클을 발견하기 위해 같은 곳을 또 방문했을 때 멈추는 조건문을 써야 하는데,

만약 이전 회차에서 방문했을 때와 이번 회차에서 방문했을 때 상태값이 같으면 오류가 생긴다.

왜냐면 이전 회차에서 방문한 노드인데 또 만났다고 사이클로 간주해 버리니까.

그리고 탐색이 끝났는데(방문을 했는데도) IN_CYCLE로 상태가 업데이트 되지 않았다면 걔는 사이클이 안 되는 거다. 다음 회차에서도 볼 필요가 없다.

에혀 방문 상태를 꼭 0,1 로만 생각하지 말기!!

복잡할 때 매직넘버 상수화 하기~~
그리고 팀이 안 된 사람 세는 거 = 전체 - 팀 된 사람
이렇게 생각할 수도 있다는 거 얻어가기~

2573 | 빙산

#include <bits/stdc++.h>
using namespace std;

int n, m, cnt;
int board[301][301], sea[301][301], vis[301][301];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

queue<pair<int, int> > q;

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

	// 입력
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> board[i][j];

			// 빙산 count
			if (board[i][j]) ++cnt;
		}
	}

	for (int year = 1;; ++year) {
		// 초기화
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				if (board[i][j] == 0)
					sea[i][j] = 1;
				else
					q.push({i, j});
			}
		}

		// 빙산 녹이기
		while (!q.empty()) {
			auto [x, y] = q.front();
			q.pop();
			for (int dir = 0; dir < 4; ++dir) {
				int nx = x + dx[dir], ny = y + dy[dir];
				if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
				if (sea[nx][ny] && board[x][y]) {
					--board[x][y];
					if (!board[x][y]) --cnt;
					if (!cnt) {
						cout << 0;
						return 0;
					}
				}
			}
		}

		// 빙산 bfs
		int tmp = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				vis[i][j] = 0;
				if (board[i][j] && q.empty()) {
					q.push({i, j});
					vis[i][j] = 1;
					++tmp;
				}
			}
		}

		while (!q.empty()) {
			auto [x, y] = q.front();
			q.pop();
			for (int dir = 0; dir < 4; ++dir) {
				int nx = x + dx[dir], ny = y + dy[dir];
				if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
				if (!board[nx][ny] || vis[nx][ny]) continue;

				q.push({nx, ny});
				vis[nx][ny] = 1;
				++tmp;
			}
		}

		// 확인
		if (tmp != cnt) {
			cout << year;
			return 0;
		}
	}
}

으으 혼자 풀긴 했는데 너무 오래 걸렸다;;
이건 복잡하게 풀 수밖에 없는 것 같다...

profile
오젼
이전 포스트

[바킹독의 실전 알고리즘] 복습 - 0x06, 0x07, 0x08

다음 포스트

[바킹독의 실전 알고리즘] 복습 - 0x09 (2)

0개의 댓글