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

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

2206번: 벽 부수고 이동하기

풀이

기본적인 bfs 에 간단한 조건만 추가하면 해결 할 수 있는 문제이다.

 

시작점 (0, 0) 에서 도착점 (N, M) 으로 갈 수 있는 최단 거리를 구하면 된다.

Position 클래스를 생성할 때 x 좌표, y 좌표, 거리, 벽을 부셨는지 여부를 함께 저장할 수 있도록 선언한다.

public static class Position {
    int x;        // x 좌표
    int y;        // y 좌표
    int cnt;      // 거리
    int isBroken; // 벽을 부셨는지 여부
		
    public Position (int x, int y, int cnt, int isBroken) {
        this.x = x;
        this.y = y;
        this.cnt = cnt;
        this.isBroken = isBroken;
    }
}

상하좌우 한 칸씩 이동할 때 다음 칸이 벽일 경우, 벽이 아닐 경우 두 가지로 나누어서 조건을 만들면 된다.

 

1. 다음 칸이 벽일 경우

  1) 벽을 부셨는지 여부 판단 (now.isBroken)

  2) 해당 벽을 이전에 부수고 방문한 적이 있는지 판단 (visited[dx][dy][1])

 

2. 다음 칸이 벽이 아닐 경우

  1) 벽을 부셨는지 여부에 따라 다음 칸을 방문했는지 판단 (visited[dx][dy][0] or visited[dx][dy][1])

// map 범위를 벗어나거나 벽을 이미 한 번 부셨을 경우
if (dx < 0 || dx >= N || dy < 0 || dy >= M || visited[dx][dy][now.isBroken]) continue;
				
if (map[dx][dy] == 0) { // 다음 칸이 벽이 아닌 경우
    visited[dx][dy][now.isBroken] = true;
    q.add(new Position(dx, dy, now.cnt+1, now.isBroken));
} else if (map[dx][dy] == 1 && now.isBroken == 0) { // 다음 칸이 벽이고 아직 벽을 부수지 않은 경우
    visited[dx][dy][1] = true;
    q.add(new Position(dx, dy, now.cnt+1, 1));
}

위 과정을 판단하기 위해선 visited 배열을 3차원 배열로 생성해주면 된다.

visited[x][y][벽을 부셨는지 여부]

 

<최종코드>

import java.io.*;
import java.util.*;
 
public class Main {
    static int[] x = {-1, 0, 1, 0};
    static int[] y = {0, -1, 0, 1};
	
    public static class Position {
        int x;        // x 좌표
        int y;        // y 좌표
        int cnt;      // 거리
        int isBroken; // 벽을 부셨는지 여부
		
        public Position (int x, int y, int cnt, int isBroken) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
            this.isBroken = isBroken;
        }
    }
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
		
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
		
        int[][] map = new int[N][M];
        boolean[][][] visited = new boolean[N][M][2];
		
        for (int i=0; i<N; i++) {
            String str = br.readLine();
            for (int j=0; j<M; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }
		
        Queue<Position> q = new LinkedList<>();
        q.add(new Position(0, 0, 1, 0));
        visited[0][0][0] = true;
		
        while (!q.isEmpty()) {
            Position now = q.poll();
			
            // 먼저 도착지에 도달한 경우 dfs 종료
            if (now.x == N-1 && now.y == M-1) {
                System.out.println(now.cnt);
                return;
            }
			
            for (int i=0; i<4; i++) {
                int dx = now.x + x[i];
                int dy = now.y + y[i];
				
                // map 범위를 벗어나거나 벽을 이미 한 번 부셨을 경우
                if (dx < 0 || dx >= N || dy < 0 || dy >= M || visited[dx][dy][now.isBroken]) continue;
				
                if (map[dx][dy] == 0) { // 다음 칸이 벽이 아닌 경우
                    visited[dx][dy][now.isBroken] = true;
                    q.add(new Position(dx, dy, now.cnt+1, now.isBroken));
                } else if (map[dx][dy] == 1 && now.isBroken == 0) { // 다음 칸이 벽이고 아직 벽을 부수지 않은 경우
                    visited[dx][dy][1] = true;
                    q.add(new Position(dx, dy, now.cnt+1, 1));
                }
            }
        }
        
        // 도착지에 도달하지 못 할 경우
        System.out.println(-1);
    }
}