[알고리즘] 백준 2589 보물섬 -BFS, 브루트포스- 자바 코틀린

 

 

www.acmicpc.net/problem/2589

2589번: 보물섬

 

 

백준 2589 보물섬 문제를 풀어봤습니다. ㅎㅎ

백준 브루트포스 유형에서 한 문제를 골라풀었는데 BFS 기본 문제였습니다.

땅끼리 거리가 가장 큰 곳이 보물이 숨어있는 땅이므로 땅인 곳을 모두 BFS 탐색돌려서 가장 먼 경로를 출력하면됩니다.

 

코틀린의 coerceAtLeast() 라는 함수를 알 수 있던 문제였습니다.

자바에서는 최대값 = Math.Max( 최댓값, 숫자2 )  이렇게 최댓값을 갱신하지만

코틀린에서는 Int 의 확장함수인 coreceAtLeast()를 사용하여 최댓값.corceAtLeast(숫자2) 로 가능해집니다.

/**
 * Ensures that this value is not less than the specified [minimumValue].
 * 
 * @return this value if it's greater than or equal to the [minimumValue] or the [minimumValue] otherwise.
 * 
 * @sample samples.comparisons.ComparableOps.coerceAtLeast
 */
public fun Int.coerceAtLeast(minimumValue: Int): Int {
    return if (this < minimumValue) minimumValue else this
}

 

 

 

풀이는 다음과 같습니다.

 

[Java]

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Main {
    private static int R; // 행
    private static int C; // 열
    private static int[] dr = new int[]{-1, 0, 1, 0};
    private static int[] dc = new int[]{0, -1, 0, 1};
    private static int[][] map; // 맵
    private static boolean[][] isVisited; // 방문여부
    private static int answer = -1;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        R = sc.nextInt();
        C = sc.nextInt();
        map = new int[R][C];
        for (int i = 0; i < R; i++) {
            String str = sc.next();
            for (int j = 0; j < str.length(); j++) {
                map[i][j] = str.charAt(j);
            }
        }
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                isVisited = new boolean[R][C];
                if (map[i][j] == 'L') {
                    bfs(i, j);
                }
            }
        }
        System.out.println(answer);
    }

    private static void bfs(int r, int c) {
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(r, c, 0));
        isVisited[r][c] = true;
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            for (int i = 0; i < 4; i++) {
                int r2 = point.r + dr[i];
                int c2 = point.c + dc[i];
                if (0 <= r2 && r2 < R && 0 <= c2 && c2 < C && map[r2][c2] == 'L' && !isVisited[r2][c2]) {
                    isVisited[r2][c2] = true;
                    queue.offer(new Point(r2, c2, point.cnt + 1));
                    answer = Math.max(answer, point.cnt + 1);
                }
            }
        }
    }

    private static class Point {
        int r;
        int c;
        int cnt; // 걸린시간

        public Point(int r, int c, int cnt) {
            this.r = r;
            this.c = c;
            this.cnt = cnt;
        }
    }
}

 

 

 

[Kotlin]

import java.util.*

private var R // 행
        = 0
private var C // 열
        = 0
private val dr = intArrayOf(-1, 0, 1, 0)
private val dc = intArrayOf(0, -1, 0, 1)
private lateinit var map // 맵
        : Array<CharArray>
private lateinit var isVisited // 방문여부
        : Array<BooleanArray>
private var answer = -1

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    R = sc.nextInt()
    C = sc.nextInt()
    map = Array(R) { CharArray(C) }
    for (i in 0 until R) {
        val str = sc.next()
        for (j in str.indices) {
            map[i][j] = str[j]
        }
    }
    for (i in 0 until R) {
        for (j in 0 until C) {
            isVisited = Array(R) { BooleanArray(C) }
            if (map[i][j] == 'L') {
                bfs(i, j)
            }
        }
    }
    println(answer)
}

private fun bfs(r: Int, c: Int) {
    val queue: Queue<Point> = LinkedList()
    queue.offer(Point(r, c, 0))
    isVisited[r][c] = true
    while (!queue.isEmpty()) {
        val point = queue.poll()
        for (i in 0..3) {
            val r2 = point.r + dr[i]
            val c2 = point.c + dc[i]
            if (r2 in 0 until R && 0 <= c2 && c2 < C && map[r2][c2] == 'L' && !isVisited[r2][c2]) {
                isVisited[r2][c2] = true
                queue.offer(Point(r2, c2, point.cnt + 1))
                answer = answer.coerceAtLeast(point.cnt + 1)
            }
        }
    }
}

data class Point(var r: Int, var c: Int, var cnt: Int)