[백준 JAVA] 2206번: 벽 부수고 이동하기

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

 

public static int N, M;
public static int[][] map, copyMap;
public static int[] visited;
public static int[] dx = {0, 0, -1, 1};
public static int[] dy = {1,-1, 0, 0};
// 1. 입력값 받기
// 1-1. map, copyMap 초기화
// 1-2. map, copyMap 받아옴
// 2. bfs 탐색
// 2-1. 4방탐색 visited[0]이면 1늘리고 도착

// 3-1. map[N-1][M-1] = 0 이라면 -1 출력 아니면 그값 출력

 

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

public class Main {
	public static int N, M;
	public static int[][] map;
	public static int[][][] visited;
	public static int[] dx = { 0, 0, -1, 1 };
	public static int[] dy = { 1, -1, 0, 0 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		// 1. 입력값 받기
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		// 1-1. map, copyMap 초기화
		map = new int[N][M];
		visited = new int[N][M][2];
		// 1-2. map받아옴
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = str.charAt(j) - '0';
			}
		}
		// 2. bfs 탐색
		bfs();
	}

	public static void bfs() {
		// 2-1. 4방탐색 visited[0]이면 1늘리고 도착
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] { 0, 0, 1, 0 });
		visited[0][0][0] = 1;
		while (!q.isEmpty()) {
			int[] cur = q.poll();
			int x = cur[0];
			int y = cur[1];
			int cnt = cur[2];
			int dis = cur[3];

			if (x == N - 1 && y == M - 1) {
				System.out.println(cnt);
				return;
			}

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

				if (nx < 0 || nx >= N || ny < 0 || ny >= M)
					continue;

				int next_cnt = cnt + 1;

				if (map[nx][ny] == 0) { // 벽이 아니면
					if (visited[nx][ny][0] == 0 && dis == 0) {// 벽을 안부수고 왔다면 
						q.offer(new int[] { nx, ny, next_cnt, 0 });
						visited[nx][ny][0] = 1;
					} else if (visited[nx][ny][1] == 0 && dis == 1) { // 벽을 부수고 왔다면
						q.offer(new int[] { nx, ny, next_cnt, 1 });
						visited[nx][ny][1] = 1;
					}
				} else if (map[nx][ny] == 1) { // 벽이면
					if (visited[nx][ny][0] == 0 && dis == 0) { // 벽을 안부수고 왔다면
						q.offer(new int[] { nx, ny, next_cnt, 1 });
						visited[nx][ny][1] = 1;
					}
				}
			}
		}
		System.out.println(-1);
	}
}

 

https://www.acmicpc.net/board/view/27386

이글을 많이 참고해서 풀었다.

 

 

visited를 3차원 배열로 만들어서 푸는 것이 인상적이고 약간의 dp의 접근방식과 비슷하다는 생각을 했다.