[JAVA] 백준 1175 배달

U_Uracil·2023년 3월 26일
0

알고리즘 JAVA

목록 보기
17/19

[백준 1175]https://www.acmicpc.net/problem/1175


문제 조건

어제 선물을 모두 포장한 민식이는 이제 선물을 배달하려고 한다. 민식이가 선물을 배달할 곳은 이 문제를 읽는 사람들이 앉아 있는 교실이다. 교실은 직사각형모양이고, 모두 같은 크기의 정사각형 블록으로 나누어져 있다.

입력으로 교실의 지도가 주어진다. 각각의 정사각형 블록은 다음과 같이 4가지 종류가 있다.

  • S : 지금 민식이가 있는 곳이다. 이곳이 민식이가 배달을 시작하는 곳이고 1개만 있다.
  • C : 민식이가 반드시 선물을 배달해야 하는 곳이다. 이러한 블록은 정확하게 2개 있다.
  • # : 민식이가 갈 수 없는 곳이다.
  • . : 민식이가 자유롭게 지나갈 수 있는 곳이다.

민식이가 한 블록 동서남북으로 이동하는데는 1분이 걸린다. 민식이는 네가지 방향 중 하나로 이동할 수 있으며, 교실을 벗어날 수 없다. 민식이가 선물을 배달해야 하는 곳에 들어갈 때, 민식이는 그 곳에 있는 사람 모두에게 선물을 전달해야 한다. 이 상황은 동시에 일어나며, 추가적인 시간이 소요되지 않는다.

민식이는 어느 누구도 자신을 보지 않았으면 하기 때문에, 멈추지 않고 매 시간마다 방향을 바꿔야 한다. 이 말은 같은 방향으로 두 번 연속으로 이동할 수 없다는 말이다. 민식이가 선물을 모두 배달하는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.


문제 입력

첫째 줄에 교실의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 교실의 지도가 주어진다.


문제 풀기 전 설계

방향만 잘 처리하면 쉬운 BFS 문제일 것 같다.


문제 코드

package Baekjoon.graph.bfsNdfs;

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

public class BOJ_1175 {
    static int N, M;
    static char[][] classRoom;
    static int[] dx = {-1, 1, 0, 0}; // 상하좌우
    static int[] dy = {0, 0, -1, 1}; // 상하좌우

    static class Node {
        int dir, x, y, time, check;
        public Node(int dir, int x, int y, int time, int check) {
            this.dir = dir;
            this.x = x;
            this.y = y;
            this.time = time;
            this.check = check;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        classRoom = new char[N][];
        Node start = null;
        Node[] end = new Node[2];

        for (int i = 0, idx = 0; i < N; i++) {
            classRoom[i] = br.readLine().toCharArray();
            for (int j = 0; j < M; j++) {
                char now = classRoom[i][j];
                if (now == 'S') start = new Node(-1, i, j, 0, 0);
                else if (now == 'C') end[idx++] = new Node(-1, i, j, 0, 0);
            }
        }

        System.out.println(bfs(start, end));
    }

    private static int bfs(Node start, Node[] end) {
        /** visited[방향][x][y][c1, c2 방문 여부]
         * 0 = 방문 X
         * 1 = c1 방문
         * 2 = c2 방문
         * 3 = 둘 다 방문 = 최소값 리턴
         */
        boolean[][][][] visited = new boolean[4][N][M][3];
        for (int i = 0; i < 4; i++) visited[i][start.x][start.y][0] = true;
        Queue<Node> q = new LinkedList<>();
        q.offer(start);

        while (!q.isEmpty()) {
            Node now = q.poll();

            if (now.x == end[0].x && now.y == end[0].y && now.check != 1) now.check += 1;
            else if (now.x == end[1].x && now.y == end[1].y && now.check != 2) now.check += 2;
            if (now.check == 3) return now.time;

            for (int i = 0; i < 4; i++) {
                if (now.dir == i) continue;
                int nextX = now.x + dx[i];
                int nextY = now.y + dy[i];

                if (!isInRange(nextX, nextY) || classRoom[nextX][nextY] == '#' || visited[i][nextX][nextY][now.check]) continue;
                visited[i][nextX][nextY][now.check] = true;
                q.offer(new Node(i, nextX, nextY, now.time + 1, now.check));

            }
        }
        return -1;
    }

    private static boolean isInRange(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }
}

문제 풀이

문제 풀기 전에는 방향만 잘 처리하면 쉬운 문제라고 생각했지만 생각만큼 쉽게 풀리지 않았다.
그래서 무엇이 문제인가 고민해 봤는데 목적지가 2개인 것이 잘 풀리지 않는 원인이었다. 그래서 visited 배열에 목적지 방문 여부를 추가한 후 정답을 받을 수 있었다.
기본적인 BFS는 단순히 해당 블록에 방문했는지만 체크하면 되지만, 이 문제는 고려해야 할 요소가 더 있다. 해당 블록에 진입하는 방향과 목적지의 방문 여부이다. 그렇기에 visited배열을 4차원으로 구성했다.
Queue에서 꺼낸 현재 노드의 좌표가 목적지의 좌표라면 목적지의 방문 여부를 체크하는 check 변수의 값을 변경한다. 만약 check == 3인 경우 두 목적지 모두 방문했다는 의미이기 때문에 해당 시간을 리턴한다.
만약 꺼낸 노드의 좌표가 목적지가 아니라면 방향과 visited배열의 값을 확인해 BFS를 수행하면 된다.


Review

만만하게 봤지만 만만하지는 않았던 문제. 그렇다고 어렵지는 않았던 문제.

profile
기억은 유한, 기록은 무한

0개의 댓글