문제출처: https://www.acmicpc.net/problem/2589
풀이
1.육지인 좌표에서 bfs를 돌리고
2. 그 좌표에서 bfs를 돌렸을 때 최단거리를 구함
3. 모든 육지좌표에서 1,2를 수행하며 최단거리 갱신
4. 마지막에 구한 최단거리==정답
핵심: 어떤 육지좌표에서 1,2를 수행하고 다른 육지좌표에서 최단거리를 구할 때 check배열은 0으로 초기화(방문하지않았다고)해야합니다.
그리고 정답을 출력할 때, 최단거리에서 1을 빼준값을 출력해야합니다. 아래 그림을 참조하면됩니다.
당연하지만, bfs가 아래 그림처럼 최단거리로 갱신해주기 때문에 최단거리문제에서 dfs보다 bfs가 훨씬유리합니다.
코드
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
char map[50][50];
int check[50][50];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int n, m;
int cnt;
int max_value = 0;
void bfs(int y, int x);
int main()
{
cin.tie(0);
cin.sync_with_stdio(false);
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> map[i];
//육지일때 그 좌표에서 최단거리구해봄
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (map[i][j] == 'L')
//육지에서시작되는 각 좌표들로부터의 최단거리를
{
bfs(i, j);
max_value = max(max_value, cnt);
cnt = 0;
}
}
}
//육지에서 bfs를돌리면 그 육지의 좌표의 인접한 좌표가2가되므로 하나빼줘야됨
cout << max_value-1 << '\n';
}
void bfs(int y, int x)
{
//핵심! 육지인 모든곳을 탐색하므로 한번 탐색할때마다 갱신
memset(check, 0, sizeof(check));
queue<pair<int, int>>q;
q.push({ y,x });
check[y][x] = 1;
while (!q.empty())
{
y = q.front().first;
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 && ny >= 0 && nx < m && ny < n)
{
//만약 육지이고, 만나지않았떤길이면
if (map[ny][nx] == 'L' && check[ny][nx] == 0)
{
check[ny][nx] = check[y][x] + 1;
cnt = max(cnt, check[ny][nx]);
q.push({ ny,nx });
}
}
}
}
}결과
'문제풀이(BOJ) > DFS,BFS' 카테고리의 다른 글
| [백준 1759] 암호 만들기 (0) | 2020.02.06 |
|---|---|
| [백준] 촌수계산 (0) | 2020.01.20 |
| [백준 14502] 연구소 (BFS) (0) | 2020.01.17 |
| [백준 2667] 단지번호붙이기 (BFS) (0) | 2020.01.17 |
| [백준 11724] 연결 요소의 개수(DFS) (0) | 2020.01.15 |
