boj 2589 보물섬

www.acmicpc.net/problem/2589

2589번: 보물섬

칸이 육지인 곳에서 bfs를 돌려서 거리가 가장 긴 시간을 출력하는 문제입니다.

이 문제는 육지인 모든 칸을 시작점으로 잡고 bfs를 돌려주면 되겠습니다.

한 번의 bfs가 끝나면 visit배열을 초기화 해주어야합니다.

 

 

[C++]

#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;
}

 

 

[Java]

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();
    }
}