[BOJ][Java] 16930. 달리기

문제

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

 

문제 이해

• N×M 체육관에 빈 칸(.)과 벽(#)이 있다.
• 한 번 이동할 때, 상·하·좌·우 중 한 방향으로 1칸 이상 k칸 이하를 이동할 수 있다.
• 시작점에서 도착점까지 이동하는 최소 시간을 구한다.

 

문제 풀이

BFS를 이용하여 각 칸에 도달하는 최소 시간을 기록한다.
상하좌우(dr, dc) 네 방향에 대해 1..k칸 이동하는 경우를 탐색한다.

 

상태 정의

• map[r][c] = -1: 미방문, -2: 벽으로 초기화
• BFS 탐색하면서 해당 칸에 도달한 최소 시간 저장

 

탐색 조건

1. 미방문: map[nr][nc] == -1
   지금이 처음 도달이므로 map[nr][nc] = map[cur.r][cur.c] + 1로 갱신하고 큐에 넣는다.
   
   

2. 이미 더 빠른 시간에 도달 map[nr][nc] < map[cur.r][cur.c] + 1
   이 칸에는 현재 시간보다 빠르게 이미 왔으므로, 그 뒤 칸들도 이 경로보다 이득이 될 수 없다.
   → 이 방향 탐색을 중단한다. (break)
   
   

3. 같은 시간으로 이미 방문 map[nr][nc] == map[cur.r][cur.c] + 1
   • 다른 경로로 같은 이동 시간에 이미 큐에 들어갔던 칸.
   • 다시 큐에 넣을 필요는 없다.
   • 하지만 그 뒤 칸은 아직 미방문일 수 있으므로 계속 확인해야 한다.
     → 이번 칸은 패스하고 같은 방향의 다음 칸으로 진행 (continue)

 

if (map[nr][nc] == -1) { // 미방문
    q.offer(new Point(nr, nc));
    map[nr][nc] = map[cur.r][cur.c] + 1;
} else if (map[nr][nc] < map[cur.r][cur.c] + 1) { // 이미 현재 시간보다 빨리 도착.
    break;
    } 
// map[nr][nc] == map[cur.r][cur.c] + 1 이면 그냥 다음 칸 계속

 

4. 도착 좌표 (er, ec)를 만나면 즉시 `return`한다. (BFS이므로 가장 처음 방문했을 때가 최소 시간)

 

주의 사항

범위를 벗어났거나 벽(#)을 만났을 때는 continue가 아니라 break를 써야 한다.

: 같은 방향으로 칸을 늘려가는 과정에서 앞이 막히면 그 뒤 칸들도 전부 갈 수 없기 때문.
→ 이 방향 탐색 자체를 중단해야 한다.

 

코드

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

public class Main {
	static class Point {
		int r, c;

		public Point(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	static int n, m, k, sr, sc, er, ec;
	static int[][] map;
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 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());
		k = Integer.parseInt(st.nextToken());
		map = new int[n][m];

		for (int i = 0; i < n; i++) {
			String s = br.readLine();
			for (int j = 0; j < m; j++) {
				if (s.charAt(j) == '.') {
					map[i][j] = -1; // 미방문
				} else {
					map[i][j] = -2; // 벽
				}
			}
		}

		st = new StringTokenizer(br.readLine());
		sr = Integer.parseInt(st.nextToken()) - 1;
		sc = Integer.parseInt(st.nextToken()) - 1;
		er = Integer.parseInt(st.nextToken()) - 1;
		ec = Integer.parseInt(st.nextToken()) - 1;

		System.out.println(bfs());
	}

	static int bfs() {
		Queue<Point> q = new LinkedList<>();

		map[sr][sc] = 0;
		q.offer(new Point(sr, sc));

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

			for (int i = 0; i < 4; i++) {
				for (int j = 1; j <= k; j++) {
					int nr = cur.r + dr[i] * j;
					int nc = cur.c + dc[i] * j;

					if (nr < 0 || nc < 0 || nr >= n || nc >= m || map[nr][nc] == -2)
						break;

					if (nr == er && nc == ec)
						return map[cur.r][cur.c] + 1;

					if (map[nr][nc] == -1) { // 미방문
						q.offer(new Point(nr, nc));
						map[nr][nc] = map[cur.r][cur.c] + 1;
					} else if (map[nr][nc] < map[cur.r][cur.c] + 1) { // 이미 현재 시간 이하로 도착했음.
						break;
					}
				}
			}
		}
		return map[er][ec];
	}
}