BFS

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/23887 🧐 관찰 및 접근 # 설명을 대충 읽는데, BFS맛이 난다 허걱, 최대 학생이 25000명이라 나이브하게는 조금 곤란하긴 하다 근데 뭔가 트리처럼 해석할 수도 있을 것 같은데? MST인가? 아 근데 좀 유향 그래프? 맛인데… 위상정렬이네 이거 엥? 근데 이게 $2$번 학생이 $5, 6$번한테 받을 수 있다고해서 무조건 $5$번한테만 받는건 아니네? 그러면 다시 트리맛으로? 그러면 뭔가 트리의 지름을 최소화하는 느낌으로 가야하는 것 같은데… 그래프에서 가장 먼 두 점을 어떻게 구할 수 있을까? ???????? 아니 문제에서 $S$가 주어지는거였네 그러면 그냥 BFS를 돌리자 구현이 상당히 재밌다! 💻 풀이 # 코드 (C++): void solve(){ int N, M, K; cin >> N >> M >> K; vector<vector<int>> board(N, vector<int>(M, 0)); vector<pii> students(K+1); vector<bool> visited(K+1); rep(i, 1, K+1){ int x, y; cin >> x >> y; x--; y--; students[i] = {x, y}; board[x][y] = i; } int S; cin >> S; set<int> Q; Q.insert(S); visited[S] = true; vector<vector<int>> links(K+1); vector<int> dx = {-1, -1, -1, 0, 0, 1, 1, 1}; vector<int> dy = {-1, 0, 1, -1, 1, -1, 0, 1}; while(!Q.empty()){ set<int> nQ; for(auto cur: Q){ auto [cx, cy] = students[cur]; rep(d, 0, 8){ int nx = cx + dx[d]; int ny = cy + dy[d]; if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue; if(board[nx][ny] == 0) continue; int nxt = board[nx][ny]; if(visited[nxt]) continue; visited[nxt] = true; links[cur].push_back(nxt); nQ.insert(nxt); } } swap(Q, nQ); } rep(i, 1, K+1) if(!visited[i]){ cout << -1; return; } vector<int> sz(K+1); function<void(int)> dfs = [&](int cur){ sz[cur] = 1; for(auto nxt: links[cur]){ dfs(nxt); sz[cur] += sz[nxt]; } }; dfs(S); rep(i, 1, K+1) cout << sz[i] << ' '; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/16940 🧐 관찰 및 접근 # 풀이1 문제 그대로 큐에 넣으면서 시뮬레이션해볼 수 있겠다. 같은 레벨 안에서 원하는대로 선택할 수 있으니, 다음으로 들려야하는걸 셋으로 잘 관리하면서 해보자. 풀이2 현재 내가 있는 노드, 그리고 다음 노드를 큐에 넣을 수 있는지를 체크하는 노드 두가지로 문제를 시뮬레이션하자. cidx에서 nidx로 갈 수 있으면 nidx++를 하고, 없을때 cidx를 ++하자. nidx가 N에 닿지 못했다면 불가능한 것이다. 이 풀이는 트리가 아닌 그래프에서만 가능하다! 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<vector<int>> links(N+1); rep(i, 0, N-1){ int u, v; cin >> u >> v; links[u].push_back(v); links[v].push_back(u); } vector<int> order(N); bitset<100001> visited; rep(i, 0, N) cin >> order[i]; queue<set<int>> v; v.push({1}); visited[1] = true; int idx = 0; while(idx < N){ set<int> nset; while(!v.empty() && v.front().empty()) v.pop(); if(v.empty()){ cout << 0; return; } if(v.front().count(order[idx]) == 0){ cout << 0; return; } int cur = order[idx]; v.front().erase(cur); for(int nxt: links[cur]){ if(visited[nxt]) continue; visited[nxt] = true; nset.insert(nxt); } v.push(nset); idx++; } cout << 1; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/7562 🧐 관찰 및 접근 # 가중치가 없으니, 간단한 BFS로 풀릴 것 같다. 시간복잡도는 $O(V + E) \approx O(N^2)$이다. 💻 풀이 # 코드 (C++): void solve(){ int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2}; int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1}; int N; cin >> N; vector<vector<int>> board(N, vector<int>(N, -1)); int sx, sy, ex, ey; cin >> sx >> sy >> ex >> ey; queue<pii> q; q.push({sx, sy}); board[sx][sy] = 0; while(!q.empty()){ auto [cx, cy] = q.front(); q.pop(); if(cx == ex && cy == ey){ cout << board[cx][cy] << "\n"; return; } rep(d, 0, 8){ int nx = cx + dx[d]; int ny = cy + dy[d]; if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue; if(board[nx][ny] == -1){ board[nx][ny] = board[cx][cy] + 1; q.push({nx, ny}); } } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/5925 🧐 관찰 및 접근 # X로 그려지는 영역이 3개가 있고, 최소한의 비용으로 이들을 연결해야한다. 멀티 소스 BFS와 같은 맛으로 가능할 것 같다. 3개니까 전수조사 해도 되겠지. 아, 근데 좀 사고인 경우가 있구나. ..... ..X.. .X.X. ..... 위와 같은 경우에, 하나만으로도 칠할 수 있는 것 같다. 위와 같은 경우에, 세 그룹이 한 정점에서 무조건 모이게 된다. 따라서 빈 정점을 잡고, 거기서 세 그룹까지의 최단경로를 이용하자. 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; vector<string> S(N); rep(i, 0, N) cin >> S[i]; vector<vector<int>> board(N, vector<int>(M)); int color = 0; rep(i, 0, N) rep(j, 0, M) { if(S[i][j] == 'X' && board[i][j] == 0){ queue<pii> Q; Q.push({i, j}); board[i][j] = ++color; while(!Q.empty()){ auto [cx, cy] = Q.front(); Q.pop(); rep(d, 0, 4){ int nx = cx + dx[d]; int ny = cy + dy[d]; if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue; if(S[nx][ny] == 'X' && board[nx][ny] == 0){ board[nx][ny] = color; Q.push({nx, ny}); } } } } } vector<ll> dists; auto getDist = [&](int c1, int c2) -> ll { vector<vector<int>> dist(N, vector<int>(M, -1)); queue<pii> Q; rep(i, 0, N) rep(j, 0, M){ if(board[i][j] == c1){ dist[i][j] = 0; Q.push({i, j}); } } while(!Q.empty()){ auto [cx, cy] = Q.front(); Q.pop(); rep(d, 0, 4){ int nx = cx + dx[d]; int ny = cy + dy[d]; if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue; if(board[nx][ny] == c2){ return dist[cx][cy]; } if(board[nx][ny] == 0 && dist[nx][ny] == -1){ dist[nx][ny] = dist[cx][cy] + 1; Q.push({nx, ny}); } } } return (ll)1e18; }; rep(i, 1, 4) rep(j, i+1, 4) dists.push_back(getDist(i, j)); sort(all(dists)); ll ans = dists[0] + dists[1]; auto getDist2 = [&](int cx, int cy, int c) -> ll { vector<vector<int>> dist(N, vector<int>(M, -1)); queue<pii> Q; dist[cx][cy] = 0; Q.push({cx, cy}); while(!Q.empty()){ auto [x, y] = Q.front(); Q.pop(); rep(d, 0, 4){ int nx = x + dx[d]; int ny = y + dy[d]; if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue; if(board[nx][ny] == c){ return dist[x][y]; } if(board[nx][ny] == 0 && dist[nx][ny] == -1){ dist[nx][ny] = dist[x][y] + 1; Q.push({nx, ny}); } } } return (ll)1e18; }; rep(i, 0, N) rep(j, 0, M) if(board[i][j] == 0){ ans = min(ans, getDist2(i, j, 1) + getDist2(i, j, 2) + getDist2(i, j, 3) + 1); } cout << ans << "\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/5214 🧐 관찰 및 접근 # 나이브하게 생각해볼까? 인접 리스트로 간선을 저장한다고 생각하면, $M\binom{K}{2} \approx MK^2$ 개의 정보가 저장된다. 그러면 BFS의 시간복잡도는 $O(V+E)$ 니까 조금 곤란한데… 잘 생각해보면, (1, 2, 3, 4), (2, 3, 4, 5) 하이퍼튜브가 있다고 가정하면, 겹치는 정보가 너무나도 많다! 첫 하이퍼튜브를 타고 2, 3, 4번 역에 1회만에 도착했다면, 두번째 하이퍼튜브에서 2, 3, 4번이 서로를 움직일 필요가 없다. 하이퍼튜브는 최대 1000개 존재한다. 또한 한 역은 최대 1000개의 하이퍼튜브에 속한다. 하이퍼튜브만 따로 정리해서, 그 안에서 움직이면 되지 않을까? 💻 풀이 # 코드 (C++): void solve(){ cin >> N >> K >> M; rep(i, 0, M){ rep(j, 0, K){ int x; cin >> x; inhyper[x].push_back(i); hypertube[i].push_back(x); } } rep(i, 1, N+1) dist[i] = -1; dist[1] = 1; queue<int> q; q.push(1); while(!q.empty()){ int cur = q.front(); q.pop(); if(cur == N) break; for(int htube : inhyper[cur]){ for(int nxt : hypertube[htube]){ if(dist[nxt] == -1){ dist[nxt] = dist[cur] + 1; q.push(nxt); } } hypertube[htube].clear(); // 이미 방문한 하이퍼튜브는 볼일이 없다 } } cout << dist[N] << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/23086 🧐 관찰 및 접근 # 그래프와 간선이 주어졌을때, 특정 시점에 이분 그래프인가?를 찾는 문제이다. 이분그래프를 판정하는데에는 $O(N+M)$의 시간이 걸린다. 직관적으로 생각해보면, 리스트에 쓰인 차례대로 친한 친구를 절교시킬 수 있으므로, 리스트를 뒤집어서 하나씩 간선을 이어가며 해당 그래프가 이분 그래프인지 판정하는 방법을 쓸 수 있을 것이다. 이때 시간 복잡도는 $O(K(N+M))$이다. 이는 너무 느리다! 문제 상황을 조금 더 관찰해보자. $\text{ans}$개의 친한 친구 쌍을 절교시켜 이분 그래프가 성립하도록 했다면, $\text{ans}+1$개의 쌍을 절교시켰을때도 마찬가지로 이분그래프일 것이다. $0 \leq a \leq K$인 $a$에 대해, 이분그래프가 성립하는지는 단조성이 존재한다! **매개변수 탐색(파라메트릭 서치)**가 가능하다. 💻 풀이 # 코드 (C++): int N, M, K; vector<pair<int, int>> links[100010]; // (nxt, idx) vector<int> prohibit_list; int color[100010]; // 0: unvisited, 1: group A, 2: group B bool prohibited[200010]; bool isBipartite(int cnt){ rep(i, 1, M+1) prohibited[i] = false; rep(i, 0, cnt) prohibited[prohibit_list[i]] = true; rep(i, 1, N+1) color[i] = 0; rep(i, 1, N+1) if(color[i] == 0){ queue<int> Q; Q.push(i); color[i] = 1; while(!Q.empty()){ int cur = Q.front(); Q.pop(); for(auto [nxt, idx]: links[cur]){ if(prohibited[idx]) continue; if(color[nxt] == 0){ color[nxt] = (color[cur] == 1 ? 2 : 1); Q.push(nxt); } else if(color[nxt] == color[cur]){ return false; } } } } return true; } void solve(){ cin >> N >> M >> K; rep(i, 1, M+1){ int u, v; cin >> u >> v; links[u].push_back({v, i}); links[v].push_back({u, i}); } rep(i, 0, K){ int p; cin >> p; prohibit_list.push_back(p); } // 모두 금지했을때 이분 그래프인가? if(!isBipartite(K)){ cout << -1; return; } // 파라메트릭 서치 int ok = K, ng = -1; while(ok - ng > 1){ int mid = (ok + ng) >> 1; if(isBipartite(mid)) ok = mid; else ng = mid; } cout << ok << "\n"; int groupA_sz = 0, groupB_sz = 0; isBipartite(ok); rep(i, 1, N+1) color[i] == 1 ? groupA_sz++ : groupB_sz++; cout << min(groupA_sz, groupB_sz) << ' ' << max(groupA_sz, groupB_sz) << "\n"; } 🔒 구현 코드 잠금