[백준] 1175 배달

www.acmicpc.net/problem/1175

1175번: 배달

2020-12-20

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main1175 {
    public static int N, M, answer, baedal[][];
    public static char arr[][];
    public static boolean flag, vtd[][][][];
    public static Queue<Person> q;
    public static int dx[] = {-1, 0, 1, 0};
    public static int dy[] = {0, -1, 0, 1};
    
    public static class Person {
        int x;
        int y;
        int dir;
        int g;
        public Person(int x, int y, int dir, int g) {
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.g = g;
        }
    }
    public static void solve() {
        int count  = 0;
        loop:while(!q.isEmpty()) {
            int size = q.size();
            while(size > 0) {
                Person tmp = q.poll();
                int x = tmp.x;
                int y = tmp.y;
                int dir = tmp.dir;
                int g = tmp.g;
                if(x == baedal[0][0] && y == baedal[0][1]) { // 1번 C
                    if(g != 1) g += 1;
                } else if(x == baedal[1][0] && y == baedal[1][1]) { // 2번 C
                    if(g != 2) g += 2;
                }
                if(g == 3) {
                    flag = true;
                    answer = count;
                    break loop;
                }
                for(int i = 0; i < 4; i++) {
                    if(i != dir) {
                        int nx = x + dx[i];
                        int ny = y + dy[i];
                        
                        if(nx < 0 || ny < 0 || nx >= N || ny >= M || arr[nx][ny] == '#' ) continue;
                        else if(!vtd[nx][ny][i][g]){
                            q.add(new Person(nx, ny, i, g));
                            vtd[nx][ny][i][g] = true;
                        }
                    }
                }                
                size--;
            }
            count++;
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new char[N][M];
        baedal = new int[2][2];
        vtd = new boolean[N][M][4][4]; // N / M / dir / baedal (1+2 => 3)
        q = new LinkedList<>();
        answer = 0;
        flag = false;
        
        int temp = 0; // 배달 array 
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(bf.readLine());
            String str = st.nextToken();
            for(int j = 0; j < M; j++) {
                arr[i][j] = str.charAt(j);
                if(arr[i][j] == 'S') {
                    for(int k = 0; k < 4; k++) {
                        q.add(new Person(i, j, k, 0));
                        vtd[i][j][k][0] = true;
                    }
                }
                if(arr[i][j] == 'C') {
                    baedal[temp][0] = i;
                    baedal[temp][1] = j;
                    temp++;
                }
            }
        }
        
        solve();
        
        if(!flag) answer = -1;
        System.out.println(answer);
    }
}
 

 

#문제풀이 

1. 입력을 받을 때, S (시작점)인 경우 4가지 방향을 다 체크할 수 있도록 queue에 넣어준다.  C (선물 배달)인 경우, 0번째에 x좌표값을, 1번째에 y좌표값을 baedal이라는 배열에 받았다. 선물 블록(C)은 딱 두개만 있으므로 첫번째는 1, 두 번째는 2라고 생각했다.

 

2. vtd 배열 (방문 좌표 체크)은 4차원으로 만들어서 x, y 좌표뿐만 아니라 dir과 배달을 간 적이 있는지를 체크할 수 있는 gift 값도 체크할 수 있도록 하였다. 마찬가지로 Person이란 클래스를 만들어서 x, y, dir, gift 값을 저장할 수 있도록 하였다.

 

3.  queue를 size만큼 돌면 하나의 레벨을 체크할 수 있으므로, size가 0이 되면 한 번 이동으로 count를 체크해주었다. queue를 돌면서 만약에 queue에서 꺼낸 좌표 값이 선물의 좌표값과 같은 경우, g 값을 체크해서 g값이 현재 선물값과 같은 경우(1 or 2)에는 선물을 업데이트 해주지 않았고 다른 경우에만 해주었다. 만약 g가 3인 경우는 1과 2를 모두 방문했다라는 의미이므로 count 값을 answer에 저장해주고 함수를 끝냈다.

 

4. 4방향을 체크해주면서 갖고 있는 dir과 다른 경우 그리고 vtd[x][y][dir][gift]방문한적이 없는 경우에 새로 queue에 넣고 체크해주었다. 

 

 

 

# 포인트

C : 민식이가 반드시 선물을 배달해야 하는 곳이다. 이러한 블록은 정확하게 2개 있다.

 

맨처음에 C가 무조건 2개라는 문제 조건을 확인을 안 했어서, 좀 다른 방향으로 체크했었다. 답은 맞았지만 제출했을 때 오류가 있었어서, 다시 확인해보니 위의 조건이 있다라는 것을 확인하고 다른 방향으로 gift 쪽을 체크했다.