[골드3] 2206. 벽 부수고 이동하기(Java)

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

2206번: 벽 부수고 이동하기

다른거 부술뻔...

---

※  문제를 요약하면 아래와 같습니다.

▶ N x M 행렬로 표현되는 맵에서 0은 이동할 수 있고 벽은 1로 표시,  (1,1) -> (N, M)으로 이동

▶ 최소 경로를 탐색, 필요하다면 1회 벽을 한 번 부수고 이동 가능

▶ 임의의 칸에서는 상,하,좌,우로 1칸만 움직임 가능

▶  Input : 첫째 줄에 N(세로), M(가로) 값, 다음 N개의 줄에 M개의 숫자로 맵이 입력

▶  Output : 최단 거리 출력, 불가능시 -1출력

---

◈ Input - 1

6 4
0100
1110
1000
0000
0111
0000

◈ Output - 1

15

◈ Input - 2

4 4
0111
1111
1111
1110

◈ Output - 2

-1

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 최소 경로 == BFS 탐색, 방문처리 필수

▶ Row, Col 좌표, 현재 탐색한 경로 수, 벽을 부순 여부 를 Point Class형태로 저장

▶ 맵의 값이 1인 경우를 전부 저장하여 하나씩 0으로 바꾸고 BFS 탐색 == 무조건 시간 초과

▶ 1을 0으로 바꾸고 일반적인 2차원 배열 방문처리 진행 시, 방문해야 할 곳을 못방문할 경우 발생

      ex)   0111

              0010   

              위의 예시에서 동서남북 순서로 탐색 시 윗줄 최초의 1을 0으로 바꾼 후

 

              남쪽 탐색 하여 해당 좌표를 방문처리할 경우, 목적지에 도달 불가 

▶ 위와 같은 케이스를 방지하기 위해 벽을 부순 경우의 방문 처리와 벽을 부수지 않은 경우의 방문 처리를 분류

▶ 3차원 좌표 0과 1을 갖는 방문처리 3차원 배열을 선언하여 벽을 부순 경우와 부수지 않은 경우의 방문 처리를 분류

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Point {
	int nRow;
	int nCol;
	int nCount;
	boolean bBreak;

	public Point(int nRow, int nCol, int nCount, boolean bBreak) {
		this.nRow = nRow;
		this.nCol = nCol;
		this.nCount = nCount;
		this.bBreak = bBreak;
	}
}

public class Main {
	static BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));
	static boolean[][][] barrVisited;
	static boolean[][] barrMap;
	static int nDay = 0;
	static int N, M;
	static int nMin = 1000 * 1000;

	public static void main(String[] args) throws IOException {
		// 대박 대박 대박
		System.setIn(new FileInputStream(Main.class.getResource("input.txt").getPath()));

		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));

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

		N = Integer.parseInt(st.nextToken()); // rows
		M = Integer.parseInt(st.nextToken()); // cols

		barrMap = new boolean[N][M];
		barrVisited = new boolean[N][M][2];
		
		// 맵 정보 입력
		for (int i = 0; i < N; i++) {
			String strLine = bReader.readLine();
			for (int j = 0; j < M; j++) {
				if (strLine.charAt(j) == '1') {
					barrMap[i][j] = true;
				}
			}
		}

		// 탐색합시당
		BFS();

		if (nMin == 1000 * 1000)
			nMin = -1;

		bWriter.write(String.valueOf(nMin));

		bWriter.flush();
		bWriter.close();
	}

	public static void BFS() throws IOException {
		// 동서남북 탐색
		int dr[] = { 0, 0, 1, -1 };
		int dc[] = { 1, -1, 0, 0 };

		// 1을 0으로 하나씩 바꿔가면서 탐색해보자
		// 1== 벽

		// 만약 벽이 없다면 한 번만 BFS돌려라

		Queue<Point> queueBfs = new LinkedList<>();
		queueBfs.add(new Point(0, 0, 0, false));
		// BFS 돌려보자~
		while (!queueBfs.isEmpty()) {
			Point p = queueBfs.poll();
			p.nCount++;

			// 도착하여 어떤 것이 제일 최소 경로인지 봅시당
			if (p.nRow == N - 1 && p.nCol == M - 1) {
				if (nMin > p.nCount)
					nMin = p.nCount;
				return;
			}


			// 동서남북 탐색
			for (int k = 0; k < dr.length; k++) {
				int nSearchRow = p.nRow + dr[k];
				int nSearchCol = p.nCol + dc[k];

				int nBroken = 0;

				// 2차원 visited를 벽을 부신 후와 부시지 않은 후로 나눈다아. == 3차원이 된다.
				if (p.bBreak)
					nBroken = 1;
				// 방문한 적이 있는감
				if (nSearchRow >= 0 && nSearchCol >= 0 && nSearchRow < N && nSearchCol < M
						&& !barrVisited[nSearchRow][nSearchCol][nBroken]) {
					// 다음이 0이다 (벽이 읎다)
					if (!barrMap[nSearchRow][nSearchCol]) {
						barrVisited[nSearchRow][nSearchCol][nBroken] = true;
						queueBfs.add(new Point(nSearchRow, nSearchCol, p.nCount, p.bBreak));
					} else if (barrMap[nSearchRow][nSearchCol] && !p.bBreak) {
						// 다음이 1인데 아직 벽을 한 번도 안부수었도다.
						barrVisited[nSearchRow][nSearchCol][nBroken] = true;
						queueBfs.add(new Point(nSearchRow, nSearchCol, p.nCount, true));
					}
				}
			}
		}

	}
}

Good Luck! (피드백 감사합니다!)