[Java] 백준 31716 - 현대모비스 자율 주행 테스팅 1

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

---

풀이

한 트랙에서 1열 → N열로 이동하는 최소거리는 BFS 돌리면 금방 나오는데

한 트랙에서 다음 트랙으로 넘어갈때 이동 거리를 꼼꼼하게 처리해줘야 한다.

특히, 해당 트랙 도착점의 행과 다음 트랙 시작점의 행을 맞춰주는 작업이 필요하다.

 

 

---

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		long K = Long.parseLong(st.nextToken());
		char[][] board = new char[2][N];

		for (int r = 0; r < 2; r++) {
			for (int c = 0; c < N; c++) {
				board[r][c] = (char) br.read();
			}
			br.readLine();
		}
		br.close();

		Queue<int[]> que = new LinkedList<>();
		int[][][] dist = new int[2][N][2];
		long moveWithinBlock = -1;
		int startRow = 0;
		int endRow = 0;

		for (int r = 0; r < 2; r++) {
			for (int c = 0; c < N; c++) {
				dist[r][c][0] = -1;
			}
		}

		if (board[0][0] == '.') {
			que.add(new int[] { 0, 0 });
			dist[0][0][0] = 0;
			dist[0][0][1] = 0;
		}
		if (board[1][0] == '.') {
			que.add(new int[] { 1, 0 });
			dist[1][0][0] = 0;
			dist[1][0][1] = 1;
		}

		while (!que.isEmpty()) {
			int[] cur = que.remove();
			int r = cur[0];
			int c = cur[1];

			if (c == N - 1) {
				moveWithinBlock = dist[r][c][0];
				startRow = dist[r][c][1];
				endRow = r;
				break;
			}

			if (board[r][c + 1] == '.') {
				if (dist[r][c + 1][0] == -1) {
					dist[r][c + 1][0] = dist[r][c][0] + 1;
					dist[r][c + 1][1] = dist[r][c][1];
					que.add(new int[] { r, c + 1 });
				}
			} else if (board[(r + 1) % 2][c] == '.') {
				if (dist[(r + 1) % 2][c][0] == -1) {
					dist[(r + 1) % 2][c][0] = dist[r][c][0] + 1;
					dist[(r + 1) % 2][c][1] = dist[r][c][1];
					que.add(new int[] { (r + 1) % 2, c });
				}
			} else {
				System.out.println(-1);
				return;
			}
		}

		long moveToNextBlock = 0;

		if (K > 1) {
			if (startRow == endRow) {
				moveToNextBlock = 1;
			} else {
				if (board[endRow][0] == '.') {
					moveToNextBlock = 2;
				} else if (board[(endRow + 1) % 2][N - 1] == '.') {
					moveToNextBlock = 2;
				} else {
					System.out.println(-1);
					return;
				}
			}
		}

		System.out.println(moveWithinBlock * K + moveToNextBlock * (K - 1));
	}
}

---

테스트 케이스

// case 1:
2 1
#.
.#
expected output: -1

// case 2:
5 1
...#.
.#...
expected output: 5
    
// case 3:
5 3
...#.
.#...
expected output: 19

// case 4:
5 3
#....
..#..
expected output: 19

// case 5:
5 3
....#
..#..
expected output: 19

// case 6:
5 3
#....
..#.#
expected output: -1

// case 7:
5 3
#...#
..#..
expected output: 20