[BOJ/Java] 2206. 벽 부수고 이동하기

[BOJ/Java] 2206. 벽 부수고 이동하기

2206번: 벽 부수고 이동하기

---

문제 해석

이 문제에서는 2차원 배열로 표현된 그리드에서 '0'은 이동 가능한 공간을, '1'은 벽을 나타낸다. 목표는 시작 지점 (0, 0)에서 출발하여 (N-1, M-1) 지점에 도착하는 최단 경로를 찾는 것이다. 중요한 조건은 벽을 한 번만 부수고 이동할 수 있다는 점이다. 이 문제는 BFS(너비 우선 탐색)를 사용하여 해결할 수 있다.

풀이 과정

제출된 코드는 BFS를 사용하여 최단 경로를 찾는다. 특이한 점은 3차원 배열을 사용하여 각 노드의 방문 상태를 관리한다는 것이다. 여기서 세 번째 차원은 벽을 부순 상태(0 또는 1)를 나타낸다.

 

• graph: 2차원 그리드를 나타내며, 각 셀은 '0' 또는 '1'이다.
• visited: 3차원 배열로, (x, y) 위치를 벽을 부수고 방문했는지, 안 부수고 방문했는지를 기록한다.
• bfs 함수: 시작점에서 BFS를 시작하여 각 점을 방문하면서 최단 경로를 계산한다.

 

Point 클래스는 위치 (x, y), 현재까지의 이동 횟수 (cnt), 그리고 벽을 부순 상태(v)를 저장한다.

코드

package edu.ssafy.im.BOJ.Gold.G3.No2206;

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

public class Main {
	public static void main(String[] args) throws IOException {
		new Main().sol();
	}

	private int[][] graph; // 그리드를 저장할 2차원 배열
	private boolean[][][] visited; // 방문 상태를 저장할 3차원 배열
	private int n; // 그리드의 세로 길이
	private int m; // 그리드의 가로 길이
	private int ans; // 결과를 저장할 변수
	private static final int[][] direction = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } }; // 이동 가능한 4가지 방향

	private void sol() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		graph = new int[n][m];
		for (int i = 0; i < graph.length; i++) {
			String row = br.readLine();
			for (int j = 0; j < graph[0].length; j++) {
				graph[i][j] = row.charAt(j) - '0'; // 문자를 숫자로 변환하여 저장
			}
		}

		int ans = bfs(); // BFS 실행

		sb.append(ans); // 결과를 StringBuilder에 추가
		bw.write(sb.toString()); // 결과 출력
		bw.flush();
		bw.close();
	}

	private int bfs() {
		Queue<Point> queue = new ArrayDeque<>(); // BFS를 위한 큐
		boolean[][][] visited = new boolean[n][m][2]; // 방문 상태 배열
		queue.offer(new Point(0, 0, 1, 0)); // 시작점
		visited[0][0][0] = true; // 시작점 방문 표시

		while (!queue.isEmpty()) {
			Point p = queue.poll();

			if (p.x == n - 1 && p.y == m - 1) // 도착점에 도달한 경우
				return p.cnt;

			for (int d = 0; d < direction.length; d++) {
				int nx = p.x + direction[d][0];
				int ny = p.y + direction[d][1];

				if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 그리드 범위를 벗어나는 경우

				if (visited[nx][ny][p.v]) continue; // 이미 방문한 경우

				if (p.v == 1 && graph[nx][ny] == 1) continue; // 이미 벽을 부순 상태에서 벽을 만난 경우

				if (graph[nx][ny] == 0) {
					visited[nx][ny][p.v] = true; // 방문 표시
					queue.offer(new Point(nx, ny, p.cnt + 1, p.v)); // 큐에 추가
				} else if (graph[nx][ny] == 1) {
					visited[nx][ny][1] = true; // 벽을 부수고 방문 표시
					queue.offer(new Point(nx, ny, p.cnt + 1, 1)); // 큐에 추가
				}
			}
		}

		return -1; // 도착점에 도달할 수 없는 경우
	}

	class Point {
		int x, y, cnt, v;

		public Point(int x, int y, int cnt, int v) {
			super();
			this.x = x;
			this.y = y;
			this.cnt = cnt;
			this.v = v;
		}

	}
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(N*M)이다. BFS는 각 노드를 한 번씩만 방문하며, 각 노드에 대해 4개의 이웃을 확인한다.

느낀점

이 문제를 통해 BFS를 사용하여 특정 조건 하에서 최단 경로를 찾는 방법을 배울 수 있었다. 3차원 방문 배열을 사용하여 각 상태(벽을 부순 상태와 부수지 않은 상태)를 관리하는 접근 방식은 다양한 문제에 적용 가능할 것이다. 또한, 문제 해결 과정에서 큐와 조건문의 사용이 매우 중요함을 인지하게 되었다.