100. 아맞다우산 (백준 17244) [JAVA]

 

 

문제

문제 링크 : https://www.acmicpc.net/problem/17244

17244번: 아맞다우산

문제

경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다.

"아 맞다 우산!!!"

경재 씨는 매번 외출하고 나서야 어떤 물건을 집에 놓고 왔다는 것을 떠올릴 때마다 자책감에 시달리는 것이 너무 싫었다.

외출이 잦은 경재 씨는 반복되는 일을 근절하기 위해 꼭 챙겨야 할 물건들을 정리해보았다. 하지만 지갑, 스마트폰, 우산, 차 키, 이어폰, 시계, 보조 배터리 등 종류와 개수가 너무 많았다.

평소 불필요한 움직임을 아주 싫어하는 경재 씨는 이 물건들을 최대한 빠르게 챙겨서 외출하는 이동 경로를 알고 싶었다.

경재 씨는 한 걸음에 상하좌우에 인접한 칸으로만 움직일 수 있다.

경재 씨를 위해 집을 위에서 바라본 모습과 챙겨야 할 물건들의 위치들을 알고 있을 때, 물건을 모두 챙겨서 외출하기까지 최소 몇 걸음이 필요한지 구하는 프로그램을 작성하자.

입력

첫 번째 줄에는 집의 가로 길이 N과 세로 길이 M이 입력된다. (3 ≤ N, M ≤ 50)

두 번째 줄부터는 집의 구조가 예제 입력과 같이 주어진다.

비어있는 곳은 '.'로 벽은 '#'로 입력된다. 경재 씨의 현재 위치는 S, 나가는 문의 위치는 E, 챙겨야 하는 물건은 종류에 상관없이 X로 입력된다.

챙겨야 하는 물건은 최대 5개까지 있을 수 있다. 집은 언제나 벽으로 둘러싸여 있고, 나가는 문은 언제나 하나이다.

출력

S에서 출발하여 모든 물건을 챙겨서 E까지 도착할 수 있는 최소 시간을 출력한다. 모든 물건을 챙길 수 없는 경우는 주어지지 않는다.

풀이

풀면서도 딱히 다른 풀이가 떠오르지 않아서 이렇게 풀어도 되나 싶은 문제였다.

문제를 크게 두 부분으로 나누어 보자면

1. 각각의 좌표에서 나머지 좌표간의 거리를 구하기 (BFS)
2. 모든 가능한 좌표 조합의 합에서 최소값을 구하기

나머지 좌표간의 거리를 구할 때, 굳이 종료포인트와 시작포인트에서는 할 필요가 없다.

(어차피 다른거에서 채워 넣으면 되므로)

순열을 만들 때는 꼭 시작포인트 - 1,2,3,4,5 - 종료포인트 임을 명심하여 거리를 더해줘야 한다.

코드

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

public class Main {

    static int N, M;
    static char[][] map;
    static Point startPoint;
    static Point endPoint;
    static ArrayList<Point> targetPoints = new ArrayList<>();

    static int[][] steps;
    static int[] moveX = {0,0,1,-1};
    static int[] moveY = {1,-1,0,0};

    static int answer = 999999999;
    static boolean visited[];

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

        map = new char[M][N];

        for(int i=0; i<M; i++){
            map[i] = br.readLine().toCharArray();
            for (int j = 0; j < N; j++) {
                if(map[i][j] == 'S'){
                    startPoint = new Point(j,i);
                    map[i][j] = 'X'; //X로 치환
                }
                else if(map[i][j] == 'E'){
                    endPoint = new Point(j,i);
                    map[i][j] = 'X';
                }
                else if(map[i][j] == 'X') {
                    targetPoints.add(new Point(j,i));
                }
            }
        }
        steps = new int[targetPoints.size()+2][targetPoints.size()+2];
        targetPoints.add(0,startPoint);
        targetPoints.add(targetPoints.size(), endPoint);

        visited = new boolean[targetPoints.size()];

        for(int i=0; i<targetPoints.size()-1; i++){
            BFS(targetPoints.get(i),i);
            steps[targetPoints.size()-1][i] = steps[i][targetPoints.size()-1];
            steps[i][i] = 999999999;
        }
        steps[targetPoints.size()-1][targetPoints.size()-1] = 999999999;
        Permutation(1,0,0);
        System.out.println(answer);
    }

    public static void BFS(Point st, int idx){
        Queue<Point> q = new LinkedList<>();
        int [][] visited = new int[M][N];

        q.add(st);
        visited[st.y][st.x] = 1;

        int size, nextX, nextY;
        int step = 0;
        int stepCount = targetPoints.size();

        while(!q.isEmpty()){
            size = q.size();
            for (int i = 0; i < size; i++) {
                Point cur = q.poll();

                if(map[cur.y][cur.x] == 'X'){
                    int check = CheckPoint(cur.y, cur.x);
                    steps[idx][check] = step;

                    stepCount--;

                    if(stepCount <= 0) return;
                    if(check == targetPoints.size()-1) continue;
                }

                for(int a=0; a<4; a++){
                    nextX = cur.x+moveX[a];
                    nextY = cur.y+moveY[a];

                    if(map[nextY][nextX] != '#' && visited[nextY][nextX] == 0){
                        q.add(new Point(nextX, nextY));
                        visited[nextY][nextX] = 1;
                    }
                }
            }
            step++;
        }
    }

    public static int CheckPoint(int y, int x){
        for(int i=0; i<targetPoints.size(); i++){
            if(targetPoints.get(i).getY() == y && targetPoints.get(i).getX() == x) return i;
        }
        return -1;
    }

    public static void Permutation(int count, int beforeIdx, int curSize){
        if(targetPoints.size()-1 == count){
            curSize += steps[beforeIdx][count];
            answer = Math.min(curSize, answer);
            return;
        }

        for(int idx = 1 ; idx< targetPoints.size()-1; idx++){
            if(!visited[idx]){
                visited[idx] = true;
                Permutation( count+1, idx, curSize+steps[beforeIdx][idx]);
                visited[idx] = false;
            }
        }
    }
}

결과

 

전문가가 아니라 정확하지 않은 지식이 담겨있을 수 있습니다.
언제든지 댓글로 의견을 남겨주세요!