[Algorithm] BOJ 2206번 - 벽 부수고 이동하기 (Java)

---

안녕하세요 coding-knowjam입니다.

오늘은 알고리즘 문제를 풀어보겠습니다.

문제는 백준 온라인 저지에 있는 2206번 문제입니다.

문제에 대한 내용은 아래 링크를 통해서 읽어보시길 바라겠습니다.

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

 

1. 문제 파악 및 해결 방법

1.1 목적

• (1,1) -> (N, M)까지 이동할 때의 최단거리 구하기

 

1.2 조건

1. 맵에서 0으로 된 곳은 이동 가능

2. 맵에서 1로 된 곳은 벽이 있어서 이동 불가능

3. 이동하면서 벽을 1번은 부술 수 있음

4. 이동 가능한 범위는 상하좌우로 인접한 칸으로만 이동 가능

5. (1,1)과 (N, M)은 항상 0이고, 최단거리에 포함해서 계산하며 이동거리는 칸마다 1 임

6. (N, M) 지점에 도착할 수 없는 경우는 -1을 출력

 

1.3 해결 방법

기본적으로 한 지점에서 다른 지점으로 이동할 때의 거리가 모두 동일한 경우에는 BFS알고리즘을 사용해서 해결할 수 있습니다.

위의 문제 또한 한 칸씩 이동할 때마다 거리가 1씩 증가하므로 BFS알고리즘을 통해서 해결할 수 있습니다.

그런데 벽을 만나면 한 번은 벽을 부수고 지나갈 수 있다는 추가 조건이 있습니다.

 

그렇다면 최단거리는 다음과 같이 정의할 수 있습니다.

- MIN(벽을 한번 부수고 도착한 경우, 벽을 한 번도 부수지 않고 도착한 경우)

 

일반적으로 BFS문제를 풀 때는 해당 지점을 방문했는지 여부를 체크해야 합니다.

위의 문제도 마찬가지로 방문 여부를 체크하는데 2가지의 경우로 나눠서 체크해야 합니다.

1. 벽을 부수고 해당 지점을 방문한 적이 있는가?

2. 벽을 부수지 않고 해당 지점을 방문한 적이 있는가?

 

2가지의 경우를 체크하는 부분에서 이런 생각이 드실 수도 있습니다.

"어차피 최단거리를 구하는 거면 2개의 경우 중 먼저 방문한 경우가 최단거리니까 굳이 2가지의 경우로 나눠서 구할 필요가 없지 않나??"

네 아닙니다.

 

왜냐하면 (N, M) 지점에 도착하기 위해서 중간에 벽을 한 번도 부수지 않아야 하는 경우가 존재하기 때문입니다.

아래의 그림을 보시면 (N-1, M), (N, M-1)의 벽을 부수고 도착지점으로 이동하기 위해서는 중간에 벽을 한 번도 부수지 않고 벽까지 도달해야 한다는 것을 알 수 있습니다.

만약에 먼저 온 경우를 기준으로 방문 체크를 하게 되면 아래와 같은 상황에서는 벽을 부수고 올 때 먼저 도착하는 지점이 존재하므로 (N, M)에 도착할 수 없게 됩니다.

BOJ_2206 설명 예시

 

이제까지의 내용을 플로우 차트로 정리하면 아래와 같습니다.

BOJ_2206 플로우차트

 

 

2. Java로 코드 작성

코드로 작성하면 다음과 같습니다.

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

public class BOJ_2206 {
	
	static private int n;							// 맵의 행
	static private int m;							// 맵의 열
	static private int[][] map; 					// 맵
	static private boolean[][][] visited;			// 방문여부 체크 3차원 배열
	static private int[] moveX = {-1, 1, 0 ,0};		// 상하 이동을 위한 배열
	static private int[] moveY = {0, 0, -1 ,1};		// 좌우 이동을 위한 배열

