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

문제

해결방법

이 문제 딱 보자마자 단순히 BFS + 횟수 기록 문제인 줄 알았다
일단은 기본적인 구조는 bfs 방식으로 queue에 넣으면서 다음 좌표에서 탐색하는 것이었당
근데 이제 queue에 들어가야 할 정보가 x, y 좌표와 벽을 부셨는지를 체크하는 destroy, 그리고 현재까지의 경로 count 값을 넣어 주었당

왜 자꾸 틀렸을까

1. 벽 부수고 나서의 경로와 벽 부수기 전의 경로가 visited 배열 한 개로 관리되는 것으로 인해 겹쳤다
   => visited배열을 3차원으로 늘려서 벽을 부수기 전 / 부순 후 방문경로를 겹치지 않게 구현하였음
2. 정답이 잘 나오게 되었지만, 메모리 초과가 났음
   => 확인해보니 벽 부수고 난 후 부수기 전에 지나갔던 경로를 다시 가고 있었던 것을 고쳤음

코드

package com.ssafy.sejin;

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

/**
 * <pre>
 * 백준 2206. 벽 부수고 이동하기
 * BFS로 탐색하면서 queue에 다음 방문할 좌표 add
 * 벽 부수기 전 / 벽 부수고 난 후로 visited 배열을 나누어서 체크하였음
 * </pre>
 * @author 새진
 *
 */
public class BJ_2206_벽부수고이동하기_천세진 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		// 1. 사용자 입력 객체 생성
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// 2. n, m 입력
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		// 3. 그래프 저장할 map 2차원 배열, 탐색 때 사용할 visited 3차원 배열 (벽 부수기 전, 부수고 난 후 경로 체크) 선언
		int[][] map = new int[n][m];
		boolean[][][] visited = new boolean[n][m][2];
		
		// 4. 그래프 탐색할 dx, dy 배열 선언
		int[] dx = { 1, -1, 0, 0 };
		int[] dy = { 0, 0, 1, -1 };
		
		// 5. map 배열에 그래프 입력받음
		for (int i = 0; i < n; i++) {
			
			char[] ca = br.readLine().toCharArray();
			
			for (int j = 0; j < m; j++) {
				map[i][j] = ca[j] - '0';
			}
			
		}
		
		// 6. Queue 선언 후 시작점 (0, 0) push / visited 체크
		Queue<Pair> queue = new LinkedList<Pair>();
		queue.add(new Pair(0, 0, 1, 0));
		visited[0][0][0] = true;
		
		// 7. queue가 빌 동안 반복한다
		while (!queue.isEmpty()) {
			
			// 8. 제일 왼 쪽에 있는 Pair객체 꺼낸다
			Pair current = queue.poll();
//			visited[current.x][current.y][current.destroy] = true;
//			System.out.println(current);
			
			// 만약 도착점이면
			if (current.x == n - 1 && current.y == m - 1) {
				// visisted 체크하고 다시 queue 담아서 break
				visited[current.x][current.y][current.destroy] = true;
				queue.add(current);
				break;
			}
			
			// 4방향 확인
			for (int i = 0; i < 4; i++) {
				
				// 다음 좌표 값 계산
				int nextX = current.x + dx[i];
				int nextY = current.y + dy[i];
				
				// Index 범위 벗어났을 땐 continue
				if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= m) { 
					continue;
				}
				
				// 방문했으면 (visited가 true이면) continue
				if (visited[nextX][nextY][current.destroy]) continue;
				
				// 벽이 아니면
				if (map[nextX][nextY] == 0) {
					
					// 아직 벽 안 깬 상태이면 (destroy가 0이면) 1일때의 visited도 체크
					if (current.destroy == 0) {
						visited[nextX][nextY][1] = true;
					}
					
					// 해당좌표 0차원 visited 체크
					visited[nextX][nextY][current.destroy] = true;
					
					// queue에 다음 좌표 add
					queue.add(new Pair(nextX, nextY, current.count + 1, current.destroy));
					continue;
				}
				
				// 벽이면
				if (map[nextX][nextY] == 1) {
					
					// 벽뚫 썼으면 continue, 안 썼으면 destroy true로 바꾸고 queue에 add (벽 뚫고 감)
					if (current.destroy == 1) continue;
					else {
						visited[nextX][nextY][current.destroy] = true;
						queue.add(new Pair(nextX, nextY, current.count + 1, 1));
						continue;
					}
					
				}
				
			}
			
		}
		
		// visited가 양쪽 차원 다 false이면 -1 출력
		// 아니면 최소값 찾아서 해당 값 출력
		if (!visited[n - 1][m - 1][0] && !visited[n - 1][m - 1][1]) {
			System.out.println(-1);
		}
		else {
			int min = queue.poll().count;
			
			while (!queue.isEmpty()) {
				int nextCount = queue.poll().count;
				if (nextCount < min) {
					min = nextCount;
				}
			}
			
			System.out.println(min);
		}
		
		
		
	}

}

/**
 * <pre>
 * Queue에 저장하기 위한 Pair 클래스
 * (x, y) 좌표
 * 해당좌표까지의 거리 count
 * 벽 뚫었는지 안뚫었는지 저장하는 destroy
 * </pre>
 * @author 세진
 *
 */
class Pair {
	
	int x;
	int y;
	int count;
	int destroy;
	
	Pair(int x, int y, int count, int destroy) {
		this.x = x;
		this.y = y;
		this.count = count;
		this.destroy = destroy;
	}
	
	public String toString() {
		return "(" + x + ", " + y + ")" + " " + count + " " + destroy;
	}
	
}

결과 / 느낀 점

이런저런 우여곡절이 있었지만 ,, 어떻게 해결하고 나니까 뿌듯하기도 하고
다음부터 bfs만 떠올릴 게 아니라 경로를 어떻게 체크하는지도 확인을 꼭 해야겠다 !