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

백준 2206: 벽 부수고 이동하기

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

풀이

• 기본적으로 bfs로 풀이
• 벽을 부수는 경우와 안 부수는 경우가 있다.
• 방문 처리를 벽을 한번 부순 경우 / 부수지 않은 경우로 나누어서 진행
• 가장 빠르게 목적지에 도달하면 종료

package algorithm2024.feb.day19;

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

public class BOJ_2206_벽부수고이동하기 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();

	//방향벡터 dy, dx 상 우 하 좌 순
	static int[] dy = {-1, 0, 1, 0};
	static int[] dx = {0, 1, 0, -1};

	//행의 개수 N, 열의 개수 M, N*M 맵
	static int N, M, map[][];

	//방문처리 boolean 배열, N*M*2
	static boolean[][][] v;

	//정답을 담을 변수
	static int ans = -1;

	//bfs를 위한 노드 클래스, 위치 좌표 y,x 와 움직인 거리 l, 벽을 부순 적이 있는지 여부를 나타내는 isBreak 변수를 두었다.
	static class Node {
		int y, x, l;
		boolean isBreak;

		public Node(int y, int x, int l, boolean isBreak) {
			this.y = y;
			this.x = x;
			this.l = l;
			this.isBreak = isBreak;
		}

	}

	//Node가 올바른 자리에 있는지 확인하는 함수, 범위를 벗어나면 false 리턴
	static boolean isValid(Node node) {
		int y = node.y;
		int x = node.x;

		if (y < 0 || x < 0 || y >= N || x >= M)
			return false;
		return true;
	}

	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new int[N][M];
		v = new boolean[N][M][2];

		for (int i = 0; i < N; i++) {
			String[] s = br.readLine().split("");
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(s[j]);
			}
		}

		/*여기까지 입력*/

		//bfs를 위해 큐 사용
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(0, 0, 1, false));
		v[0][0][0] = true;

		/*bfs*/
		while (!q.isEmpty()) {

			Node cur = q.poll();
			int y = cur.y;
			int x = cur.x;
			int l = cur.l;
			/*목적지에 도착하면 종료*/
			if (y == N - 1 && x == M - 1) {
				ans = l;
				break;
			}
			boolean isBreak = cur.isBreak;
			/*방향벡터 돌려보면서 확인*/
			for (int d = 0; d < 4; d++) {
				int ny = y + dy[d];
				int nx = x + dx[d];
				Node next = new Node(ny, nx, l + 1, isBreak);
				/*범위를 벗어나면 continue*/
				if (!isValid(next))
					continue;
				/*다음 경로가 벽이고 아직 벽을 부순 적이 없다면*/
				if (map[ny][nx] == 1 && !isBreak && !v[ny][nx][1]) {
					v[ny][nx][1] = true;
					next.isBreak = true;
					q.offer(next);
					/*다음 목적지가 벽이 아님*/
				} else if (map[ny][nx] == 0) {
					/*벽으 부순 적이 있는데 이미 벽을 부수고 해당 목적지로 간 적이 있으면 continue*/
					if (isBreak) {
						if (v[ny][nx][1])
							continue;
						v[ny][nx][1] = true;
						/*벽을 부순 적이 없지만 해당 목적지에 이미 간 적이 있으면 continue*/
					} else {
						if (v[ny][nx][0])
							continue;
						v[ny][nx][0] = true;
					}
					q.offer(next);
				}
			}
		}
		System.out.println(ans);

	}
}

---

Issue

• 처음에 DFS로 풀었는데 시간 초과 떴음.
• 최단 경로를 찾는 문제는 bfs가 훨씬 빠름!