17836. 공주님을 구해라

- 검을 가지고 다시 왔던 길을 가야할 수 있기 때문에 방문처리를 3차원으로 해주는 것이 핵심 포인트였다.

package baekjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class B_17836_공주님을구해라 {

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int T = Integer.parseInt(st.nextToken());
		int[][] arr = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		int result = bfs(N, M, T, arr);
		if (result == -1)
			sb.append("Fail");
		else
			sb.append(result);
		System.out.println(sb);
	}

	private static int bfs(int N, int M, int T, int[][] arr) {
		int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
		Queue<Node> q = new LinkedList<>();
		boolean[][][] visited = new boolean[N][M][2];
		// 검을 가지고 다시 가야할 수 있는 경우가 있으므로
		// 검이 없는 상황에서 이미 방문하였다면 중복 방문으로 그 곳을 갈 수 없기 때문에
		// 3차원의 배열로 해주어야 한다.

		// 또한 큐에 들어있는 좌표에서 검의 여부에 따라 연산을 각각 수행해야 하므로
		// Node안에 검의 유무를 같이 넣어주어야 한다.
		q.offer(new Node(0, 0, 0, 0));
		visited[0][0][0] = true;
		while (!q.isEmpty()) {
			Node now = q.poll();
			int y = now.y;
			int x = now.x;
			int cnt = now.cnt;
			int isPass = now.isPass;
			if (cnt > T) // 시간 초과
				return -1;
			if (y == N - 1 && x == M - 1) // 공주를 구하면
				return cnt;
			for (int i = 0; i < 4; i++) {
				int my = y + dir[i][0];
				int mx = x + dir[i][1];
				if (my < 0 || mx < 0 || my >= N || mx >= M || visited[my][mx][isPass])
					continue;
				if (isPass == 0 && arr[my][mx] == 1) // 검이 없고 벽이면
					continue;
				visited[my][mx][isPass] = true;
				if (arr[my][mx] == 2) { // 검을 잡으면
					q.offer(new Node(my, mx, cnt + 1, 1));
					continue;
				}
				q.offer(new Node(my, mx, cnt + 1, isPass));
			}
		}
		return -1; // 공주를 구하지 못하면 - 공주의 좌표까지 가지 못할 경우
	}

	static class Node {
		int y, x, cnt, isPass;

		public Node(int y, int x, int cnt, int isPass) {
			super();
			this.y = y;
			this.x = x;
			this.cnt = cnt;
			this.isPass = isPass;
		}

	}
}