이번에 풀어본 문제는
백준 17836번 공주님을 구해라! 입니다.

📕 문제 링크

❗️코드

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

class Warrior
{
    int x,y,t;
    int sword;

    public Warrior(int x, int y, int t, int sword) {
        this.x = x;
        this.y = y;
        this.t = t;
        this.sword = sword;
    }
}
public class Main {
    static int N,M,T;
    static int [][] map;
    static boolean [][][] visited;
    static int [] dx = {-1,1,0,0};
    static int [] dy = {0,0,-1,1};
    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());
        T = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        visited = new boolean[N][M][2];

        for(int i = 0; i < N; i++)
        {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++)
            {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

//        PriorityQueue<Warrior> q = new PriorityQueue<>(new Comparator<Warrior>()
//        {
//            @Override
//            public int compare(Warrior o1, Warrior o2)
//            {
//                return o1.t - o2.t;
//            }
//        });
        Queue<Warrior> q = new LinkedList<>();
        q.add(new Warrior(0,0,0,0));
        visited[0][0][0] = true;
        int minVal = -1;
        while(!q.isEmpty())
        {
            Warrior cur = q.poll();
            //시간초과
            if(cur.t > T) continue;
            //공주한테 도달
            if((cur.x == N-1) && (cur.y == M-1))
            {
                minVal = cur.t;
                break;
            }
            for(int idx = 0; idx < 4; idx++)
            {
                int mx = cur.x + dx[idx];
                int my = cur.y + dy[idx];
                int hasSword = cur.sword;

                if(!isValid(mx,my)) continue;
                //검이 없을때
                if(hasSword == 0)
                {
                    if(visited[mx][my][0] || map[mx][my] == 1) continue;
                    //검을 주움
                    if(map[mx][my] == 2) hasSword++;

                }
                //있을때
                else
                {
                    if(visited[mx][my][1]) continue;
                }
                visited[mx][my][hasSword] = true;
                q.add(new Warrior(mx,my,cur.t+1,hasSword));

            }
        }
        System.out.print(minVal < 0 ? "Fail" : minVal);
    }
    static boolean isValid(int x, int y)
    {
        return x >= 0 && y >= 0 && x < N && y < M;
    }
}

📝 풀이

(0,0)위치의 용사가 (N,M)위치에 있는 공주를 구할 수 있다면 최단거리, 구할 수 없다면 Fail을 출력하는 문제입니다.
평범한 그래프 탐색 문제같지만 벽을 부술 수 있는 검이라는 재미있는 요소가 하나 존재합니다. 만약 경로에서 검을 습득하게 되면, 개수 제한 없이 벽을 부수며 공주에게 도달할 수 있습니다. 방문배열을 2차원으로 사용하게 되면, 검을 주운 이후에 앞지르는 경우를 고려할 수 없기 때문에, 검이 있을때와 없을 때를 구분하여 방문배열을 활용해주어야 합니다.

📜 후기

스토리가 있어 재밌는 문제였습니다 ㅋㅋㅋ