[백준 2206번] 벽 부수고 이동하기 - (python,java)

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

풀이

 

벽 부수고 이동하기 문제의 경우 벽을 최대 한번밖에 부술수 없기 때문에 벽을 부쉈는지 여부를 알고있는게 중요하다. 

보통 정점을 정의할때 (x,y) 로 정의하지만 벽 부순 여부를 저장하기 위해 (x,y,k) 라고 정의하고 푼다.

 

 

코드

package baekjoon;
import java.util.Scanner;
import java.util.*;

class Pair {
    int x, y, z;
    Pair(int x, int y, int z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }
}
public class Main {
    public static int[] dx = {1, -1, 0, 0};
    public static int[] dy = {0, 0, 1, -1};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine();  // 다음 입력을 위해 버퍼에 개행 제거
        int[][] a = new int[n][m]; // 격자 map 정의
        int[][][] d = new int[n][m][2]; // 거리 저장 배열

        for (int i=0; i<n; i++) {
            String s = sc.nextLine();
            for (int j=0; j<m; j++) {
                a[i][j] = s.charAt(j) - '0'; // 문자를 숫자로 변환
            }
        }

        d[0][0][0] = 1; // 시작 위치 거리 1
        Queue<Pair> q = new LinkedList<Pair>();
        q.offer(new Pair(0, 0, 0));

        while (!q.isEmpty()) { // bfs
            Pair p = q.remove();
            int x = p.x;
            int y = p.y;
            int z = p.z;

            for (int k=0; k<4; k++) {
                int nx = x+dx[k];
                int ny = y+dy[k];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (a[nx][ny] == 0 && d[nx][ny][z] == 0) {  // ? -> 빈칸 
                    d[nx][ny][z] = d[x][y][z] + 1;
                    q.offer(new Pair(nx, ny, z));
                }
                if (z == 0 && a[nx][ny] == 1 && d[nx][ny][z+1] == 0) { // ? -> 벽
                    d[nx][ny][z+1] = d[x][y][z] + 1;
                    q.offer(new Pair(nx, ny, z+1));
                }
            }
        }
        if (d[n-1][m-1][0] != 0 && d[n-1][m-1][1] != 0) {
            System.out.println(Math.min(d[n-1][m-1][0], d[n-1][m-1][1]));
        } else if (d[n-1][m-1][0] != 0) {
            System.out.println(d[n-1][m-1][0]);
        } else if (d[n-1][m-1][1] != 0) {
            System.out.println(d[n-1][m-1][1]);
        } else {
            System.out.println(-1);
        }
    }
}