[백준 골드1] 1175번: 배달 (BFS) - Java

1175번: 배달

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

 

문제
어제 선물을 모두 포장한 민식이는 이제 선물을 배달하려고 한다. 민식이가 선물을 배달할 곳은 이 문제를 읽는 사람들이 앉아 있는 교실이다. 교실은 직사각형모양이고, 모두 같은 크기의 정사각형 블록으로 나누어져 있다.
입력으로 교실의 지도가 주어진다. 각각의 정사각형 블록은 다음과 같이 4가지 종류가 있다.
S: 지금 민식이가 있는 곳이다. 이곳이 민식이가 배달을 시작하는 곳이고 1개만 있다.
C: 민식이가 반드시 선물을 배달해야 하는 곳이다. 이러한 블록은 정확하게 2개 있다.
#: 민식이가 갈 수 없는 곳이다.
.: 민식이가 자유롭게 지나갈 수 있는 곳이다.
민식이가 한 블록 동서남북으로 이동하는데는 1분이 걸린다. 민식이는 네가지 방향 중 하나로 이동할 수 있으며, 교실을 벗어날 수 없다. 민식이가 선물을 배달해야 하는 곳에 들어갈 때, 민식이는 그 곳에 있는 사람 모두에게 선물을 전달해야 한다. 이 상황은 동시에 일어나며, 추가적인 시간이 소요되지 않는다.
민식이는 어느 누구도 자신을 보지 않았으면 하기 때문에, 멈추지 않고 매 시간마다 방향을 바꿔야 한다. 이 말은 같은 방향으로 두 번 연속으로 이동할 수 없다는 말이다. 민식이가 선물을 모두 배달하는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

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

출력
첫째 줄에 민식이가 선물을 모두 배달하는데 걸리는 시간의 최솟값을 출력한다. 만약 불가능 할 때는 -1을 출력한다.

예제 입력 1 
2 3
SCC
...
예제 출력 1 
4
예제 입력 2 
1 5
C.C.S
예제 출력 2 
-1
예제 입력 3 
3 3
#.#
CSC
#.#
예제 출력 3 
5
예제 입력 4 
10 7
#.#....
##...#.
C#...#.
.....#.
..#....
..#S.#.
.##..#.
###..##
..C.#.#
###.#..
예제 출력 4 
24
예제 입력 5 
3 36
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#C
.................S..................
C#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
예제 출력 5 
155

---

풀이

시도

선물을 좌표평면 상의 두 곳에 배달하고 최소 시간을 구해야 하는 문제이므로 BFS로 해결할 수 있다.

다만, 방문했던 칸을 다시 방문해야 하는 상황이 있어 단순히 visited[y][x]로 방문 여부를 체크하거나 중복 방문을 모두 허용하면 정답을 구할 수 없다.

<테스트 케이스 비교>

(1) 2 3 / SCC / ... -> 4

(2) 2 3 / SCC / #.# -> 4

(3) 2 3 / CSC / #C# -> 5

"방향, 배달 여부"를 함께 확인해야 한다.

(다차원을 생각하는 것이 어려워 다른 분들의 풀이를 바탕으로 공부했다.

참고: https://sookr5416.tistory.com/307, https://drasgon.tistory.com/278)

- 다음에 갈 점을 어떤 방향에서 방문했었는지(같은 길 다시 가지 않아야 최소 시간) => 한 차원 추가

- 어떤 선물을 배달한 상태로 지나갔었는지(상태) => 한 차원 추가 (비트마스킹 사용해 체크)

=> visited를 4차원 배열로 만들어 사용!

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main
{
    static class Node {
        int x, y, dir, time, delivered;
        
        public Node(int x, int y, int dir, int time, int delivered) {
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.time = time;
            this.delivered = delivered;
        }
    }
    
    static int n, m;
    static char[][] map;
    static int[][] dirs = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
    static int[][] giftPos = new int[2][2];
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nm = br.readLine().split(" ");
        n = Integer.parseInt(nm[0]);
        m = Integer.parseInt(nm[1]);
        map = new char[n][m];
        
        int sx=0, sy=0, giftIdx=0;
        for(int i=0; i<n; i++) {
            String line = br.readLine();
            for(int j=0; j<m; j++) {
                map[i][j] = line.charAt(j);
                if (map[i][j] == 'S') {
                    sx = j;
                    sy = i;
                } else if (map[i][j] == 'C') {
                    giftPos[giftIdx][0] = j;
                    giftPos[giftIdx++][1] = i;
                }
            }
        }
        int result = bfs(sx, sy);
        System.out.println(result);
    }
    
    static int bfs(int sx, int sy) {
        Queue<Node> q = new LinkedList<>();
        boolean[][][][] visited = new boolean[n][m][4][4]; // y, x, 방향, 배달한 선물 비트마스크
        
        q.add(new Node(sx, sy, -1, 0, 0)); // 시작점
        
        while(!q.isEmpty()) {
            Node cur = q.poll();
            if (cur.delivered == 0b11) // 모두 배달 완료
                return cur.time;
           
            for (int d = 0; d < 4; d++) {
                if (d == cur.dir)
                    continue;
                int nx = cur.x + dirs[d][0];
                int ny = cur.y + dirs[d][1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && map[ny][nx] != '#') {
                    int nextDelivered = checkDelivered(nx, ny, cur.delivered); // 다음 선물 배달 상태
                    if (!visited[ny][nx][d][nextDelivered]) {
                        visited[ny][nx][d][nextDelivered] = true;
                        q.add(new Node(nx, ny, d, cur.time+1, nextDelivered));
                    }
                }
            }
        }
        return -1;
    }
    
    static int checkDelivered(int x, int y, int delivered) {
        if (x == giftPos[0][0] && y == giftPos[0][1]) delivered |= 0b01; // 첫 번째 C 배달 체크
        if (x == giftPos[1][0] && y == giftPos[1][1]) delivered |= 0b10; // 두 번째 C 배달 체크
        return delivered;
    }
}