[BOJ/JAVA] 백준 16930번 : 달리기

16930번: 달리기

 

 

---

 

 

 

• 풀이

 

시작점(x1,y1)부터 끝점(x2,y2)까지 최단거리로 이동할 수 있는 값 or 이동할 수 없으면 -1을 출력하면 되는 문제입니다.

 

조건은 아래와 같습니다.

• 벽은 지나갈 수 없다.
• 1초에 이동할 수 있는 칸의 최대 개수는 K개 이다.

 

위의 조건을 감안하여 해결해낸 풀이는 아래와 같습니다.

 

1. 큐를 통해 좌표를 꺼내옵니다.
2. 상, 하, 좌, 우를 각각 K번씩 이동합니다.
   1. 벽이 있으면 더이상 이동하지 않습니다.
   2. 한 번도 이동한적이 없다면 값을 초기화 해주고 큐에 추가합니다.
   3. 현재 이동할 값이랑 같다면 추가해줄 필요가 없으므로 지나갑니다.
3. 이동한 값이 (x2,y2)라면 값을 초기화해 준 후 종료합니다.

 

 

 

• 코드

 

import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {
	static int N, M, K, x1, x2, y1, y2, answer;
	static boolean[][] wall;
	static int[][] visit;
	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { -1, 1, 0, 0 };

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(answer);
	}

	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

		N = in.nextInt();
		M = in.nextInt();
		K = in.nextInt();
		wall = new boolean[N + 1][M + 1];
		for (int i = 1; i <= N; i++) {
			String s = in.nextLine();
			for (int j = 1; j <= M; j++) {
				if(s.charAt(j - 1)=='#')
					wall[i][j] = true;
			}
		}

		x1 = in.nextInt();
		y1 = in.nextInt();
		x2 = in.nextInt();
		y2 = in.nextInt();
		answer = Integer.MAX_VALUE;
		visit = new int[N + 1][M + 1];
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				visit[i][j] = Integer.MAX_VALUE;
			}
		}

		bfs();

		// 이동할 수 없는 경우
		if (answer == Integer.MAX_VALUE)
			answer = -1;
	}

	private static void bfs() {
		Queue<Node> pq = new LinkedList<>();
		pq.add(new Node(x1, y1, 0));
		visit[x1][y1] = 0;

		while (!pq.isEmpty()) {
			Node node = pq.poll();
			
			if (node.x == x2 && node.y == y2) {
				answer = Math.min(answer, node.distance);
				break;
			}

			for (int direction = 0; direction < 4; direction++) {
				for (int k = 1; k <= K; k++) {
					int r = node.x + dx[direction]*k;
					int c = node.y + dy[direction]*k;

					if(r < 1 || c < 1 || r > N || c > M || wall[r][c]) break;

					if (visit[r][c] == Integer.MAX_VALUE) {
						visit[r][c] = node.distance + 1;
						pq.add(new Node(r,c,node.distance + 1));
					}
					else if (visit[r][c] == node.distance + 1) {
						continue;
					}
					else break;
				}
			}
		}
	}
}

class Node{
	int x;
	int y;
	int distance;

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

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}