백준 1175 (배달) - java

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

1175번: 배달

 

문제

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

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

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

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

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

 

유형 : BFS

 

접근 방식

• 개인적으로 어려운 BFS의 조건 중 하나는 갔던 곳을 다시 가는 것이다.
  • 갔던 곳을 다시 간다고? : 애초에 방문 체크를 하는 이유가 다시 가는 걸(중복)을 방지하기 위해 하는 것이 아닌가?
  • 다시 생각해보자 : 단순히 좌표는 동일할지라도 해당 탐색 위치는 중복이지 않은 경우이다.
  • 구분할 수 있는 기준은 2개이다.
    • 해당 (x,y) 위치로 들어오는 방향 (방향 중복 방지를 위해서도 있다)
    • 찾은 개수 : 2와 4중 찾은 값 -> 2개 찾았으면 6
• already : 이미 찾았는지 확인하는 방법

    static boolean already(int cur,int t){
        // 현재 찾은 값을 cur이라 했을 때 t라는 값을 이미 찾았는지 확인하는 메소드
        int[] arr = {2,4};

        for(int i=1;i>=0;i--){
            if(cur >= arr[i]){
                if(t == cur)
                    return true; // 해당 값을 가지고 있다.

                cur -= arr[i];
            }
        }

        return false;
    }

 

전체 코드

import java.util.*;
import java.io.*;
public class Main {

    static int n = 0;
    static int m = 0;

    static int sx = 0;
    static int sy = 0;
    static int[][] board;

    static int result = -1;
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};

    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());

        board = new int[n+1][m+1];
        int land = 2;

        for(int i=1;i<=n;i++){

            String line = bf.readLine();

            for(int j=1;j<=m;j++){

                char cur = line.charAt(j-1);

                if(cur == '#'){
                    board[i][j] = -1; // 벽
                }else if(cur == 'S'){
                    sx = i;
                    sy = j; // 시작 좌표
                }else if(cur == 'C'){
                    board[i][j] = land; // 도착지 (2개이고 구분하기 위해 각각 2,4 설정)
                    land *= 2;
                }
            }
        }

        bfs();
        System.out.println(result);
        bf.close();
    }

    static void bfs(){
        Queue<Node> q = new LinkedList<>();
        int[][][][] v = new int[n+1][m+1][4][7]; // 행 , 열 , 방향 , 찾은 개수

        for(int i=0;i<4;i++){
            int nx = sx + dx[i];
            int ny = sy + dy[i];

            if(isOut(nx,ny))
                continue;

            if(board[nx][ny] == 0){
                v[nx][ny][i][0] = 1;
                q.add(new Node(nx,ny,i,0));
            }else if(board[nx][ny] >= 1){
                v[nx][ny][i][board[nx][ny]] = 1;
                q.add(new Node(nx,ny,i,board[nx][ny]));
            }
        }

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

            if(cur.f == 6){
                if(result == -1 || result > v[cur.x][cur.y][cur.d][cur.f]){
                    result = v[cur.x][cur.y][cur.d][cur.f];
                }
                return;
            }

            for(int i=0;i<4;i++){

                if(cur.d == i)
                    continue;

                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                if(isOut(nx,ny))
                    continue;

                if(board[nx][ny] == 0){
                    if(v[nx][ny][i][cur.f] == 0 || v[nx][ny][i][cur.f] > v[cur.x][cur.y][cur.d][cur.f] + 1){
                        v[nx][ny][i][cur.f] = v[cur.x][cur.y][cur.d][cur.f] + 1; // 빈 좌표 (그냥 이동)
                        q.add(new Node(nx,ny,i,cur.f));
                    }
                }else if(board[nx][ny] >= 1){
                    if(already(cur.f,board[nx][ny])){

                        if(v[nx][ny][i][cur.f] == 0 || v[nx][ny][i][cur.f] > v[cur.x][cur.y][cur.d][cur.f] + 1){
                            v[nx][ny][i][cur.f] = v[cur.x][cur.y][cur.d][cur.f] + 1; // (이미 찾았을 경우)
                            q.add(new Node(nx,ny,i,cur.f));
                        }
                    }else{
                        if(v[nx][ny][i][cur.f + board[nx][ny]] == 0 || v[nx][ny][i][cur.f + board[nx][ny]] > v[cur.x][cur.y][cur.d][cur.f] + 1 ){

                            v[nx][ny][i][cur.f + board[nx][ny]] = v[cur.x][cur.y][cur.d][cur.f] + 1;
                            q.add(new Node(nx,ny,i,cur.f + board[nx][ny])); // (새로 찾은 경우)
                        }
                    }
                }

            }
        }

    }
    static boolean already(int cur,int t){
        // 현재 찾은 값을 cur이라 했을 때 t라는 값을 이미 찾았는지 확인하는 메소드
        int[] arr = {2,4};

        for(int i=1;i>=0;i--){
            if(cur >= arr[i]){
                if(t == cur)
                    return true;

                cur -= arr[i];
            }
        }

        return false;
    }

    static boolean isOut(int nx,int ny){
        if(nx < 1 || nx > n || ny < 1 || ny > m)
            return true; // 밖을 나갈 경우

        if(board[nx][ny] == -1)
            return true; // 벽

        return false;
    }

}
class Node{
    int x;
    int y;
    int d;
    int f;

    Node(int x,int y,int d,int f){
        this.x = x; // x 좌표
        this.y = y; // y 좌표
        this.d = d; // d 방향
        this.f = f; // f 몇개 찾았는지
    }
}