기본적인 BFS의 구현은 노드와 방문 리스트를 이용한다.
BFS의 특성상 큐에 쌓이는 순서는 반드시 거리순이다.
연습 문제
1926: 그림
더보기
#include <iostream>
#include <queue>
using namespace std;
int canvas[501][501];
int visited[501][501];
int width, height;
pair<bool, int> bfs(int& _x, int& _y)
{
if (visited[_y][_x] || !canvas[_y][_x])
{
return make_pair(false, 0);
}
// 좌 상 우 하
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };
queue<pair<int, int>> q;
int pic_size = 0;
visited[_y][_x] = 1;
q.push({ _x, _y });
while (!q.empty())
{
pair<int, int> cur = q.front();
q.pop();
pic_size++;
for (int i = 0; i < 4; ++i)
{
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
if (nx < 0 || nx >= width || ny < 0 || ny >= height || !canvas[ny][nx])
{
continue;
}
if (!visited[ny][nx])
{
visited[ny][nx] = 1;
q.push({ nx, ny });
}
}
}
return make_pair(true, pic_size);
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int pic = 0, pic_size = 0;
cin >> height >> width;
for (int y = 0; y < height; ++y)
{
for (int x = 0; x < width; ++x)
{
int p;
cin >> p;
canvas[y][x] = p;
}
}
for (int y = 0; y < height; ++y)
{
for (int x = 0; x < width; ++x)
{
pair<int, int> t = bfs(x, y);
if (t.first)
{
pic++;
pic_size = pic_size > t.second ? pic_size : t.second;
}
}
}
cout << pic << '\n' << pic_size;
return 0;
}
가장 기초적인 BFS
2178: 미로 탐색
더보기
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int maze[101][101];
int dist[101][101];
int width, height;
int bfs(int _x, int _y)
{
// 좌 상 우 하
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };
queue<pair<int, int>> q;
dist[_y][_x] = 1;
q.push({ _x, _y });
while (!q.empty())
{
pair<int, int> cur = q.front();
q.pop();
for (int i = 0; i < 4; ++i)
{
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
if (nx < 0 || nx >= width || ny < 0 || ny >= height || !maze[ny][nx])
{
continue;
}
if (dist[ny][nx] == -1)
{
dist[ny][nx] = dist[cur.second][cur.first] + 1;
q.push({ nx, ny });
}
}
}
return dist[height-1][width-1];
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int answer;
cin >> height >> width;
for (int y = 0; y < height; ++y)
{
string s;
cin >> s;
for (int x = 0; x < width; ++x)
{
maze[y][x] = s[x] - '0';
dist[y][x] = -1;
}
}
answer = bfs(0, 0);
cout << answer;
return 0;
}
간선의 가중치가 모두 1인 그래프의 최단거리는 BFS로 간단히 구현할 수 있다.
7576: 토마토
더보기
#include <iostream>
#include <queue>
using namespace std;
int field[1001][1001];
int dist[1001][1001];
int main()
{
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int width, height, answer = 0;
// 좌 상 우 하
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };
queue<pair<int, int>> q;
cin >> width >> height;
for (int y = 0; y < height; ++y)
{
for (int x = 0; x < width; ++x)
{
cin >> field[y][x];
dist[y][x] = 0;
if (field[y][x] == 1)
{
q.push({ x, y });
}
else if (field[y][x] == 0)
{
dist[y][x] = -1;
}
}
}
while (!q.empty())
{
pair<int, int> cur = q.front();
q.pop();
for (int i = 0; i < 4; ++i)
{
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
if (nx < 0 || nx >= width || ny < 0 || ny >= height || dist[ny][nx] >= 0 || field[ny][nx])
{
continue;
}
dist[ny][nx] = dist[cur.second][cur.first] + 1;
q.push({ nx, ny });
}
}
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
if (dist[y][x] == -1)
{
cout << "-1";
return 0;
}
answer = answer > dist[y][x] ? answer : dist[y][x];
}
}
cout << answer;
return 0;
}
시작점이 여러개인 BFS. 모든 시작점을 큐에 넣고 똑같이 BFS를 돌면 된다.
bfs가 끝난 후 최장거리 및 토마토의 고립여부 확인을 위해 완전 탐색을 실시한다.
7569: 토마토
더보기
#include <iostream>
#include <queue>
#include <tuple>
using namespace std;
int field[101][101][101];
int dist[101][101][101];
int main()
{
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int width, height, depth, answer = 0;
// 좌 상 우 하 앞 뒤
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 };
queue<tuple<int, int, int>> q;
cin >> width >> height >> depth;
for (int z = 0; z < depth; ++z)
{
for (int y = 0; y < height; ++y)
{
for (int x = 0; x < width; ++x)
{
cin >> field[x][y][z];
dist[x][y][z] = 0;
if (field[x][y][z] == 1)
{
q.push({x, y, z});
}
else if (field[x][y][z] == 0)
{
dist[x][y][z] = -1;
}
}
}
}
while (!q.empty())
{
tuple<int, int, int> cur = q.front();
q.pop();
for (int i = 0; i < 6; ++i)
{
int nx = get<0>(cur) + dx[i];
int ny = get<1>(cur) + dy[i];
int nz = get<2>(cur) + dz[i];
if (nx < 0 || nx >= width || ny < 0 || ny >= height || nz < 0 || nz >= depth || dist[nx][ny][nz] >= 0 || field[nx][ny][nz])
{
continue;
}
dist[nx][ny][nz] = dist[get<0>(cur)][get<1>(cur)][get<2>(cur)] + 1;
q.push({ nx, ny, nz });
}
}
for (int z = 0; z < depth; z++)
{
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; ++x)
{
if (dist[x][y][z] == -1)
{
cout << "-1";
return 0;
}
answer = answer > dist[x][y][z] ? answer : dist[x][y][z];
}
}
}
cout << answer;
return 0;
}
3차원 확장판. x, y, z를 좀더 직관적으로 사용 및 볼수있게 수정함
4179: 불!
더보기
#include <iostream>
#include <string>
#include <queue>
using namespace std;
char field[1001][1001];
int dist_fire[1001][1001];
int dist_jh[1001][1001];
int main()
{
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int width, height;
// 좌 상 우 하
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };
queue<pair<int, int>> q_fire;
queue<pair<int, int>> q_jh;
cin >> height >> width;
for (int y = 0; y < height; ++y)
{
string s;
cin >> s;
for (int x = 0; x < width; ++x)
{
field[y][x] = s[x];
dist_fire[y][x] = -1;
dist_jh[y][x] = -1;
if (field[y][x] == 'F')
{
q_fire.push({ x,y });
dist_fire[y][x] = 0;
}
else if (field[y][x] == 'J')
{
q_jh.push({ x,y });
dist_jh[y][x] = 0;
}
}
}
while (!q_fire.empty())
{
pair<int, int> cur = q_fire.front();
q_fire.pop();
for (int i = 0; i < 4; ++i)
{
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
if (nx < 0 || nx >= width || ny < 0 || ny >= height)
{
continue;
}
if (field[ny][nx] == '#' || dist_fire[ny][nx] >= 0)
{
continue;
}
dist_fire[ny][nx] = dist_fire[cur.second][cur.first] + 1;
q_fire.push({ nx, ny });
}
}
while (!q_jh.empty())
{
pair<int, int> cur = q_jh.front();
q_jh.pop();
for (int i = 0; i < 4; ++i)
{
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
// 이번엔 범위를 벗어나면 탈출 성공.
if (nx < 0 || nx >= width || ny < 0 || ny >= height)
{
cout << dist_jh[cur.second][cur.first] + 1;
return 0;
}
if (field[ny][nx] == '#' || dist_jh[ny][nx] >= 0)
{
continue;
}
if (dist_fire[ny][nx] != -1 && dist_fire[ny][nx] <= dist_jh[cur.second][cur.first] + 1)
{
continue;
}
dist_jh[ny][nx] = dist_jh[cur.second][cur.first] + 1;
q_jh.push({ nx, ny });
}
}
cout << "IMPOSSIBLE";
return 0;
}
시작점이 두종류인 BFS. 지훈이와 불에 대한 BFS를 각각 수행함으로써 해결이 가능하다.
우선 불에대한 BFS를 수행해서 각 칸에 불이 전파되는 시간을 다 구해둔다.
이후 지훈이에 대한 BFS 수행시 각 칸의 값보다 작은 경우만 이동할 수 있다.
보통 이미 방문을 했거나 특정 값인 경우 continue로 건너뛰었는데 이 문제는 불이 붙은 시간을 확인해서 필요에 따라 continue를 하면 된다.
방문 테이블을 따로 쓴다.
두 종류의 BFS에서 BFS를 수행할 때 어느 한쪽이 독립적이지 않고 서로에게 영향을 준다면 위와 같은 방법으로는 풀 수 없고 백트래킹으로 해결해야한다.
1697: 숨바꼭질
더보기
#include <iostream>
#include <queue>
using namespace std;
int dist[100001];
int main()
{
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
queue<int> q;
int n, k;
cin >> n >> k;
dist[n] = 0;
q.push(n);
while (!q.empty())
{
int pos = q.front();
q.pop();
if (pos == k)
{
cout << dist[pos];
return 0;
}
for (auto nxt : { pos - 1, pos + 1, pos * 2 })
{
if (nxt < 0 || nxt > 100000)
{
continue;
}
if (dist[nxt])
{
continue;
}
dist[nxt] = dist[pos] + 1;
q.push(nxt);
}
}
return 0;
}
수빈이가 갈 수있는 좌표인 x-1, x+1, x*2를 큐에 넣고 돌리면 된다.
범위가 넘는건 당연히 continue 처리를 하면 되고 방문여부도 확인해주면 된다.
기본 문제
1012: 유기농 배추
더보기
#include <iostream>
#include <queue>
using namespace std;
int visited[51][51];
int cabbage_field[51][51];
int width, height;
const int dx[4] = { -1, 0, 1, 0 };
const int dy[4] = { 0, -1, 0, 1 };
int bfs(int& x, int& y)
{
if (!cabbage_field[x][y] || visited[x][y])
{
return 0;
}
queue<pair<int, int>> q;
q.push({ x, y });
visited[x][y] = 1;
while (!q.empty())
{
pair<int, int> current_pos = q.front();
q.pop();
for (int i = 0; i < 4; ++i)
{
int nx = current_pos.first + dx[i];
int ny = current_pos.second + dy[i];
if (nx < 0 || nx >= width || ny < 0 || ny >= height)
{
continue;
}
if (!visited[nx][ny] && cabbage_field[nx][ny] == 1)
{
visited[nx][ny] = 1;
q.push({ nx, ny });
}
}
}
return 1;
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while (t--)
{
int k, answer = 0;
cin >> width >> height >> k;
for (int x = 0; x < width; ++x)
{
fill(cabbage_field[x], cabbage_field[x] + height, 0);
fill(visited[x], visited[x] + height, 0);
}
while (k--)
{
int x, y;
cin >> x >> y;
cabbage_field[x][y] = 1;
}
for (int x = 0; x < width; x++)
{
for (int y = 0; y < height; ++y)
{
answer += bfs(x, y);
}
}
cout << answer << '\n';
}
return 0;
}
기본적인 BFS
10026: 적록색약
더보기
#include <iostream>
#include <string>
#include <queue>
using namespace std;
string picture[101];
int ordinary_visited[101][101];
int special_visited[101][101];
const int dx[4] = { -1, 0, 1, 0 };
const int dy[4] = { 0, -1, 0, 1 };
int bfs(int (*visited)[101], int len, bool special = false)
{
int answer = 0;
for (int x = 0; x < len; ++x)
{
for (int y = 0; y < len; ++y)
{
if (visited[x][y]) {
continue;
}
queue<pair<int, int>> q;
visited[x][y] = 1;
q.push({ x, y });
answer++;
while (!q.empty())
{
pair<int, int> current_pos = q.front();
q.pop();
for (int i = 0; i < 4; ++i)
{
int nx = current_pos.first + dx[i];
int ny = current_pos.second + dy[i];
if (nx < 0 || nx >= len || ny < 0 || ny >= len)
{
continue;
}
// special
if (special)
{
// 153 = G(71) + R(82)
if (!visited[nx][ny] && ((picture[ny][nx] == picture[current_pos.second][current_pos.first])
|| (picture[ny][nx] + picture[current_pos.second][current_pos.first] == 153)))
{
visited[nx][ny] = 1;
q.push({ nx, ny });
}
}
// ordinary
else {
if (!visited[nx][ny] && (picture[ny][nx] == picture[current_pos.second][current_pos.first]))
{
visited[nx][ny] = 1;
q.push({ nx, ny });
}
}
}
}
}
}
return answer;
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> picture[i];
}
cout << bfs(ordinary_visited, n) << " ";
cout << bfs(special_visited, n, true);
return 0;
}
bfs 함수 재활용좀 해보려고 디폴트 매개변수를 썼더니 중간에 가독성이 확 떨어지는 한줄이 생겼다
보통의 경우는 보통의 bfs인데 적록색약인 경우 R=G로 봐야하기 때문에 둘의 아스키코드 값을 더해서 판별함
7562: 나이트의 이동
더보기
#include <iostream>
#include <queue>
using namespace std;
int table[301][301];
int bfs(pair<int, int>& start, pair<int, int>& dest, int& len)
{
// 좌2 상2 우2 하2 x, y
pair<int, int> move[8] = { {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}, {-1, 2} };
queue<pair<int, int>> q;
q.push(start);
table[start.first][start.second] = 0;
while (!q.empty())
{
pair<int, int> cur = q.front();
q.pop();
if (cur == dest)
{
return table[cur.first][cur.second];
}
for (int i = 0; i < 8; ++i)
{
int dx = cur.first + move[i].first;
int dy = cur.second + move[i].second;
if (dx < 0 || dx >= len || dy < 0 || dy >= len)
{
continue;
}
if (table[dx][dy] >= 0)
{
continue;
}
q.push({ dx, dy });
table[dx][dy] = table[cur.first][cur.second] + 1;
}
}
return 0;
}
void init_table(int len)
{
for (int i = 0; i < len; ++i)
{
fill(table[i], table[i] + len, -1);
}
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int tc;
cin >> tc;
while (tc--)
{
int l;
pair<int, int> current, target;
cin >> l;
cin >> current.first >> current.second;
cin >> target.first >> target.second;
init_table(l);
cout << bfs(current, target, l) << '\n';
}
return 0;
}
기본적인 BFS 문제
5427: 불
더보기
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int fire_dist[1001][1001];
int sk_dist[1001][1001];
string s[1001];
int main()
{
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int tc;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};
cin >> tc;
while (tc--)
{
int width, height;
queue<pair<int, int>> fire_q;
queue<pair<int, int>> sk_q;
bool isEscape = false;
cin >> width >> height;
for (int y = 0; y < height; ++y)
{
cin >> s[y];
for (int x = 0; x < width; ++x)
{
fire_dist[x][y] = 1000001;
sk_dist[x][y] = -1;
if (s[y][x] == '*')
{
fire_q.push({ x, y });
fire_dist[x][y] = 0;
}
else if (s[y][x] == '@')
{
sk_q.push({ x, y });
sk_dist[x][y] = 0;
}
}
}
while (!fire_q.empty())
{
pair<int, int> cur = fire_q.front();
fire_q.pop();
for (int i = 0; i < 4; ++i)
{
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
if (nx < 0 || nx >= width || ny < 0 || ny >= height)
{
continue;
}
if (s[ny][nx] == '#' || fire_dist[nx][ny] <= fire_dist[cur.first][cur.second] + 1)
{
continue;
}
fire_q.push({ nx, ny });
fire_dist[nx][ny] = fire_dist[cur.first][cur.second] + 1;
}
}
while (!sk_q.empty() && !isEscape)
{
pair<int, int> cur = sk_q.front();
sk_q.pop();
for (int i = 0; i < 4; ++i)
{
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
if (nx < 0 || nx >= width || ny < 0 || ny >= height)
{
cout << sk_dist[cur.first][cur.second] + 1 << '\n';
isEscape = true;
break;
}
if (s[ny][nx] == '#' || sk_dist[cur.first][cur.second] + 1 >= fire_dist[nx][ny] || sk_dist[nx][ny] >= 0)
{
continue;
}
sk_q.push({ nx, ny });
sk_dist[nx][ny] = sk_dist[cur.first][cur.second] + 1;
}
}
if (!isEscape)
{
cout << "IMPOSSIBLE" << '\n';
}
}
return 0;
}
불! 이랑 거의 동일한 문제임에도 불구하고 1시간 11분이 걸렸다.
구현의 95%정도는 30분안에 해결했는데 사소한 부분을 놓치니까 40분이 넘었다.
1000*1000 사이즈라서 최대값을 100만으로 줬어야하는데 1001로 줘서 25%에서 틀렸고 string 자체를 x,y 좌표방식으로 쓰려면 y,x 순서를 바꿔서 써야함에도 자꾸 틀리게 써서 오류도 많이 났다.
2583: 영역 구하기
더보기
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int paper[101][101];
int visited[101][101];
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};
int main()
{
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int width, height, n;
int p_num = 0;
queue<pair<int, int>> q;
vector<int> answer;
cin >> height >> width >> n;
while (n--)
{
int lx, ly, rx, ry;
cin >> lx >> ly >> rx >> ry;
for (int x = lx; x < rx; ++x)
{
for (int y = ly; y < ry; ++y)
{
paper[x][y] = 1;
}
}
}
for (int x = 0; x < width; ++x)
{
for (int y = 0; y < height; ++y)
{
if (paper[x][y] || visited[x][y])
{
continue;
}
queue<pair<int, int>> q;
int p_size = 0;
q.push({ x, y });
visited[x][y] = 1;
p_num++;
while (!q.empty())
{
pair<int, int> cur = q.front();
q.pop();
p_size++;
for (int i = 0; i < 4; ++i)
{
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
if (nx < 0 || nx >= width || ny < 0 || ny >= height)
{
continue;
}
if (paper[nx][ny] || visited[nx][ny])
{
continue;
}
q.push({ nx,ny });
visited[nx][ny] = 1;
}
}
answer.push_back(p_size);
}
}
sort(answer.begin(), answer.end());
cout << p_num << '\n';
for (auto& ans : answer)
{
cout << ans << " ";
}
return 0;
}
2667: 단지번호붙이기
더보기
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int visited[26][26];
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};
int main()
{
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n, h_num = 0;
string house[26];
queue<pair<int, int>> q;
vector<int> answer;
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> house[i];
}
for (int x = 0; x < n; ++x)
{
for (int y = 0; y < n; ++y)
{
if (!(house[x][y]-'0') || visited[x][y])
{
continue;
}
queue<pair<int, int>> q;
int h_size = 0;
q.push({ x, y });
visited[x][y] = 1;
h_num++;
while (!q.empty())
{
pair<int, int> cur = q.front();
q.pop();
h_size++;
for (int i = 0; i < 4; ++i)
{
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= n)
{
continue;
}
if (!(house[nx][ny]-'0') || visited[nx][ny])
{
continue;
}
q.push({ nx,ny });
visited[nx][ny] = 1;
}
}
answer.push_back(h_size);
}
}
sort(answer.begin(), answer.end());
cout << h_num << '\n';
for (auto& ans : answer)
{
cout << ans << '\n';
}
return 0;
}
기본적인 BFS
5014: 스타트링크
더보기
#include <iostream>
#include <queue>
using namespace std;
int visited[1000001];
int main()
{
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// f:층수 s:현재위치 g:목적지 u:위로 u층 d:아래로 d층
int f, s, g, u, d;
queue<int> q;
cin >> f >> s >> g >> u >> d;
fill(visited, visited + f + 1, -1);
q.push(s);
visited[s] = 0;
while (!q.empty())
{
int cur = q.front();
q.pop();
if (cur == g)
{
cout << visited[cur];
return 0;
}
if (cur - d >= 1)
{
if (visited[cur - d] == -1)
{
q.push(cur - d);
visited[cur - d] = visited[cur] + 1;
}
}
if (cur + u <= f)
{
if (visited[cur + u] == -1)
{
q.push(cur + u);
visited[cur + u] = visited[cur] + 1;
}
}
}
cout << "use the stairs";
return 0;
}
2468: 안전 영역
더보기
#include <iostream>
#include <queue>
using namespace std;
int area[101][101];
int visited[101][101];
const int dx[4] = { -1, 0, 1, 0 };
const int dy[4] = { 0, -1, 0, 1 };
void init_visited(int len)
{
for (int i = 0; i < len; ++i)
{
fill(visited[i], visited[i] + len + 1, 0);
}
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n, answer = 0;
int hst_h = 0;
queue<pair<int, int>> q;
cin >> n;
for (int x = 0; x < n; ++x)
{
for (int y = 0; y < n; ++y)
{
cin >> area[x][y];
hst_h = hst_h > area[x][y] ? hst_h : area[x][y];
}
}
for (int h = 0; h < hst_h; ++h)
{
int cnt = 0;
init_visited(n);
for (int x = 0; x < n; ++x)
{
for (int y = 0; y < n; ++y)
{
if (area[x][y] <= h || visited[x][y])
{
continue;
}
q.push({ x, y });
visited[x][y] = 1;
cnt++;
while (!q.empty())
{
pair<int, int> cur = q.front();
q.pop();
for (int i = 0; i < 4; ++i)
{
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= n)
{
continue;
}
if (area[nx][ny] <= h || visited[nx][ny])
{
continue;
}
q.push({ nx, ny });
visited[nx][ny] = 1;
}
}
}
}
answer = answer > cnt ? answer : cnt;
}
cout << answer;
return 0;
}
높이에 따라 bfs를 수행할 때 마다 값이 달라지기때문에 각 높이별로 bfs를 모두 수행해 주어 최고값을 산출해야 한다.
처음에 예제보고 n이하는 다 패스처리하고 예제 ac길래 매우 쉽다 생각했는데 반례랑 글좀 찾아보니 예제를 일부러 혼동하기 쉽게 만들어 둔것 같음. 아니면 내가 빡대가리거나
6593: 상범빌딩
더보기
#include <iostream>
#include <string>
#include <queue>
#include <tuple>
using namespace std;
string area[31][31];
int dist[31][31][31];
// 좌 우 상 하 앞 뒤
const int dx[6] = { -1, 0, 1, 0, 0, 0 };
const int dy[6] = { 0, -1, 0, 1, 0, 0 };
const int dz[6] = { 0, 0, 0, 0, -1, 1 };
int main()
{
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
while (true)
{
int width, height, depth;
int answer = 0;
queue<tuple<int, int, int>> q;
// l, c, r
cin >> depth >> height >> width;
if (depth + width + height == 0)
{
return 0;
}
// dist 초기화
for (int x = 0; x < width; ++x)
{
for (int y = 0; y < height; ++y)
{
fill(dist[x][y], dist[x][y] + depth, -1);
}
}
// area 초기화
for (int z = 0; z < depth; ++z)
{
for (int y = 0; y < height; ++y)
{
cin >> area[z][y];
for (int x = 0; x < width; ++x)
{
if (area[z][y][x] == 'S')
{
q.push({ x, y, z });
dist[x][y][z] = 0;
}
}
}
}
while (!q.empty())
{
int curX = get<0>(q.front());
int curY = get<1>(q.front());
int curZ = get<2>(q.front());
q.pop();
if (area[curZ][curY][curX] == 'E')
{
answer = dist[curX][curY][curZ];
}
for (int i = 0; i < 6; ++i)
{
int nx = curX + dx[i];
int ny = curY + dy[i];
int nz = curZ + dz[i];
if (nx < 0 || nx >= width || ny < 0 || ny >= height || nz < 0 || nz >= depth)
{
continue;
}
if (area[nz][ny][nx] == '#' || dist[nx][ny][nz] >= 0)
{
continue;
}
q.push({ nx, ny, nz });
dist[nx][ny][nz] = dist[curX][curY][curZ] + 1;
}
}
if (answer)
{
cout << "Escaped in " << answer << " minute(s)." << '\n';
}
else
{
cout << "Trapped!" << '\n';
}
}
return 0;
}
토마토 3차원이랑 개념은 같음. 다행히 금방 짰음
'알고리즘 > 바킹독의 실전 알고리즘' 카테고리의 다른 글
| [0x0B] 재귀 (0) | 2022.07.30 |
|---|---|
| [0x0A] DFS (0) | 2022.07.30 |
| [0x08] 스택의 활용 (0) | 2022.07.25 |
| [0x07] 덱(Deque) (0) | 2022.07.25 |
| [0x06] 큐 (0) | 2022.07.25 |