1. BFS
BFS의 목적은 임의의 정점에서 시작해서, 모든 정점을 한 번씩 방문하는 것이다.
목적
현재 위치/성분을 기준으로 정해진 경우를 다 해보며 모든 정점을 방문하고 싶을 때 사용할 수 있다. -> 지도형태 입력이 아니여도 사용이 가능하다. + 원래 BF 유형은 입력이 작은데 얘는 적당히 커도 사용이 가능하다.
단 가중치는 0똔느 1일때만 사용가능하다.
단 500만 이한의 간선까지만 버틸 수 있다.
- BFS의 목적은 임의의 정점에서(시작점) 시작해서, 모든 정점을 한 번씩 방문하는 것이다.
- BFS는 최단거리를 구하는 알고리즘 = 최소비용 문제(<-> DFS 는 최단거리를 구할 수 없음)
- BFS는 최소를 구한다는 성질이 있다.
※ 단 모든 가중치가 0 또는 1일 때 가능
키워드
- 가중치 0또는 1
- 미로
- 최소 거리
조건
- 최소 비용 문제이어야 한다.
- 간선의 가중치가 1이어야 한다.
- 정점과 간선의 개수가 적어야 한다. 시간복잡도가 O(V+E) 이기 때문에 500만 정도의 간선까지는 버틸 수 있음
알고리즘
- BFS를 그래프로 변환
- 기본 추가 라이브러리
#include <iostream>
#include <functional>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>문제
1697 숨바꼭질
분석
최소시간을 구하는 문제 -> BFS 문제
이동 방법은 총 3가지
cur +1 / cur -1 / cur * 2
따라서 위의 방법 대로 큐에 넣고 도착할때까지 반복해서 식을 돌리어 주면 됨
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans, i, j, n, m;
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(100001,-1);
queue<int> q;
q.push(n);
a[n] = 0;
while (!q.empty()) {
int now = q.front();
q.pop();
if (now - 1 >= 0 and (a[now - 1] == -1 or a[now-1]>a[now]+1)) {
a[now - 1] = a[now] + 1;
q.push(now - 1);
}
if (now + 1 < 100001 and (a[now + 1] == -1 or a[now+1]>a[now]+1)) {
a[now + 1] = a[now] + 1;
q.push(now + 1);
}
if (now * 2 < 100001 and (a[now * 2] == -1 or a[now * 2] > a[now] + 1)) {
a[now * 2] = a[now] + 1;
q.push(now * 2);
}
}
cout << a[m] << '\n';
}개선판 : memset을 사용하여 배열 하나를 줄였습니다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstring>
#define ll long long
#define max 100001
using namespace std;
int d[max];
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
freopen("input.txt", "r", stdin);
int n, k;
cin >> n >> k;
memset(d, -1, sizeof(d));
d[n] = 0;
queue<int> q;
q.push(n);
while (!q.empty()) {
int t = q.front();
q.pop();
if (t - 1 >= 0 && d[t - 1] == -1) {
d[t - 1] = d[t] + 1;
q.push(t - 1);
}
if (t + 1 < 100001 && d[t + 1] == -1) {
d[t + 1] = d[t] + 1;
q.push(t + 1);
}
if (2 * t < 100001 && d[2 * t] == -1) {
d[2 * t] = d[t] + 1;
q.push(2 * t);
}
}
cout << d[k] << endl;
}13913 숨바꼭질 4
이번에는 시간이 아닌 방법을 구하는 문제
이러한 문제를 역추적 문제라 부름(백트래킹 문제)
※ 앞의 LIS 문제 풀때 섰던 백트래킹 방식을 그대로 사용하면 됨
이때 백트래킹은 추가 배열을 쓰되 출력하는 방법은 2가지 구현방법을 가짐
1. 재귀를 이용하는 방법
-> 이때는 재귀로 호출하여 돌아감
2. 스택을 이용하는 방법
-> 이때는 스택에 모두 넣고 빼면서 돌아감
주의! 가장 간지가 남
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define ll long long
#define len 100001
using namespace std;
bool check[len] = { false };
int dist[len];
int back[len];
void go(int n, int k) {
if (k != n) {
go(n, back[k]);
}
cout << k << ' ';
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
freopen("input.txt", "r", stdin);
int n, k;
cin >> n >> k;
int max = k * 2 + 1;
queue<int> q;
q.push(n);
dist[n] = 0;
check[n] = true;
back[n] = n;
while (!q.empty()) {
int cur = q.front();
q.pop();
if (cur - 1 >= 0 && check[cur-1] == false) {
check[cur - 1] = true;
q.push(cur - 1);
back[cur - 1] = cur;
dist[cur - 1] = dist[cur] + 1;
}
if (cur + 1 < len && check[cur + 1] == false) {
check[cur + 1] = true;
q.push(cur + 1);
back[cur + 1] = cur;
dist[cur + 1] = dist[cur] + 1;
}
if (cur * 2 < len && check[cur * 2] == false) {
check[cur * 2] = true;
q.push(cur * 2);
back[cur * 2] = cur;
dist[cur * 2] = dist[cur] + 1;
}
}
cout << dist[k]<<'\n';
go(n, k);
}#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans, i, j, n, m;
vector<int> a(100001, -1);
vector<int> from(100001, -1);
void go(int m) {
if (from[m] == -1) {
cout << m << ' ';
return;
}
go(from[m]);
cout << m << ' ';
}
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
queue<int> q;
q.push(n);
a[n] = 0;
while (!q.empty()) {
int now = q.front();
q.pop();
if (now - 1 >= 0 and (a[now - 1] == -1 or a[now-1]>a[now]+1)) {
from[now - 1] = now;
a[now - 1] = a[now] + 1;
q.push(now - 1);
}
if (now + 1 < 100001 and (a[now + 1] == -1 or a[now+1]>a[now]+1)) {
from[now + 1] = now;
a[now + 1] = a[now] + 1;
q.push(now + 1);
}
if (now * 2 < 100001 and (a[now * 2] == -1 or a[now * 2] > a[now] + 1)) {
from[now *2] = now;
a[now * 2] = a[now] + 1;
q.push(now * 2);
}
}
cout << a[m] << '\n';
go(m);
}2. BFS, 정점을 나누다
사실상 한 개의 경로를 구한 이후의 더 짧은 경로를 탐색하는 문제하는 문제가 될것이다.
하지만 문제에서 조건이 추가되어서 파란선은 한 번만 사용 가능하다면?
그 경우에는 한개의 정점도 두가지의 경우로 나누어야 한다. 파란간선을 사용한 경우와 사용하지 않은 경우로
결과적으로 그림으로 그려보면 이런식으로 정점을 나누게 된다
말은 거창하지만 bfs는 입력되는 배열/
문제
이모티콘 14226
screen 과 clipboard가 존재하는데 문제는 clipboard에 몇개의 이모티콘이 있었는지 알 수가 없다.
방법은 3가지로
1. 스크린에 있는 이모티콘을 모두 클립보드에 복사한다.
2. 클립보드에 있는 이모티콘을 모두 스크린에 복사한다.
3. 스크린에서 이모티콘 한개를 지운다.
따라서 시작할때 클립보드에 저장되어 있는 이모티콘의 갯수를 0부터 모두 구하여 BFS 형태로 문제를 풀 수 밖에 없다.
문제를 풀기 위해 2차원 배열을 선언하여 s,c 위치는 스크린과 클립보드의 이모티콘 갯수이고 변수내에 저장된 값을 s,c 가 될때까지 사용된 시간이다.
만약 2차원 배열을 사용한다면 행과 열이 각각 무슨 의미를 가지는지 정의하고 사용하자
또한 문제 풀이를 위해 2차원 배열을 초기화 하려면
#include <cstring>
int b[1001][1001];
memset(b,-1,sizeof(b));로 처리하면 2차원 배열이 모두 -1로 초기화 된다.
추가로 파이썬과 같이 두개의 변수를 한번에 받을려면
#include <functional>
tie(s,c) = q.front();을 이용하는 것도 좋다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <functional>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstring>
#define ll long long
#define len 1001
using namespace std;
int b[len][len];
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
freopen("input.txt", "r", stdin);
int t;
cin >> t;
memset(b, -1, sizeof(b));
queue<pair<int,int>> q;
q.push(make_pair(1, 0));
b[1][0] = 0;
int s, c;
while (!q.empty()) {
tie(s, c) = q.front();
q.pop();
if (b[s][s] == -1) {
q.push(make_pair(s, s));
b[s][s] = b[s][c] + 1;
}
if (s + c <= t && b[s + c][c] == -1) {
q.push(make_pair(s + c, c));
b[s + c][c] = b[s][c] + 1;
}
if (s - 1 >= 0 && b[s - 1][c] == -1) {
q.push(make_pair(s - 1, c));
b[s - 1][c] = b[s][c] + 1;
}
}
int ans = -1;
for (int i = 0; i <= t; ++i) {
if (b[t][i] != -1) {
if (b[t][i] < ans || ans == -1) {
ans = b[t][i];
}
}
}
cout << ans << '\n';
}3. 덱 사용하기
덱 문제는 BFS 문제 중에서도 가중치가 두가지이상으로 갈리는 경우에 사용할 수 있다.
예를 들어 가중치가 0과 1 이라면 덱의 앞부분은 가중치가 0인 걸 집어 넣고 뒷부분은 가중치가 1인것을 집어 넣는 것으로 큐를 두개 이용할 것을 덱 하나만 이용해서 풀 수 가 있다.
문제
숨바꼭질 3 13549
숨바꼭질 3이 대표적인 가중치가 두개인 문제이며
앞에서 풀었던 숨바꼭질이 가중치가 모두 1이였다면, 여기에서는 순간이동의 가중치가 0이되기 때문에 큐를 사용하여 풀어야 한다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <functional>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>
#include <cstring>
#define ll long long
#define len 100001
using namespace std;
bool check[len];
int dist[len];
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
freopen("input.txt", "r", stdin);
int n, m;
cin >> n >> m;
deque<int> d;
dist[n] = 0;
check[n] = true;
d.push_back(n);
while (!d.empty()) {
int cur = d.front();
d.pop_front();
if (cur * 2 < len && check[cur * 2] == false) {
d.push_front(cur * 2);
dist[cur * 2] = dist[cur];
check[cur * 2] = true;
}
if (cur - 1 >= 0 && check[cur - 1] == false) {
d.push_back(cur - 1);
dist[cur - 1] = dist[cur] + 1;
check[cur - 1] = true;
}
if (cur + 1 < len && check[cur + 1] == false) {
d.push_back(cur + 1);
dist[cur + 1] = dist[cur] + 1;
check[cur + 1] = true;
}
}
cout << dist[m] << '\n';
}알고스팟 1261
같이사용하면 좋은 함수
scanf("%1d",m[i][j]);BFS로 돌아다니며 최소로 벽을 부수는 횟수를 계산하는 문제이다.
중요한 것은 가중치가 2개이기 때문에 덱을 쓰던가 아니면 큐를 두개 써서 큐를 바꾸어 가면 쉽게 풀 수 있다.
위에서는 덱을 사용하였기에 여기에서는 큐를 사용해서 풀어보았다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <functional>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>
#include <cstring>
#define ll long long
#define len 101
using namespace std;
int map[len][len];
int check[len][len];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { -1,1,0,0 };
int main(void) {
freopen("input.txt", "r", stdin);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
scanf("%1d", &map[i][j]);
check[i][j] = -1;
}
}
queue<pair<int ,int>> q;
queue<pair<int, int>> next_queue;
q.push(make_pair(0, 0));
check[0][0] = 0;
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for (int i = 0; i < 4; ++i) {
int ny = y + dy[i];
int nx = x + dx[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
if (check[ny][nx] == -1) {
if (map[ny][nx] == 1) {
check[ny][nx] = check[y][x] + 1;
next_queue.push(make_pair(ny, nx));
}
else {
check[ny][nx] = check[y][x];
q.push(make_pair(ny, nx));
}
}
}
}
if (q.empty()) {
q = next_queue;
next_queue = queue<pair<int, int>>();
}
}
cout << check[m-1][n-1] << '\n';
}4. 연습문제
문제
16928 뱀과 사다리 게임
문제는 일렬로 생긴 100짜리 칸에서 뱀을 만나는 아래로 사다리를 만나면 위쪽으로 움직여서 주사위를 조작해 최소 횟수만에 100번째 칸에 도착하는 문제이다.
기존에 풀던 BFS 방식하고 크게 다르지도 않고 BF로 풀기에는 제한이 크기 때문에 BFS를 이용해 문제를 풀어보자
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans, i, j, n, m;
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
queue<int> q;
int n, m;
cin >> n >> m;
vector<int> map(101);
vector<int> next(101);
for (i = 0; i < 101; ++i) {
map[i] = -1;
next[i] = i;
}
for (i = 0; i < n + m; ++i) {
int s, e;
cin >> s >> e;
next[s] = e;
}
q.push(1);
map[1] = 0;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = 1; i <= 6; ++i) {
int y = x + i;
if (y > 100) continue;
y = next[y];
if (map[y] == -1) {
q.push(y);
map[y] = map[x] + 1;
}
}
}
cout << map[100] << '\n';
}16948 데스 나이트
가장 기본적인 경로 탐색 문제
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans, i, j, n, m;
int dx[6] = { -2,-2,0,0,2,2 };
int dy[6] = { -1,1,-2,2,-1,1 };
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
queue<pair<int,int>> q;
cin >> n;
int sx, sy, tx, ty;
cin >> sx >> sy >> tx >> ty;
vector<vector<int>> map(n, vector<int>(n,-1));
q.push(make_pair(sx, sy));
map[sx][sy] = 0;
while (!q.empty()) {
int x, y;
tie(x, y) = q.front(); q.pop();
for (i = 0; i < 6; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 or nx>=n or ny < 0 or ny>=n) continue;
if (map[nx][ny]==-1) {
map[nx][ny] = map[x][y] + 1;
q.push(make_pair(nx, ny));
if (nx == tx and ny == ty) break;
}
}
}
cout << map[tx][ty] << '\n';
}9019 DSLR
A->B로 만드는 방법을 출력하는 문제이다. 이 문제를 풀기 위해 다음 3가지가 필요하다.
1. 최솟값을 구하기 위한 배열
2. 어떤 과정을 거치었는지 확인하는 배열
3. 과정의 방법을 저장하는 배열
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int i, j, n, m;
int from[10001];
char how[10001];
int dist[10001];
void print(int a, int b) {
if (b == a) {
return;
}
print(a, from[b]);
cout << how[b];
}
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int a, b;
cin >> a >> b;
queue<int> q;
q.push(a);
memset(from, 0, sizeof(from));
memset(dist, -1, sizeof(dist));
memset(how, 0, sizeof(how));
dist[a] = 0;
from[a] = a;
while (!q.empty()) {
int now = q.front();
q.pop();
//cout<<now<<'\n';
int y = (now * 2) % 10000;
if (dist[y] == -1) {
dist[y] = dist[now] + 1;
from[y] = now;
how[y] = 'D';
q.push(y);
}
y = now - 1;
if (y < 0) y = 9999;
if (dist[y] == -1) {
dist[y] = dist[now] + 1;
from[y] = now;
how[y] = 'S';
q.push(y);
}
y = (now % 1000) * 10 + now / 1000;
if (dist[y] == -1) {
dist[y] = dist[now] + 1;
from[y] = now;
how[y] = 'L';
q.push(y);
}
y = (now / 10) + (now%10) * 1000;
if (dist[y] == -1) {
dist[y] = dist[now] + 1;
from[y] = now;
how[y] = 'R';
q.push(y);
}
}
print(a,b);
cout << '\n';
}
}14502 연구소
N X M 크기의 직사각형 지도가 있고, 1X1 칸으로 나뉘어져 있다. 일부 빈 칸에 바이러스가 있고, 인접한 빈 칸으로 게속 퍼져 나간다. 벽을 3개 세워서 바이러스가 퍼질 수 없는 곳의 크기를 구하는 문제
탐색 : O(NM)
벽을 세우는 시간 : O((NM)^3) x O(NM) = O((NM)^4) = 2^24 = 16,777,216
N개 중에서 K를 구하는 문제는 재귀를 이용해서 풀고 정해져 있는 경우라면 중첩 for문이 보다 구현하기 편할 수 있다.
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans,i, j, n, m;
int map[10][10];
int dx[4] = { -1,1,0,0, };
int dy[4] = { 0,0,-1,1 };
int bfs() {
queue<pair<int,int>> q;
vector<vector<int>> cmap(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cmap[i][j] = map[i][j];
if (map[i][j] == 2) {
q.push(make_pair(i, j));
}
}
}
while (!q.empty()) {
int x, y;
tie(x, y) = q.front(); q.pop();
for (i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
if (cmap[nx][ny] == 0) {
cmap[nx][ny] = 2;
q.push(make_pair(nx, ny));
}
}
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (cmap[i][j] == 0) cnt += 1;
}
}
return cnt;
}
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
cin >> n >> m;
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) {
cin >> map[i][j];
}
}
for (int x1 = 0; x1 < n; ++x1) {
for (int y1 = 0; y1 < m; ++y1) {
if (map[x1][y1] != 0) continue;
for (int x2 = 0; x2 < n; ++x2) {
for (int y2 = 0; y2 < m; ++y2) {
if (map[x2][y2] != 0 or (x1==x2 and y1==y2)) continue;
for (int x3 = 0; x3 < n; ++x3) {
for (int y3 = 0; y3 < m; ++y3) {
if (map[x3][y3] != 0 or (x3==x1 and y3==y1) or (x3==x2 and y3==y2) ) continue;
map[x1][y1] = 1;
map[x2][y2] = 1;
map[x3][y3] = 1;
ans=max(ans,bfs());
map[x1][y1] = 0;
map[x2][y2] = 0;
map[x3][y3] = 0;
}
}
}
}
}
}
cout << ans << '\n';
}12886 돌 그룹
각 그룹에는 돌이 A,B,C개가 있다. 돌은 다음의 단계별로 움직이게 된다.
1. 크기가 같지 않은 두 그룹을 고른다. 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 한다.
2. X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X로 만든다.
3. A,B,C가 주어졌을 떄, 모든 그룹에 들어있는 돌의 개수를 같게 만들 수 있는지 구하는 문제
하지만 문제는 공간을 너무 많이 쓴다는 것에 있다. 최악의 경우 1500^3 만큼의 공간을 쓰기 때문에 3GB의 공간을 차지 한다.
그래서 A와 B의 갯수를 알고 있다면 C는 없어도 된다. C = N-A-B 이기 때문
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans,i, j, n, m;
bool check[1501][1501];
void go(int a, int b) {
if (check[a][b]) return;
check[a][b] = true;
int d[3] = { a,b,n - a - b };
for (i = 0; i < 3; ++i) {
for (j = 0; j < 3; ++j) {
if (d[i] < d[j]) {
int temp[3] = { a,b,n - a - b };
temp[i] += d[i];
temp[j] -= d[i];
go(temp[0],temp[1]);
}
}
}
}
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
int a, b, c;
cin >> a >> b >> c;
n = a + b + c;
if (n % 3 != 0) {
cout << "0" << '\n';
return 0;
}
go(a, b);
if (check[n / 3][n / 3]) {
cout << "1" << '\n';
return 0;
}
else {
cout << "0" << '\n';
}
}유일하게 DFS로 푼 문제, BFS로 변환도 가능하다. 하지만 아직까지 왜 이게 BFS 문제인지 이해는 할 수 없다. 아마 BF에 특정케이스로 나뉘어지다보니 가능했던거 같긴 한데...
5. BFS 조건
BFS에서 중요한 것은 정점의 정의이다. 행렬로 되어 있는 곳에서는 칸이 정점. DSLR 에서는 A,B 수가 정점, 연구소는 그냥 칸이 정점, 뱀과 사다리도 칸이 정점
보통 조건이 추가된 경우는 입력 받는 값을 추가시켜서 실행한다.
ex> int d[x][y][k] : x,y는 위치, k는 벽을 부순 횟수
2206 벽 부수고 이동하기
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans,i, j, n, m;
int map[1001][1001];
int d[1001][1001][2];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
scanf("%d %d", &n, &m);
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) {
scanf("%1d", &map[i][j]);
}
}
queue<tuple<int, int, int>> q;
q.push(make_tuple(0, 0, 0));
d[0][0][0] = 1;
while (!q.empty()) {
int x, y, k;
tie(x, y, k) = q.front(); q.pop();
for (i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
//그냥 도로일때
if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
if (map[nx][ny]==0 and d[nx][ny][k]==0) {
d[nx][ny][k] = d[x][y][k] + 1;
q.push(make_tuple(nx, ny, k));
}
//벽 있을 때 : 벽 느껴져?
if (map[nx][ny] == 1 and k == 0 and d[nx][ny][k + 1] == 0) {
d[nx][ny][k+1] = d[x][y][k] + 1;
q.push(make_tuple(nx, ny, k + 1));
}
}
}
if (d[n - 1][m - 1][0] != 0 and d[n - 1][m - 1][1] != 0) {
cout << min(d[n - 1][m - 1][0], d[n - 1][m - 1][1]) << '\n';;
}
else if (d[n - 1][m - 1][0] != 0) {
cout << d[n - 1][m - 1][0] << '\n';;
}
else if (d[n - 1][m - 1][1] != 0) {
cout << d[n - 1][m - 1][1] << '\n';;
}
else {
cout << "-1";
}
}16946 벽 부수고 이동하기 4
벽 하나 때려부수고 거기에서 이동할 수 있는 칸의 갯수 구하고
또 다른 벽 하나 때려부수고 거기에서 이동할 수 있는 칸의 갯수 구하는 방식으로 문제를 풀 수 있다.
O(NM x NM) 제한이 (1000x1000)^2 이기 때문에 문제를 풀 수 없다.
그래서 한번 부수고 탐색한것은 미리 숫자를 적어놓자
그리고 부수는 벽을 기준으로 이동할 수 있는 칸의 그룹정보에 저장된 갯수를 결과로 출력하면 된다.
하지만 이 경우와 같이 갈 수 있는 경로 3군데에 같은 그룹만 있을 수 있기때문에 중복을 제거해 주는 과정이 필요하다.
O(NM) + O(NM) = O(NM)
같은 그룹을 여러번 새어보지 않기 위해서 cpp는 set을 사용했다.
14442 벽 부수고 이동하기 2
벽 부수고 이동하기 1에서 벽 부수는 횟수가 증가한 문제이다.
16933 벽 부수고 이동하기 3
이동할 때마다 낮과 밤이 바뀐다. 그리고 낮에만 부술 수 있다. 그래서 낮과 밤의 정보도 함께 저장해서 4차원 배열을 저장해야 한다.
가만히 있는것도 가능하기 때문에 가만히 있는 경우도 처리해 주어야 한다.
16954 움직이는 미로 탈출
신촌거지출신개발자(시리즈 부분에 목차가 나옵니다.)