-
[백준/JAVA] 2206 벽 부수고 이동하기ETC/Algorithm 2023. 5. 27. 01:45
문제
문제 인식
변수 상황
N * M의 행렬로 표현되는 맵이 있고, 0은 이동가능 1은 이동 불가능한 벽으로 표현된다.
이동은 (1,1)에서 시작하며, 도착점은 (N,M)으로 고정되어있다.
하지만 변수 상황이 주어지는데
간단히 기존 BFS 문제에서 벽을 한번은 통과할 수 있다는 것이다.그렇다면 다른 BFS 문제와 형태는 같지만 벽을 한 번 통과 가능하다는 점을 어떻게 구현할 것인가가 문제의 핵심으로 인식했다.
실패한 문제 해결
처음 생각한 방법은, BFS를 재귀를 통해 다시 불러오는 방식을 생각하였다.
첫 시작은 벽 부신 값을 false로 갖고 시작
재귀를 통해 한번 벽을 부셨다면 true 값을 주고 반복하여 진행하였다.여기서 문제가 발생하는데,
벽을 한번 부신 경우가 그냥 정상적인 길로 가도 거리 값은 동일한데 먼저 진행된 경우였다.
이 경우 visited 값이 미리 true로 입력되어, 벽을 한 번 부실 수 있는 기회를 날리고 시작하게 되는 것이다.이 경우에서 이후 풀이인 visited를 3차원 배열로 구현하여 한번 더 진행하였다면 성공하였겠지만,
새로운 풀이로 다시 진행하였다.
풀이
주의점
도중에 한 개의 벽을 부신경우 더 이상 부실 수 없다.
당연하게도 벽은 한번 밖에 부시질 못한다. 그럼 true, false 또는 0,1로 표현 가능하다.
벽을 부시고 이동한 경우와, 벽을 안부시고 이동한 경우의 거리값이 동일 할 수 있다.
위의 실패한 해결의 내용과 동일하다. 이를 해결하기 위해 visited를 3차원 배열로 구현하여 해결가능하다.
map을 입력 받을 때, char 값으로 입력받는다.
여태 문제 풀면서 고려 해왔지만,
String line = br.readLine();
으로 값을 입력 받아 charAt() 으로 값을 char 형으로 받아오므로 0,1이 정수 형이 아니다.
꼭 48 값을 빼주자
코드
코드 해석
- BFS 알고리즘을 사용하였다.
- 다음 이동할 곳이 그냥 길인 경우 그리고, 다음 이동할 곳이 벽인데 벽을 부지 않은 경우를 고려한 조건문을 설정해서 해결하였다.
- 다른 BFS 문제와 다르게, map 자체의 값의 변화를 주지 않고 해결하였다. 자체 Pos 클래스에 x,y,이동한 거리, 벽을 부신 여부를 저장한다.
- 시작하는 칸과 끝나는 칸을 포함해서 센다. 시작부터 cnt는 1로 시작한다.
- 큐에서 값을 꺼내오자마자 좌표값이 도착점이면 현재 까지의 이동거리 값(cnt)를 리턴한다.
- 큐에 비어있게 되었을 때까지 도착지점에 도달하지 못한 경우는 불가능한 경우이다. -1을 리턴하도록 지정해둔다.
제출 코드
import java.io.*; import java.util.*; class Main { static int N, M; static Queue<Pos> q = new LinkedList<>(); static boolean[][][] visited; static int[][] map; static int[] opsX = {1, -1, 0 ,0}; static int[] opsY = {0, 0, 1, -1}; static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static StringTokenizer st; static class Pos { int x; int y; int cnt; int hit; public Pos(int x, int y, int cnt, int hit) { this.x = x; this.y = y; this.cnt = cnt; this.hit = hit; } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); st = new StringTokenizer(br.readLine(), " "); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); map = new int[N][M]; visited = new boolean[N][M][2]; for (int i = 0; i < N; i++) { String line = br.readLine(); for (int j = 0; j < line.length(); j++) { map[i][j] = line.charAt(j) - 48; } } bw.write(String.valueOf(bfs(new Pos(0,0,1,0)))); bw.flush(); } public static int bfs(Pos node) { q.offer(new Pos(node.x, node.y, node.cnt, node.hit)); visited[node.x][node.y][node.hit] = true; while (!q.isEmpty()) { Pos now = q.poll(); if (now.x == N-1 && now.y == M-1) { return now.cnt; } for (int i = 0; i < 4; i++) { int newX = now.x + opsX[i]; int newY = now.y + opsY[i]; if (checkRange(newX, newY)) { // 다음 이동할 곳이 그냥 길인 경우 if (map[newX][newY] == 0 && !visited[newX][newY][now.hit]) { q.offer(new Pos(newX, newY, now.cnt+1, now.hit)); visited[newX][newY][now.hit] = true; } // 다음 이동할 곳이 벽인데 벽을 부지 않은 경우 if (now.hit == 0 && map[newX][newY] == 1 && !visited[newX][newY][now.hit]) { q.offer(new Pos(newX, newY, now.cnt+1, now.hit+1)); visited[newX][newY][now.hit] = true; } } } } return -1; } public static boolean checkRange(int x, int y) { return -1 < x && x < N && -1 < y && y < M; } }