[JAVA]BOJ(백준) - 벽 부수고 이동하기 - 2206

문제 내용

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

2206번: 벽 부수고 이동하기

최단거리를 찾는 BFS에 벽을 한번 부수고 지나갈 수 있는 조건이 추가된 문제이다.

 

---

문제 접근 방법

 

• 첫번째로 생각한 방법.

BFS를 돌리는데 벽의 존재 여부에 따라 경우의수가 나뉜다는 생각을해서 벽을 처음 만날때마다 백트래킹으로 옳은길인지 아닌지를 하나씩 판단해야겠다 라는 생각을 했다. 그리고 문제에서 입력으로 주어진 2차원 배열 map의 요소값을 1씩 증가시키면서 map[N-1][M-1]+1 의 값을 구하려고 했는데.... 결과적으로 삽질을 몇시간동안 했다.

 

내가 생각한 방법의 문제을 생각해보면

 

1. 입력 받은 map의 요소값을 경우의수마다 계속 건드리기 때문에 원하는 값이 안나올수가 있다.

2. 두뇌가 슈퍼컴이 아니라면 애초에 BFS와 DFS방식을 같이 쓰지 않는게 좋다.

3. 상하좌우 4방향을 탐색하는데 방문했던 곳은 탐색하지 않는게 좋다.(방문배열이 있는게 좋다.)

4. 만약 입력받은 map의 값을 건드리고 싶을땐 값이 같은 배열을 복사해서 사용하던지 크기가 같은 배열을 만들어 초기화시키고 사용하는게 좋다.

5. map은 분기문에서만 사용하는게 베스트다.

 

첫번째로 생각한 방법에 대해 다시 생각해보고 내린 결론이다.

 

• 두번째 방법

두번째로는 'https://pangtrue.tistory.com/259 -팡트루야' 님의 블로그에서 도움을 얻었다.

 

두번째 방법을 간단하게 정리해 보면

 

1. 큐에는 (x, y, 현재까지 거리(dis), 현재 벽을 부숨 여부(wall)) 를 알려주는 객체를 넣어준다.

2. 큐에서 뺀 객체의 인덱스가 N-1,M-1의 위치라면 그 위치의 dis를 출력하고 함수를 끝낸다.

3. 상하좌우 4방향 탐색시 방문배열을 통해 방문안한 곳만 골라 간다.

4. 벽의 존재여부에 따라 벽을 부수고갈지 아니면 끝낼지에 대한 판단을 해준다.

5. 부수고 갈지 아닌지에 대한 판단은 큐에서 뺀 객체를 기준으로 한다.

6. 부수고 간다면 큐에 그에 맞는 객체를 넣어주고, 2~6반복. 

 

그리고 방문배열은 방문했던 곳의 변수 wall의 여부에 따라 판단할 것이기 때문에 boolean대신 int 배열을 사용한다.

wall의 경우 벽을 부쉈던 객체는 1, 부수지 않은 객체는 0으로 표현한다.

 

이해가 안간다면 코드에 주석을 달아놨으니 분석해보자.

 

---

 

풀이

import ...

class BOJ2206Point{ // 큐에넣을 클래스
	int pointX, pointY; // 현재 x,y 인덱스 값
	int dis; // 이동거리
	int wall; // 벽을 안부순 놈은 0, 부순 놈은 1로 표현
	public BOJ2206Point(int x, int y, int dis, int wall) {
		this.pointX = x;
		this.pointY = y;
		this.dis = dis;
		this.wall = wall;
	}
}

public class BOJ_2206 {
	static int N, M;
	static int[] x = {0, 0, -1, 1}; // 상하
	static int[] y = {-1, 1, 0, 0}; // 좌우
	static int[][] map, check;
	
	public void bfs(int v1, int v2) {
		Queue<BOJ2206Point> queue = new LinkedList<BOJ2206Point>();
		queue.add(new BOJ2206Point(v1,v2,1,0)); //현재거리를 1로 하는 이유는 시작점도 포함해서. 
		
		while(!queue.isEmpty()) {
			BOJ2206Point point = queue.poll();
			int nowX = point.pointX; // 현재 인덱스 x
			int nowY = point.pointY; // 현재 인덱스 y
			int nowDis = point.dis; // 현재 거리
			int nowWall = point.wall; // 현재 벽부숨 여부
			
			if(nowX == N-1 && nowY == M-1) { //뽑은 객체가 인덱스의 끝이라면 거리 출력후 함수종료.
				System.out.println(nowDis);
				return;
			}
			
			for(int i=0; i<4; i++) {// 4방향 탐색
				int dx = nowX + x[i];
				int dy = nowY + y[i];
				
				if(dx>=0 && dy>=0 && dx<N && dy<M) {
					if(check[dx][dy]>nowWall){//방문안한 곳은 nowWall보다 무조건 큼.(방문안한 곳만 가기)
						if(map[dx][dy]==0) {//벽이 없을때
							queue.add(new BOJ2206Point(dx, dy, nowDis+1, nowWall));
							check[dx][dy] = nowWall; //방문 체크
						} else if(map[dx][dy]==1 && nowWall==0) {//벽이 있을때
							queue.add(new BOJ2206Point(dx, dy, nowDis+1, nowWall+1));
							check[dx][dy] = nowWall+1; //방문 체크
						}
					}//if(방문안한 곳 방문하겠다는 분기문)
				}//if(다음인덱스값 범위확인 분기문)
			}//for
		}//while
		
		System.out.println(-1); //BFS 다돌면 N-1,M-1까지 못간거임. 그래서 -1 출력.
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		if(N-1==0 && M-1==0) {//시작지점과 도착지점 같으면 걍 1출력 후 끝냄.
			System.out.println(1);
			System.exit(0);
		}
		
		map = new int[N][M]; 
		check = new int[N][M]; //방문배열
		
		String temp = null;
		for(int i=0; i<N; i++) {
			temp = br.readLine();
			for(int j=0; j<M; j++) {
				map[i][j] = Integer.parseInt(temp.substring(j, j+1));
				check[i][j] = Integer.MAX_VALUE; //방문배열 초기화
			}
		}
		
		new BOJ_2206().bfs(0,0); // 시작위치를 인수로.
	}
}

 

---

마치며

삽질하지 말고 내가 계속 필요로 하는 객체는 반드시 만들고 갖고 다녀하는 것,

입력받은 배열들은 확실한거 아님 건들지말고 필요한경우 의도에 맞게 다시 만들어서 쓰자는 것,

BFS와 DFS를 같이쓰지 말자를 명심하자!