문제 풀이

n이 최대 500이기때문에 dfs로 풀면 시간초과가 발생한다.
그렇기 때문에 특정 지점에서 특정 지점까지 거리를 구하면서 해당 거리를 현재 가지고 있는 체력과 우산의 내구도로 갈 수 있는지, 갈 수 있다면 얼만큼 소비해서 가는지 등을 구해서 일일이 좌표를 한칸씩 움직이지 않고 이동해야한다.

그렇기 위해서는 S,E 지점의 좌표를 저장하고 U의 좌표를 배열 형태로 저장한다.
S에서 시작해서 거쳐갈 수 있는 U의 모든 경우를 백트래킹 형식으로 확인하면 된다.
그리고 매번 현재 위치에서 E로 갈 수 있는지 없는지 체크하면된다.

예를 들어 우산이 세개로 U1, U2, U3이 있다면

S -> U1 -> U2 -> U3 -> E
S -> U1 -> U3 -> U2 -> E
S -> U2 -> U1 -> U3 -> E
S -> U2 -> U3 -> U1 -> E
S -> U3 -> U1 -> U2 -> E
S -> U3 -> U2 -> U1 -> E

이렇게 모든 경우의 수를 체크하면된다.

문제 링크

boj/22944

소스코드

PS/22944.java

    import java.io.*;
    import java.util.*;

    public class Main {
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        static int []visit ;
        static int sx,sy,ex,ey;
        static int n ,h,d;
        static int ans =2100000000;
        static ArrayList<Entity> umb = new ArrayList<>();
        static class Entity
        {
            int x,y;

            public Entity(int x, int y) {
                this.x = x;
                this.y = y;
            }
        }

        public static void main(String[] args) throws IOException {

            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken());
            visit = new int[11];

            for(int i=0;i<n;i++)
            {
                char []arr = br.readLine().toCharArray();
                for(int j=0;j<n;j++)
                {
                    if(arr[j] == 'S')
                    {
                        sx =j;
                        sy = i;
                    }
                    else if(arr[j] == 'E')
                    {
                        ex=j;
                        ey=i;
                    }
                    else if(arr[j] == 'U')
                        umb.add(new Entity(j, i));
                }
            }

            solution(sx,sy,h,0,0);
            if(ans == 2100000000)
                bw.write("-1");
            else
            bw.write(Integer.toString(ans));
            bw.flush();

        }
        static void solution(int x,int y, int life,int shield ,int cnt)
        {

            if(Math.abs(ex-x) + Math.abs(ey-y) <= life + shield)
            {
                ans = Math.min(ans,cnt + Math.abs(ex-x) + Math.abs(ey-y));
                return ;
            }
            for(int i=0;i<umb.size();i++) {
                int dis = Math.abs(umb.get(i).x - x) + Math.abs(umb.get(i).y - y);
                if(life + shield <= dis-1 || visit[i] ==1)
                    continue;
                if(shield < dis)
                {
                    visit[i] = 1;
                    solution(umb.get(i).x,umb.get(i).y,life - (dis-shield),d, cnt + dis);
                    visit[i] = 0;
                }
                else
                {
                    visit[i] = 1;
                    solution(umb.get(i).x,umb.get(i).y,life,d, cnt + dis);
                    visit[i] = 0;
                }
            }

        }


    }