	public static void main(String[] args) throws IOException {
		
		// 콘솔로부터 입력 받기 위한 BufferedReader 객체 선언
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// N,M 입력받기
		String[] s = br.readLine().split(" ");
		
		n = Integer.parseInt(s[0]);
		m = Integer.parseInt(s[1]);
		
		map = new int[n+1][m+1];
		
		// 부수고 다니는 경우, 안 부수고 다니는 경우를 체크하기위해 3차원배열 사용
		// visited[n][m][0] = 벽을 한번도 부수지 않은경우의 방문여부
		// visited[n][m][1] = 벽을 한번 이상 부순 경우의 방문여부
		visited = new boolean[n+1][m+1][2];
		
		// 콘솔로부터 입력받아 맵 생성
		for(int i=1; i<=n; i++) {
			String[] t = br.readLine().split("");
			for(int j=1; j<=m; j++) {
				map[i][j] = Integer.parseInt(t[j-1]);
			}
		}
		
		// bfs메서드 실행 및 최단거리 출력
		System.out.println(bfs());	
	}
	
	static int bfs() {
		
		Queue<Cell> queue = new LinkedList<Cell>();
		
		// queue에 출발지점 객체 넣기
		queue.offer(new Cell(1, 1, 0, 1));
		// 출발지점 방문으로 체크
		visited[1][1][0] = true;
		
		while(!queue.isEmpty()) {
			Cell cell = queue.poll();
			
			// 도착지점에 도착 했을 경우 최단거리 출력
			if(cell.getX()==n && cell.getY()==m ) {
				return cell.getPathValue();
			}
			
			// 상하좌우 이동을 위해 for문 사용
			for(int i=0; i<4; i++) {
				int x = cell.getX() + moveX[i];
				int y = cell.getY() + moveY[i];
				
				// 맵을 벗어나는 경우의 좌표는 제외
				if(x<1 || x>n || y<1 || y>m) {
					continue;
				}else {
					//벽이 아니면서 방문하지 않은 경우 (벽을 부수고 오거나, 부수지 않은 경우 둘다 처리)
					if(map[x][y]==0 && visited[x][y][cell.getBreakWall()]==false) {
						// 최단거리 계산 및 큐에 다음 방문할 지점 넣기
						queue.offer(new Cell(x, y, cell.getBreakWall(), cell.getPathValue()+1));
						// 방문처리 (벽을 부순 경우와 부수지 않은 경우 둘다 처리)
						visited[x][y][cell.getBreakWall()] = true;
					}
					// 벽이면서 방문하지 않았고, 한번도 벽을 부수지 않은 경우
					else if(map[x][y]==1 && cell.getBreakWall()==0 && visited[x][y][1]==false) {
						// 최단거리 계산 및 큐에 다음 방문할 지점 넣기
						queue.offer(new Cell(x, y, 1, cell.getPathValue()+1));
						// 방문처리 (벽을 부순 경우)
						visited[x][y][1] = true;
					}
				}
			}
		}
		// (N,M)에 도착하지 못할 경우 -1 출력
		return -1;
	}
}

class Cell{
	
	private int x;			// 맵의 행
	private int y;			// 맵의 열
	private int breakWall;	// 안 부순 상태 : 0 , 부순 상태 : 1
	private int pathValue;	// 최단거리
	
	Cell(int x, int y, int breakWall, int pathValue) {
		this.x = x;
		this.y = y;
		this.breakWall = breakWall;
		this.pathValue = pathValue;
	}

	public int getX() {
		return x;
	}
	public int getY() {
		return y;
	}
	public int getBreakWall() {
		return breakWall;
	}
	public int getPathValue() {
		return pathValue;
	}
}

 

2.1 주요 코드 설명

조건을(visited [x][y][cell.getBreakWall()]==false) 통해서 두 가지의 경우를 동시에 체크할 수 있습니다.

1. 벽을 부순 상태에서의 방문 여부

2. 벽을 부수지 않은 상태에서의 방문 여부

 

감사합니다.

---