2589번: 보물섬
보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서
www.acmicpc.net
칸이 육지인 곳에서 bfs를 돌려서 거리가 가장 긴 시간을 출력하는 문제입니다.
이 문제는 육지인 모든 칸을 시작점으로 잡고 bfs를 돌려주면 되겠습니다.
한 번의 bfs가 끝나면 visit배열을 초기화 해주어야합니다.
[C++]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
typedef struct Point {
int x;
int y;
int cnt;
}Point;
char list[60][60];
bool visit[60][60];
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int N, M, ans;
void bfs(int sx, int sy) {
queue<Point> q;
q.push({ sx,sy,0 });
visit[sx][sy] = true;
while (!q.empty()) {
int x = q.front().x;
int y = q.front().y;
int cnt = q.front().cnt;
q.pop();
ans = max(ans, cnt);
for (int i = 0; i < 4; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (visit[nx][ny] || list[nx][ny] == 'W') continue;
q.push({ nx,ny,cnt + 1 });
visit[nx][ny] = true;
}
}
}
void func() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (list[i][j] == 'W') continue;
bfs(i, j);
memset(visit, false, sizeof(visit));
}
}
cout << ans << '\n';
}
void input() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> list[i][j];
}
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
[Java]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static char list[][] = new char[60][60];
static boolean visit[][] = new boolean[60][60];
static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
static int N, M, ans;
static void bfs(int sx, int sy) {
Deque<int[]> dq = new ArrayDeque<>();
dq.add(new int[] { sx, sy, 0 });
visit[sx][sy] = true;
while (!dq.isEmpty()) {
int x = dq.peek()[0];
int y = dq.peek()[1];
int cnt = dq.poll()[2];
ans = Math.max(ans, cnt);
for (int i = 0; i < 4; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M)
continue;
if (visit[nx][ny] || list[nx][ny] == 'W')
continue;
dq.add(new int[] { nx, ny, cnt + 1 });
visit[nx][ny] = true;
}
}
}
static void func() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (list[i][j] == 'W')
continue;
bfs(i, j);
for (int k = 0; k < N; k++)
Arrays.fill(visit[k], false);
}
}
System.out.println(ans);
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
list[i] = st.nextToken().toCharArray();
}
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 9205 맥주 마시면서 걸어가기 (0) | 2021.03.25 |
|---|---|
| boj 1600 말이 되고픈 원숭이 (0) | 2021.03.24 |
| boj 11559 Puyo Puyo (0) | 2021.02.26 |
| boj 15653 구슬 탈출 4 (0) | 2021.02.22 |
| boj 1525 퍼즐 (0) | 2021.02.19 |