중급반 5주차 풀이 - DFS, BFS, 백트래킹
1. [1260] DFS와 BFS (Silver II)
DFS와 BFS를 구현하는 문제입니다.
사전순으로 방문해야 하니, 인접 리스트 adj를 정렬해야 합니다.
시간복잡도는 \( O(V+E) \)가 됩니다.
+ 인접 행렬을 사용할 경우, DFS와 BFS의 시간복잡도가 \( O(V^2) \)이 됩니다.
int n, m;
vector<int> adj[1020];
bool chk[1020];
void dfs(int now){
chk[now] = 1; cout << now << ' ';
for (int nxt : adj[now]){
if (chk[nxt]){ continue; }
dfs(nxt);
}
}
int dis[1020];
void bfs(int st){
memset(dis, -1, sizeof(dis));
queue<pi2> q; q.push({st, 0}); dis[st] = 0;
while (!q.empty()){
int now = q.front().fr, dst = q.front().sc;
q.pop();
cout << now << ' ';
for (int nxt : adj[now]){
if (dis[nxt] != -1){ continue; }
q.push({nxt, dst+1}); dis[nxt] = dst+1;
}
}
}
void Main(){
int n, m, st; cin >> n >> m >> st;
while (m--){
int v, w; cin >> v >> w;
adj[v].push_back(w); adj[w].push_back(v);
}
for (int i = 1; i <= n; i++){ sort(all(adj[i])); }
dfs(st); cout << endl; bfs(st);
}2. [2178] 미로 탐색 (Silver I)
2차원 배열에서 BFS를 돌려주면 됩니다.
이 때, \( (y, x) \)가 정점이 되고, \( (y, x) \leftrightarrow (y \pm 1, x) \)와 \( (y, x) \leftrightarrow (y, x \pm 1) \)이 간선이 됩니다.
입력이 붙어서 들어오는데, char를 사용해서 1글자씩 입력받을 수도 있고
아니면 string 배열로 맵을 저장할 수도 있습니다.
const int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, 1, 0, -1};
int mp[120][120];
int dis[120][120];
void Main(){
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
char ch; cin >> ch; mp[i][j] = ch-'0';
}
}
memset(dis, -1, sizeof(dis));
queue<pi3> q; q.push({ {1, 1}, 1 }); dis[1][1] = 1;
while (!q.empty()){
int y = q.front().fr.fr, x = q.front().fr.sc;
int dst = q.front().sc; q.pop();
if (y==n && x==m){ cout << dst; return; }
for (int k = 0; k < 4; k++){
int yy = y+dy[k], xx = x+dx[k];
if (0 > yy || yy > n){ continue; }
if (0 > xx || xx > m){ continue; }
if (mp[yy][xx] == 0){ continue; }
if (dis[yy][xx] != -1){ continue; }
q.push({ {yy, xx}, dst+1 }); dis[yy][xx] = dst+1;
}
}
}3. [9663] N-Queen (Gold V)
가능한 모든 경우의 수를 백트래킹으로 돌려주면 됩니다.
이러면 시간 초과가 뜰 것 같지만, 초반 부분에서 커팅되는 부분이 많아서 시간 내에 돌아갑니다.
TODO: 풀이 더 자세히 작성
시간복잡도는 커팅이 동반된 \( O(N!) \)입니다.
TODO: 더 작은 상한을 계산할 수 있을까?
int n;
bool mp[20][20];
bool pos(int y, int x){
for (int yp = 1; yp <= y; yp++){
if (mp[yp][x]){ return 0; }
if (1 <= x-y+yp && mp[yp][x-y+yp]){ return 0; }
if (x+y-yp <= n && mp[yp][x+y-yp]){ return 0; }
}
return 1;
}
int ans;
void btk(int y){
if (y > n){ ans += 1; return; }
for (int x = 1; x <= n; x++){
if (pos(y, x)){
mp[y][x] = 1; btk(y+1);
mp[y][x] = 0;
}
}
}
void Main(){
cin >> n;
btk(1); cout << ans;
}1번 풀이처럼 지금 설치하는 퀸이 다른 퀸을 보고 있는지 일일이 봐도 되지만,
같은 y / x / x+y / x-y 좌표에만 퀸이 없으면 되기 때문에 이를 따로 체크하면서 풀어도 됩니다.
이렇게 하면 속도가 굉장히 빨라집니다. (5592 ms → 1660 ms)
int n;
bool xc[20], d1c[40], d2c[40];
bool pos(int y, int x){
if (xc[x]){ return 0; }
if (d1c[x+y]){ return 0; }
if (d2c[x-y+20]){ return 0; }
return 1;
}
int ans;
void btk(int y){
if (y > n){ ans += 1; return; }
for (int x = 1; x <= n; x++){
if (pos(y, x)){
xc[x] = d1c[x+y] = d2c[x-y+20] = 1; btk(y+1);
xc[x] = d1c[x+y] = d2c[x-y+20] = 0;
}
}
}
void Main(){
cin >> n;
btk(1); cout << ans;
}이건 사실 풀이가 아니긴 한데...
\( N < 15 \)이기 때문에, 1부터 14까지의 모든 답을 로컬에서 미리 돌린 뒤 전처리해줄 수도 있습니다.
이 풀이는 (로컬에서 돌리는 시간 제외) 0 ms가 나옵니다.
int ans[20] = { 0,
1, 0, 0, 2, 10,
4, 40, 92, 352, 724,
2680, 14200, 73712, 365596
};
void Main(){
int n; cin >> n;
cout << ans[n];
}4. [11724] 연결 요소의 개수 (Silver II)
연결 요소 \( S \)는 아래와 같이 정의됩니다.
- 연결 요소 \( S \) 안의 임의의 두 정점 \( v, w \)에 대해 \( v \Rightarrow w \)의 경로가 존재한다.
- 연결 요소 \( S \) 안의 정점 \( v \)와 밖의 정점 \( w \)에 대해 \( v \Rightarrow w \)의 경로는 존재하지 않는다.
어떤 그래프에서의 연결 요소는 한 정점을 잡은 뒤 DFS를 돌려주면 찾을 수 있고,
연결 요소의 개수는 "모든 정점을 방문하기까지 필요한 DFS의 횟수"입니다.
+ 사실 BFS를 돌려도 결과가 동일하긴 합니다.
그런데 보통 DFS가 구현이 편해서 DFS를 사용하는 경우가 많습니다.
vector<int> adj[1020];
bool chk[1020];
void dfs(int now){
chk[now] = 1;
for (int nxt : adj[now]){
if (chk[nxt]){ continue; }
dfs(nxt);
}
}
void Main(){
int n, m; cin >> n >> m;
while (m--){
int v, w; cin >> v >> w;
adj[v].push_back(w); adj[w].push_back(v);
}
int ans = 0;
for (int v = 1; v <= n; v++){
if (chk[v]){ continue; }
dfs(v); ans += 1;
}
cout << ans;
}5. [1012] 유기농 배추 (Silver II)
"[2178] 미로 탐색" + "[11724] 연결 요소의 개수"입니다.
연결 요소의 개수를 2차원 맵에서 세주면 됩니다.
풀이 역시 둘을 합한 건데, "배추가 있는" (y, x)를 모두 정점으로 변환하고 인접한 칸들을 간선으로 연결시킨 뒤
연결요소의 개수를 세주면 됩니다.
const int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, 1, 0, -1};
int n, m, k;
int mp[60][60];
bool chk[60][60];
void dfs(int y, int x){
chk[y][x] = 1;
for (int k = 0; k < 4; k++){
int yy = y+dy[k], xx = x+dx[k];
if (0 > yy || yy >= n){ continue; }
if (0 > xx || xx >= m){ continue; }
if (mp[yy][xx] == 0){ continue; }
if (chk[yy][xx]){ continue; }
dfs(yy, xx);
}
}
void Main(){
int t; cin >> t;
while (t--){
memset(mp, 0, sizeof(mp)); memset(chk, 0, sizeof(chk));
cin >> m >> n >> k;
while (k--){
int x, y; cin >> x >> y; mp[y][x] = 1;
}
int ans = 0;
for (int y = 0; y < n; y++){
for (int x = 0; x < m; x++){
if (mp[y][x] == 0){ continue; }
if (chk[y][x]){ continue; }
dfs(y, x); ans += 1;
}
}
cout << ans << endl;
}
}6. [2644] 촌수계산 (Silver II)
이런 저런 말이 나와있지만, 사람을 정점으로 보고 부모-자식 관계를 간선으로 보면
두 정점 간의 최단경로를 찾는 문제가 됩니다.
+ 사실 부부 관계 = 0촌이긴 한데, 문제 조건에 의해 부부 관계가 나올 수 없어서 무시해도 됩니다.
vector<int> adj[120];
int dis[120];
void Main(){
memset(dis, -1, sizeof(dis));
int n; cin >> n;
int st, ed; cin >> st >> ed;
int m; cin >> m;
while (m--){
int v, w; cin >> v >> w;
adj[v].push_back(w); adj[w].push_back(v);
}
queue<pi2> q; q.push({st, 0}); dis[st] = 0;
while (!q.empty()){
int now = q.front().fr, dst = q.front().sc;
q.pop();
if (now == ed){ cout << dst; return; }
for (int nxt : adj[now]){
if (dis[nxt] != -1){ continue; }
q.push({nxt, dst+1}); dis[nxt] = dst+1;
}
}
cout << -1;
}7. [2583] 영역 구하기 (Silver I)
[y, x] = (x, y)에서 시작해서 (x+1, y+1)에서 끝나는 직사각형 으로 두면
각 [y, x] 별로 직사각형으로 덮였다 / 안 덮였다를 체크할 수 있고,
안 덮인 칸들만으로 그래프를 이루면 각 영역은 하나의 연결 요소를 이루게 됩니다.
+ 원래 [a, b]는 다른 의미를 가지고 있지만 여기서는 특별히 이렇게 쓰겠습니다.
연결 요소의 개수는 "[11724] 연결 요소 구하기"에서 구해봤으니, 각 연결 요소의 크기를 구해봅시다.
어떤 연결 요소의 크기는 "그 연결 요소 안에 있는 정점의 수"가 됩니다.
즉, DFS 탐색을 하면서 방문한 정점의 수를 세주면 됩니다.
탐색이 끝난 뒤 연결 요소의 크기들을 정렬해야 함에 주의하세요.
const int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, 1, 0, -1};
int n, m, k;
int mp[120][120];
int cnt = 0; bool chk[120][120];
void dfs(int y, int x){
chk[y][x] = 1; cnt += 1;
for (int k = 0; k < 4; k++){
int yy = y+dy[k], xx = x+dx[k];
if (0 > yy || yy >= n){ continue; }
if (0 > xx || xx >= m){ continue; }
if (mp[yy][xx] == 1){ continue; }
if (chk[yy][xx]){ continue; }
dfs(yy, xx);
}
}
void Main(){
cin >> n >> m >> k;
while (k--){
int y1, y2, x1, x2; cin >> x1 >> y1 >> x2 >> y2;
for (int x = x1; x < x2; x++){
for (int y = y1; y < y2; y++){ mp[y][x] = 1; }
}
}
vector<int> ans;
for (int y = 0; y < n; y++){
for (int x = 0; x < m; x++){
if (mp[y][x] == 1){ continue; }
if (chk[y][x]){ continue; }
cnt = 0; dfs(y, x); ans.push_back(cnt);
}
}
sort(all(ans));
cout << ans.size() << endl;
for (int cnt : ans){ cout << cnt << ' '; }
}8. [7562] 나이트의 이동 (Silver II)
2차원 맵을 그래프로 바꾸는 건 "[2178] 미로 탐색"에서 이미 해봤습니다.
하지만, 이번에는 간선을 나이트의 움직임으로 바꿔야 합니다.
나이트의 움직임을 간단히 표현하면, (y±2, x±1) 또는 (y±1, x±2)로 나타낼 수 있습니다.
그러니, 우리가 정의해줬던 dy, dx 배열을 이에 맞게 고치면 됩니다.
/* Knight's Move
8 1
7 2
*
6 3
5 4
*/
const int dy[8] = {-2, -1, 1, 2, 2, 1, -1, -2}, dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int dis[320][320];
void Main(){
int t; cin >> t;
while (t--){
memset(dis, -1, sizeof(dis));
int n; cin >> n;
pi2 st, ed; cin >> st.fr >> st.sc >> ed.fr >> ed.sc;
queue<pi3> q; q.push({st, 0}); dis[st.fr][st.sc] = 0;
while (!q.empty()){
int y = q.front().fr.fr, x = q.front().fr.sc;
int dst = q.front().sc; q.pop();
if (make_pair(y, x) == ed){ cout << dst << endl; break; }
for (int k = 0; k < 8; k++){
int yy = y+dy[k], xx = x+dx[k];
if (0 > yy || yy >= n){ continue; }
if (0 > xx || xx >= n){ continue; }
if (dis[yy][xx] != -1){ continue; }
q.push({ {yy, xx}, dst+1 }); dis[yy][xx] = dst+1;
}
}
}
}9. [7576] 토마토 (Gold V)
각 토마토별로 익은 토마토와의 최단경로를 찾아주면 됩니다.
이는 익은 토마토에서 출발하는 BFS를 여러 번 돌려서 해결할 수 있지만, 이 문제에서 그렇게 했다가는 TLE가 뜨게 됩니다.
그래서, "익은 토마토들"에서 출발하는 BFS를 한 번에 돌려주면 됩니다.
+ 이런 형식의 BFS를 Multisource BFS라고 합니다.
const int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, 1, 0, -1};
int dis[1020][1020];
void Main(){
queue<pi3> q;
int n, m; cin >> m >> n;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cin >> dis[i][j];
if (dis[i][j] == 1){ q.push({ {i, j}, 1 }); }
}
}
while (!q.empty()){
int y = q.front().fr.fr, x = q.front().fr.sc;
int dst = q.front().sc; q.pop();
for (int k = 0; k < 4; k++){
int yy = y+dy[k], xx = x+dx[k];
if (1 > yy || yy > n){ continue; }
if (1 > xx || xx > m){ continue; }
if (dis[yy][xx] != 0){ continue; }
q.push({ {yy, xx}, dst+1 }); dis[yy][xx] = dst+1;
}
}
int ans = 1;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
if (dis[i][j] == -1){ continue; }
if (dis[i][j] == 0){ cout << -1; return; }
ans = max(ans, dis[i][j]);
}
}
cout << ans-1;
}10. [17129] 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 (Gold V)
정신나간 문제처럼 보이지만, 사실 "[2178] 미로 탐색"에서 약간만 더 추가하면 됩니다.
- 시작점이 (1, 1)이 아니라 2의 위치입니다.
- 도착점은 (N, M)이 아니라 3, 4, 5의 위치입니다.
그러니까 그냥 2에서 BFS 돌리고 3, 4, 5 중 가장 가까운 걸 찾으면 됩니다.
const int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, 1, 0, -1};
int mp[3020][3020], dis[3020][3020];
void Main(){
memset(dis, -1, sizeof(dis));
queue<pi3> q;
int n, m; cin >> m >> n;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
char ch; cin >> ch; mp[i][j] = ch-'0';
if (mp[i][j] == 2){ q.push({ {i, j}, 0 }); dis[i][j] = 0; }
}
}
while (!q.empty()){
int y = q.front().fr.fr, x = q.front().fr.sc;
int dst = q.front().sc; q.pop();
if (mp[y][x] >= 3){
cout << "TAK" << endl << dst; return;
}
for (int k = 0; k < 4; k++){
int yy = y+dy[k], xx = x+dx[k];
if (1 > yy || yy > n){ continue; }
if (1 > xx || xx > m){ continue; }
if (mp[yy][xx] == 1){ continue; }
if (dis[yy][xx] != -1){ continue; }
q.push({ {yy, xx}, dst+1 }); dis[yy][xx] = dst+1;
}
}
cout << "NIE";
}11. [2206] 벽 부수고 이동하기 (Gold IV)
\( (y, x) \)만으로 BFS를 돌리기에는 어려워 보이는 문제입니다.
아무리 생각해봐도 '벽을 부순 횟수'가 저장되어야 할 것 같으니 이를 저장해봅시다.
즉, \( DIS_{y, x, c} := \) \( (1, 1) \Rightarrow (y, x) \)로 \( c \)개의 벽을 부숴서 갈 수 있는 최단경로 라고 정의해봅시다.
이제 이러면 문제는 간단해집니다.
최단경로니까 BFS를 써주면 되고, 간선은 인접한 칸들끼리 연결하되 도착점이 벽이라면 \( (y, x, c) \rightarrow (y', x', c+1) \)로 연결해주면 됩니다.
const int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, 1, 0, -1};
int mp[1020][1020], dis[1020][1020][2];
void Main(){
memset(dis, -1, sizeof(dis));
queue<pi4> q;
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
char ch; cin >> ch; mp[i][j] = ch-'0';
}
}
q.push({ {1, 1}, {0, 1} }); dis[1][1][0] = 1;
while (!q.empty()){
int y = q.front().fr.fr, x = q.front().fr.sc;
int c = q.front().sc.fr, dst = q.front().sc.sc; q.pop();
if (y==n && x==m){ cout << dst; return; }
for (int k = 0; k < 4; k++){
int yy = y+dy[k], xx = x+dx[k];
if (1 > yy || yy > n){ continue; }
if (1 > xx || xx > m){ continue; }
int cc = c + mp[yy][xx];
if (cc >= 2){ continue; }
if (dis[yy][xx][cc] != -1){ continue; }
q.push({ {yy, xx}, {cc, dst+1} }); dis[yy][xx][cc] = dst+1;
}
}
cout << -1;
}12. [1987] 알파벳 (Gold IV)
(1, 1)에서 시작해서 갈 수 있는 방향을 하나하나 보면서 그 칸에 적힌 알파벳이 지금까지 등장한 적 없으면 가본다 를 백트래킹으로 돌려주면 됩니다.
시간복잡도는 \( O(4^26) \)이지만, 커팅이 굉장히 많이 됩니다.
TODO: 풀이가 왜 시간 안에 도는지 보이기
const int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, 1, 0, -1};
int n, m;
char mp[22][22];
int ans = 0; bool chk[30];
void btk(int y, int x, int cnt){
//cout << "BTK " << y << ' ' << x << ' ' << cnt << endl;
//cout << "CHK "; for (int i = 0; i < 26; i++){ cout << chk[i] << ' '; } cout << endl << flush;
ans = max(ans, cnt);
for (int k = 0; k < 4; k++){
int yy = y+dy[k], xx = x+dx[k];
//cout << "NXT " << yy << ' ' << xx << endl;
if (1 > yy || yy > n){ continue; }
if (1 > xx || xx > m){ continue; }
if (chk[ mp[yy][xx]-'A' ]){ continue; }
chk[ mp[yy][xx]-'A' ] = 1; btk(yy, xx, cnt+1);
chk[ mp[yy][xx]-'A' ] = 0;
}
}
void Main(){
cin >> n >> m;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){ cin >> mp[i][j]; }
}
chk[ mp[1][1]-'A' ] = 1; btk(1, 1, 1);
chk[ mp[1][1]-'A' ] = 0;
cout << ans;
}13. [2239] 스도쿠 (Gold IV)
입력 제한이 굉장히 친절합니다.
12095번 문제의 코드를 요약하면 "비어있는 칸에 대해 1부터 9까지 넣어보면서 백트래킹하기"이고,
이 코드로 풀리는 입력만이 들어오니 그렇게 짜주면 됩니다.
const int N = 9;
int mp[12][12], res[12][12];
bool row[12][12], col[12][12], box[12][12];
inline int bxi(int y, int x){ return (y-1)/3*3 + (x-1)/3 + 1; }
void btk(int y, int x){
if (x > N){ y += 1; x = 1; }
if (y > N){
for (int i = 1; i <= N; i++){
for (int j = 1; j <= N; j++){ cout << res[i][j]; }
cout << endl;
}
exit(0);
}
if (mp[y][x] != 0){ return btk(y, x+1); }
for (int d = 1; d <= 9; d++){
if (row[y][d]){ continue; }
if (col[x][d]){ continue; }
if (box[bxi(y,x)][d]){ continue; }
row[y][d] = col[x][d] = box[bxi(y,x)][d] = 1; res[y][x] = d; btk(y, x+1);
row[y][d] = col[x][d] = box[bxi(y,x)][d] = 0; res[y][x] = 0;
}
}
void Main(){
for (int i = 1; i <= N; i++){
for (int j = 1; j <= N; j++){
char ch; cin >> ch;
mp[i][j] = ch-'0';
if (mp[i][j] != 0){ int d = mp[i][j];
row[i][d] = col[j][d] = box[bxi(i,j)][d] = 1;
res[i][j] = d;
}
}
}
btk(1, 1);
}14. [1759] 암호 만들기 (Gold V)
\( {}_{L}C_{C} \)개의 조합을 아래 주의 사항에 맞춰서 출력하면 됩니다.
아래는 주의할 사항들입니다.
- 정렬된 문자열이어야 합니다. 그러니, 입력받은 문자를 정렬해줘야 합니다.
- 모음은 1개 이상, 자음은 2개 이상입니다. 하지만 모음만 세도 자음은 (전체 - 모음)으로 셀 수 있습니다.
- 모음 판별에서 오타 내지 맙시다. 모음은 'a', 'e', 'i', 'o', 'u'입니다.
int n, m;
char arr[20];
inline int vwl(char ch){
return ch=='a' || ch=='e' || ch=='i' || ch=='o' || ch=='u';
}
char res[20];
void btk(int idx, int cnt, int vc){
if (idx > n){ int cc = cnt-vc;
if (cnt != m){ return; }
if (vc < 1 || cc < 2){ return; }
for (int i = 1; i <= m; i++){ cout << res[i]; }
cout << endl; return;
}
cnt += 1; res[cnt] = arr[idx]; btk(idx+1, cnt, vc + vwl(arr[idx]));
cnt -= 1; btk(idx+1, cnt, vc);
}
void Main(){
cin >> m >> n;
for (int i = 1; i <= n; i++){ cin >> arr[i]; }
sort(arr+1, arr+n+1);
btk(1, 0, 0);
}15. [1799] 비숍 (Gold I)
\( (y, x) \) 좌표로 생각하면 대각선을 2개나 생각해야 하고, 이는 복잡합니다.
하지만, 가로/세로를 생각하지 않고 대각선만 생각한다면, 입력받은 좌표를 45도 돌린 뒤 룩을 배치하는 문제로 바꿀 수 있습니다.
좌표를 45도 돌리는 방법은 N-Queen에서 사용한 방식처럼 해줄 수 있습니다.
즉, 대각선이 \( y-x = k_1; y+x = k_2 \)임을 이미 알고 있으니, \( (y, x) \rightarrow (k_1, k_2) = (y-x, y+x) \)로 사용해주면 됩니다.
이 때 중간에 들어오는 빈 칸이 생길 수 있는데, 어차피 1이 아니면 못 놓으니 0으로 초기화해주면 됩니다.
int n;
bool mp[22][22];
bool chk[22]; int ans = 0;
void btk(int y, int cnt){
if (cnt + n-y+1 < ans){ return; }
ans = max(ans, cnt);
if (y > n){ return; }
for (int x = 1; x <= n; x++){
if (!mp[y][x]){ continue; }
if (chk[x]){ continue; }
chk[x] = 1; btk(y+1, cnt+1);
chk[x] = 0;
}
return btk(y+1, cnt);
}
void Main(){
cin >> n;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
cin >> mp[n-i+j][i+j-1];
}
}
n = 2*n - 1;
btk(1, 0); cout << ans;
}