๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
๐ŸŽ› Others.../- ์‹ค์ „ ๋ฌธ์ œ ํ’€์ด : PS

[์•Œ๊ณ ๋ฆฌ์ฆ˜ PS] 2589๋ฒˆ ๋ณด๋ฌผ์„ฌ ์ž๋ฐ” ๋ฌธ์ œํ’€์ด

by Wonit 2021. 8. 14.

๋ฌธ์ œ

ํ•ด๋‹น ํฌ์ŠคํŒ…์€ ๋ฐฑ์ค€์˜ 2589๋ฒˆ ๋ณด๋ฌผ์„ฌ ์˜ ์ ‘๊ทผ๊ณผ ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•์„ ์„ค๋ช…ํ•œ ๊ธ€ ์ž…๋‹ˆ๋‹ค.
์ •๋‹ต ์†Œ์Šค ์ฝ”๋“œ๋ฅผ ํ™•์ธํ•˜์‹œ๋ ค๋ฉด solve url ์—์„œ ํ™•์ธ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.

 

2589๋ฒˆ: ๋ณด๋ฌผ์„ฌ

์ฒซ์งธ ์ค„์—๋Š” ๋ณด๋ฌผ ์ง€๋„์˜ ์„ธ๋กœ์˜ ํฌ๊ธฐ์™€ ๊ฐ€๋กœ์˜ ํฌ๊ธฐ๊ฐ€ ๋นˆ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. ์ด์–ด L๊ณผ W๋กœ ํ‘œ์‹œ๋œ ๋ณด๋ฌผ ์ง€๋„๊ฐ€ ์•„๋ž˜์˜ ์˜ˆ์™€ ๊ฐ™์ด ์ฃผ์–ด์ง€๋ฉฐ, ๊ฐ ๋ฌธ์ž ์‚ฌ์ด์—๋Š” ๋นˆ ์นธ์ด ์—†๋‹ค. ๋ณด๋ฌผ ์ง€๋„์˜

www.acmicpc.net

 

์ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด ์–ด๋–ค ๋ฐฉ์‹์œผ๋กœ ์ ‘๊ทผํ•ด์•ผ ํ•˜๋Š”์ง€๋ฅผ ๋จผ์ € ์ƒ๊ฐํ•ด๋ณด์ž.

 

๋ฌธ์ œ ์ ‘๊ทผ

 

์ด๋ฒˆ ๋ฌธ์ œ๋Š” BFS ๋กœ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ์˜€๋‹ค.

 

๊ณจ๋“œ 5๋ผ๊ณ  ํ•˜๋Š”๋ฐ ๋ง‰์ƒ ํ’€๋ฉด ์‹ค๋ฒ„ 1? ์ •๋„ ๋Š๋‚Œ์˜ ๋ฌธ์ œ์˜€๋‹ค.

 

ํ•ด๊ฒฐ๋ฒ•

 

๊ฐ๊ฐ ๋ฐฐ์—ด์„ ๋Œ๋ฉฐ L์ผ ๋•Œ BFS ๋กœ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ๊ธธ์ด๋ฅผ ๋งค๋ฒˆ ๊ฐฑ์‹ ํ•ด์ฃผ๋ฉด ๋œ๋‹ค.

 

์ฃผ์˜ํ•ด์•ผํ•  ์ ์ด ๋ฐฐ์—ด์„ ํ•œ ๋ฒˆ์”ฉ ๋‹ค ๋Œ๋ฉด ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋‚˜์˜ค๊ธฐ ๋•Œ๋ฌธ์— L ์ธ ๊ฒƒ๋งŒ ๋Œ์•„์•ผ ํ•œ๋‹ค.

 

์ •๋‹ต ์ฝ”๋“œ

public class Main {

    private static int l;
    private static int w;
    private static String[][] arr;
    private static int[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] lw = br.readLine().split(" ");

        l = Integer.parseInt(lw[0]);
        w = Integer.parseInt(lw[1]);

        arr = new String[l][w];

        for (int i = 0; i < l; i++) {
            String[] s = br.readLine().split("");
            for (int j = 0; j < w; j++) {
                arr[i][j] = s[j];
            }
        }

        int max = 0;

        for (int i = 0; i < l; i++) {
            for (int j = 0; j < w; j++) {
                if(arr[i][j].equals("L")) {
                    visited = new int[l][w];
                    max = Math.max(max, getTreasure(j, i));   
                }
            }
        }

        bw.write(String.valueOf(max - 1));

        bw.flush();
        bw.close();
    }

    private static int getTreasure(int x, int y) {

        int[] xPos = {1, -1, 0, 0};
        int[] yPos = {0, 0, 1, -1};

        Queue<Pair> queue = new LinkedList<>();

        queue.add(new Pair(x, y));
        visited[y][x] = 1;

        while(!queue.isEmpty()) {
            Pair front = queue.remove();

            for (int i = 0; i < 4; i++) {
                int xx = front.x + xPos[i];
                int yy = front.y + yPos[i];

                if(!(0 <= xx && xx < w && 0 <= yy && yy < l)) continue;
                if(visited[yy][xx] != 0) continue;
                if(arr[yy][xx].equals("W")) continue;

                visited[yy][xx] = visited[front.y][front.x] + 1;
                queue.add(new Pair(xx, yy));
            }
        }

        int max = 0;

        for (int i = 0; i < visited.length; i++) {
            for (int j = 0; j < visited[i].length; j++) {
                max = Math.max(max, visited[i][j]);
            }
        }

        return max;
    }

    private static class Pair {
        int x;
        int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}


์ •๋‹ต ์†Œ์Šค ์ฝ”๋“œ๋ฅผ ํ™•์ธํ•˜์‹œ๋ ค๋ฉด solve url ์—์„œ ํ™•์ธ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.

๋Œ“๊ธ€