[백준 알고리즘] 17836번: 공주님을 구해라! (JAVA)

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

코드

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

public class Main {
	public static int n, m, t;
	public static int[][] maps;
	public static boolean[][][] visited;
	public static int[] dx = { 0, 1, 0, -1 };
	public static int[] dy = { 1, 0, -1, 0 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		t = Integer.parseInt(st.nextToken());

		maps = 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++) {
				maps[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		int answer = bfs();

		if (answer == 0 || answer > t)
			System.out.println("Fail");
		else
			System.out.println(answer);
	}

	public static int bfs() {
		Queue<Node> q = new ArrayDeque<Node>();
		visited[0][0][0] = true;
		q.offer(new Node(0, 0, 0, false));

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

			if (cur.x == n - 1 && cur.y == m - 1)
				return cur.time;

			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];

				if (check(nx, ny)) {
					// 검이 없는 경우
					if (!cur.sword) {
						if (!visited[nx][ny][0]) {
							if (maps[nx][ny] == 2) {
								visited[nx][ny][1] = true;
								q.offer(new Node(nx, ny, cur.time + 1, true));
							} else if (maps[nx][ny] == 0) {
								visited[nx][ny][0] = true;
								q.offer(new Node(nx, ny, cur.time + 1, cur.sword));
							}
						}
					}

					// 검 있을 때
					else {
						if (!visited[nx][ny][1]) {
							visited[nx][ny][1] = true;
							q.offer(new Node(nx, ny, cur.time + 1, cur.sword));
						}
					}
				}
			}
		}
		return 0;
	}

	public static boolean check(int x, int y) {
		if (0 <= x && x < n && 0 <= y && y < m)
			return true;
		else
			return false;
	}
}

class Node {
	int x;
	int y;
	int time;
	boolean sword;

	public Node(int x, int y, int time, boolean sword) {
		this.x = x;
		this.y = y;
		this.time = time;
		this.sword = sword;
	}
}

 

 

풀이

• 가장 중요한 부분은 visited 배열로 방문을 체크할 때 검이 있을 경우, 없을 경우를 따로 처리해줘야 한다는 점입니다.
• 만약 여느때와 같이 2차원 배열로 visited를 처리했을 경우에 검을 가지고 갈 수 있는 길을 다시 가지 못하는 경우가 발생할 수 있습니다. 그 이유는 이미 검이 없을 때 해당 격자를 지나왔고, visited에 true로 체크를 해준다면 검이 생겼을 때 다시 그 길로 돌아갈 수 없기 때문입니다. 하지만 다시 돌아갔을 때, 공주님에게로 가는 가장 빠른 길을 찾을 수도 있겠지요 !