2589 보물섬

BOJ::2589 보물섬

https://www.acmicpc.net/problem/2589

육지중 가장 먼거리의 최단경로를 찾으면 된다.

특정 포인트만 찾아내 bfs 해보려 했으나, 굳이 그럴 필요 없을거 같아 모든 육지에 대해 bfs 돌려서 최대값을 찾았다. (어차피 bfs로 탐색하면 최단경로를 찾기 때문)

<JAVA>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    static int n,m,x,y,ax,ay;
    static int map[][]=new int[50][50];
    static int max=0;
    static int dx[]={1,-1,0,0};
    static int dy[]={0,0,1,-1};
    static int tmp[][];
    
    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        ArrayList<Node> points = new ArrayList();
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        for(int i = 0; i < n ; i++){
            String s=br.readLine();
            for(int j = 0 ; j < m ; j++){
                map[i][j]=s.charAt(j);
            }
        }
        
        for(int i = 0 ; i < n ; i ++){
            for(int j = 0 ; j < m ; j++){
                if(map[i][j]=='L'){
                    tmp=new int[n][m];
                    bfs(i,j);
                }
            }
        }
 
        System.out.println(max);
    }
    public static void bfs(int a, int b){
        Queue<Node> q = new LinkedList();
        q.add(new Node(a,b));
        while(!q.isEmpty()){
            x = q.peek().x;
            y = q.poll().y;
            for(int i = 0 ; i < 4 ; i++){
                ax = x+dx[i];
                ay = y+dy[i];
                if(ax>=0&&ay>=0&&ax<n&&ay<m){
                    if(map[ax][ay]=='L'){
                        if(tmp[ax][ay]==0||tmp[ax][ay]>tmp[x][y]+1){
                            tmp[ax][ay]=tmp[x][y]+1;
                            if(tmp[ax][ay]>max){
                                max = tmp[ax][ay];
                            }
                            q.add(new Node(ax,ay));
                        }
                    }
                }
            }
        }
    }
}
class Node{
    int x;
    int y;
    Node(int _x, int _y){
        x=_x;
        y=_y;
    }
}

<C++>

#include <iostream>
#include <queue>
#include <string>
using namespace std;
 
int n, m, x, y, ax, ay,res;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int map[50][50];
int tmp[50][50];
 
struct Node
{
    int x;
    int y;
    Node(int _x,int _y) {
        x = _x;
        y = _y;
    }
};
 
void bfs(int a, int b) {
    queue<Node> q;
    q.push(Node(a, b));
    while (!q.empty()) {
        x = q.front().x;
        y = q.front().y;
        q.pop();
        for (int i = 0; i < 4; i++) {
            ax = x + dx[i];
            ay = y + dy[i];
            if (x >= 0 && y >= 0 && ax < n&&ay < m) {
                if (map[ax][ay] == 'L') {
                    if (tmp[ax][ay] == 0 || tmp[ax][ay] > tmp[x][y] + 1) {
                        tmp[ax][ay] = tmp[x][y] + 1;
                        if (res < tmp[ax][ay]) {
                            res = tmp[ax][ay];
                        }
                        q.push(Node(ax,ay));
                    }
                }
            }
        }
    }
}
 
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            map[i][j] = s.at(j);
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 'L') {
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < m; j++) {
                        tmp[i][j] = 0;
                    }
                }
                bfs(i, j);
            }
        }
    }
    cout << res << endl;
}