[백준][Java] 2288 - 격자의 분리자

1. 문제 정보

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

난이도 : G5

유형 : BFS, DFS, DP

시간 : O(S)

---

2. 문제 풀이

최단 경로를 찾기 위해 위아래로 연결되어 있는 S 집합의 좌우 폭을 넓혀야 한다.

넓히는 이유는 S로 이루어진 길에서 탐색의 경로의 경우의 수를 늘려 최소 거리를 찾기 위함이다.

 

문제 조건을 보면 B는 S로 변경할 수 있다, 단 왼쪽에 S가 있는 B만 변경할 수 있다.

즉 S와 B가 붙어 있는 경우에만 B를 S로 변경할 수 있다

 

입력된 문자열을 통해 테이블을 초기화할 때

각 줄마다 처음 등장하는 B를  S로 바꾼다

 

결과적으로 기존의 테이블에서 변경된 테이블의  S의 모양은 오른쪽으로 1칸씩 확장된 모양이다.

(단, 문제의 제약사항에 따라 테이블의 꼭짓점에는 S가 존재할 수 없으므로, 꼭짓점은 예외처리 해줘야 한다.)

 

문제의 조건에 따라 탐색의 방향은 좌, 우, 아래 방향으로만 탐색할 수 있다.

맨 윗줄에서 모든 S를 큐에 넣은 후 탐색을 진행하며, 제일 아랫줄에 도착하면 탐색을 종료하면 된다.

 

이해가 부족한 부분은 아래 코드를 참고하자.

 

---

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static final StringBuilder sb = new StringBuilder();
    public static StringTokenizer st;

    public static final int[][] dir = {{0, -1}, {1, 0}, {0, 1}};
    private int N;
    private int M;
    private char[][] board;
    private Queue<int[]> que;
    private boolean[][] isVisited;
    private int res;

    private void execBFS() {

        while (!que.isEmpty()) {
            int[] cur = que.poll();
            if (cur[0] == N - 1) {
                res = cur[2];
                return;
            }

            for (int i = 0; i < dir.length; i++) {
                int nX = cur[0] + dir[i][0];
                int nY = cur[1] + dir[i][1];

                if (nX < 0 || nX >= N || nY < 0 || nY >= M) {
                    continue;
                }
                if (board[nX][nY] != 'S') {
                    continue;
                }
                if (isVisited[nX][nY]) {
                    continue;
                }

                que.add(new int[]{nX, nY, cur[2] + 1});
                isVisited[nX][nY] = true;
            }
        }
    }

    private void solution() throws IOException {

        while (true) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            if (N == 0 && M == 0) {
                break;
            }

            board = new char[N][M];
            for (int i = 0; i < N; i++) {
                String input = br.readLine();
                for (int j = 0; j < M; j++) {
                    board[i][j] = input.charAt(j);
                }
            }

            for (int i = 0; i < N; i++) {
                for (int j = M - 1; j >= 0; j--) {
                    if (board[i][j] == 'S') {
                        if ((j == 0 || j == N - 1)) {
                            if (j < M - 2) {
                                board[i][j + 1] = 'S';
                                break;
                            }
                        } else {
                            if (j < M - 1) {
                                board[i][j + 1] = 'S';
                                break;
                            }
                        }
                    }
                }
            }

            que = new ArrayDeque<>();
            isVisited = new boolean[N][M];
            for (int i = 1; i < M - 1; i++) {
                if (board[0][i] == 'S') {
                    que.add(new int[]{0, i, 1});
                    isVisited[0][i] = true;
                }
            }

            execBFS();

            sb.append(res).append("\n");
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws IOException {

        Main main = new Main();
        main.solution();
    }
}