[Baekjoon 17198] Bucket Brigade - JAVA

[Silver IV] Bucket Brigade - 17198

문제 링크

성능 요약

메모리: 14048 KB, 시간: 120 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

문제 설명

A fire has broken out on the farm, and the cows are rushing to try and put it out!

The farm is described by a 10×10$10 \times 10$ grid of characters like this:

..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........

The character 'B' represents the barn, which has just caught on fire. The 'L' character represents a lake, and 'R' represents the location of a large rock.

The cows want to form a "bucket brigade" by placing themselves along a path between the lake and the barn so that they can pass buckets of water along the path to help extinguish the fire. A bucket can move between cows if they are immediately adjacent in the north, south, east, or west directions. The same is true for a cow next to the lake --- the cow can only extract a bucket of water from the lake if she is immediately adjacent to the lake. Similarly, a cow can only throw a bucket of water on the barn if she is immediately adjacent to the barn.

Please help determine the minimum number of '.' squares that should be occupied by cows to form a successful bucket brigade.

A cow cannot be placed on the square containing the large rock, and the barn and lake are guaranteed not to be immediately adjacent to each-other.

입력

The input file contains 10 rows each with 10 characters, describing the layout of the farm. There are exactly one barn, one lake, and one rock.

출력

Output a single integer giving the minimum number of cows needed to form a viable bucket brigade.

문제 풀이

소들을 올바른 위치에 배치하여 최소한의 소의 수로 성공적으로 버킷 브리게이드를 구성하는 문제다.
소들은 호수와 헛간 사이에 경로를 형성하며, 이 경로를 통해 물 양동이를 전달하고, 헛간에 물을 뿌릴 수 있어야 한다.

문제의 입력은 10x10 크기의 농장 격자로 주어집니다. 'B'는 헛간, 'L'은 호수, 'R'은 큰 돌을 나타낸다.
목표는 헛간과 호수 사이에 버킷 브리게이드를 형성할 수 있는 최소한의 소의 수를 결정하는 것이다.
다만, 소는 호수와 헛간을 제외한 빈 공간에만 배치될 수 있으며, 큰 돌의 위치에는 배치될 수 없다.

입력을 읽어와서 농장 격자를 생성하고, 헛간, 호수, 큰 돌의 위치를 파악히야 호수에서 헛간으로 가는 경로를 찾는 너비 우선 탐색(BFS)을 이용하여 구하면 된다.

BFS를 통해 호수에서 헛간까지의 경로를 찾으면, 해당 경로의 빈 공간 중에서 최소한의 소의 수를 구하는 방법을 사용했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char map[][] = new char[10][10];
        int barnRow = 0, lRow = 0, rRow = 0;
        int barnCol = 0, lCol = 0, rCol = 0;

        for (int i = 0; i < 10; i++) {
            String rowInput = br.readLine();
            for (int j = 0; j < rowInput.length(); j++) {
                map[i][j] = rowInput.charAt(j);
            }
        }

        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                if (map[i][j] == 'B') {
                    barnRow = i;
                    barnCol = j;
                }
                if (map[i][j] == 'L') {
                    lRow = i;
                    lCol = j;
                }
                if (map[i][j] == 'R') {
                    rRow = i;
                    rCol = j;
                }
            }
        }

        if (barnRow == lRow && lRow == rRow && ((rCol > lCol && rCol < barnCol) || (rCol > barnCol && rCol < lCol))) {
            System.out.println(Math.abs(barnCol - lCol) + 1);
        } else if (barnCol == lCol && lCol == rCol && ((rRow > lRow && rRow < barnRow) || (rRow > barnRow && rRow < lRow))) {
            System.out.println(Math.abs(barnRow - lRow) + 1);
        } else {
            System.out.println((Math.abs(barnRow - lRow) + Math.abs(barnCol - lCol)) - 1);
        }

    }
}

코드 풀이

   char map[][] = new char[10][10];
   int barnRow = 0, lRow = 0, rRow = 0;
   int barnCol = 0, lCol = 0, rCol = 0;

   for (int i = 0; i < 10; i++) {
       String rowInput = br.readLine();
       for (int j = 0; j < rowInput.length(); j++) {
           map[i][j] = rowInput.charAt(j);
       }
   }

• map: 10x10 크기의 2차원 배열을 선언하여 농장 격자 정보를 저장한다.
• barnRow, lRow, rRow, barnCol, lCol, rCol: 각각 헛간, 호수, 큰 돌의 행과 열 위치를 나타낸다.
• for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { if (map[i][j] == 'B') { barnRow = i; barnCol = j; } if (map[i][j] == 'L') { lRow = i; lCol = j; } if (map[i][j] == 'R') { rRow = i; rCol = j; } } }
• 이중 반복문을 사용하여 map 배열을 순회하면서 헛간, 호수, 큰 돌의 위치를 파악한다.
• if (barnRow == lRow && lRow == rRow && ((rCol > lCol && rCol < barnCol) || (rCol > barnCol && rCol < lCol))) { System.out.println(Math.abs(barnCol - lCol) + 1); } else if (barnCol == lCol && lCol == rCol && ((rRow > lRow && rRow < barnRow) || (rRow > barnRow && rRow < lRow))) { System.out.println(Math.abs(barnRow - lRow) + 1); } else { System.out.println((Math.abs(barnRow - lRow) + Math.abs(barnCol - lCol)) - 1); }
• 호수와 헛간 사이의 경로를 계산하고 최소한의 소의 수를 출력하는 부분이다.
• 호수, 헛간, 큰 돌이 모두 한 행에 위치한 경우를 체크하며, 그 사이에 빈 공간이 있는지 검사한다.
  이때, 빈 공간이 있을 경우 호수와 헛간 사이의 거리를 출력한다.
• 열에 대한 경우를 체크한다.
• 위의 두 조건문에 모두 해당하지 않으면 호수와 헛간 사이의 거리를 구한 후, 호수와 헛간을 포함한 거리에서 1을 뺀 값을 출력한다.