[백준] 벽 부수고 이동하기 (java)

2020-03-12

벽 부수고 이동하기 (백준> Dfs_Bfs)

문제설명

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

예제 입력 1 복사

예제 출력 1 복사

예제 입력 2 복사

예제 출력 2 복사

-1

풀이

package Dfs_Bfs;

import java.util.*;

public class beak_벽부수고이동하기 {

	static class Pos{
		int x; int y; int c; int d;
		
		Pos(int x, int y, int c, int d){
			this.x = x;
			this.y = y;
			this.c = c;
			this.d = d;
		}
	}

	static int answer;
	static int dx[] = {0,0,1,-1};
	static int dy[] = {1,-1,0,0};
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		sc.nextLine();
		
		int arr[][] = new int[n][m];
		//방문의 최소값을 visit할때마다 담을거니까, 방문의 값을 전부 max로 만든다
		int visited[][] = new int[n][m];
		
		
		for(int i=0;i<n; i++) {
			String s = sc.nextLine();
			for(int j=0; j<m; j++) {
				arr[i][j] = Integer.parseInt(String.valueOf(s.charAt(j)));
				visited[i][j] = Integer.MAX_VALUE;
			}
		}
		
		
		answer = Integer.MAX_VALUE; // 최대값으로 초기화 해놓은 후, n-1 m-1 만날때 마다 min 비교
		
		//bfs
		Queue<Pos> q = new LinkedList<>();
		
		q.add(new Pos(0,0,1,0)); //시작 위치, 이동거리는 1부터, 아직 벽을 안만났으니 0
		
		while(!q.isEmpty()) {
			Pos p = q.poll();
			
			int x = p.x; int y = p.y; int c = p.c;
			
//			System.out.println(x + " " + y + " " + c);
			
			if(x == n-1 && y == m-1) { //도달하지않으면 answer 바뀌지않음
				answer = p.c;
				break;
			}
			
			
			for(int i=0; i<4; i++) {
				int nx = x+dx[i];
				int ny = y+dy[i];
				
				//visited[x][y] = 무한대, 0, 1 만 존재할 수 있고, p.d = 0,1 만 가능
				if(nx>=0 && nx<n && ny>=0 && ny<m) {
//					System.out.println(nx +" " + ny +" " +visited[nx][ny] + " " + p.d);
					
					if(visited[nx][ny] > p.d) { //현재의 drill이 visited보다 작을때만 수행한다.
						
						if(arr[nx][ny] == 0) {//벽이 아니라면
							q.add(new Pos(nx,ny,c+1,p.d));
							visited[nx][ny] = p.d; // 0이면 갈 수 있는거고, 아니면 밑의 else를 타야하기때문에
						}
						else {//벽일 때 ->d가 0일때만 들어오기때문에 p가 1초과일 수는 없다!!!
							if(p.d == 0) {
								q.add(new Pos(nx,ny,c+1, p.d+1)); //d+1증가
								visited[nx][ny] = p.d+1;
							}
						}
					}
				}
			}//for
			
		}//while
		
		if(answer == Integer.MAX_VALUE)
			System.out.println(-1);
		else
			System.out.println(answer);
		
	}
}

후기 (1h 30min)

전에 풀었던 연구소처럼 모든 경우의 수를 다 따졌더니 맞긴 맞는데, 시간초과가 떴다…

package Dfs_Bfs;

import java.util.*;

public class beak_벽부수고이동하기 {

	static class Pos{
		int x; int y; int c;
		Pos(int x, int y){
			this.x = x;
			this.y = y;
		}
		
		Pos(int x, int y, int c){
			this.x = x;
			this.y = y;
			this.c = c;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		sc.nextLine();
		
		Queue<Pos> one = new LinkedList<>();
		ArrayList<Integer> answer = new ArrayList<>();
		
		int arr[][] = new int[n][m];
		for(int i=0;i<n; i++) {
			String s = sc.nextLine();
			for(int j=0; j<m; j++) {
				arr[i][j] = Integer.parseInt(String.valueOf(s.charAt(j)));
				if(arr[i][j] == 1)
					one.add(new Pos(i,j));
			}
		}
		
		int nn = n-1; int mm = m-1; // ... mm = m = 1; ....?ㅋㅎ
		
		int size = one.size();
		
		//1을 0번 부수는거부터 one개 부수는거까지
		for(int k=0; k<=size; k++) {
			int copy[][] = new int[n][m];
			
			for(int i=0;i<n;i++) {
				for(int j=0; j<m; j++)
					copy[i][j] = arr[i][j];
			}
			
			if(k != size) {
				Pos p = one.poll();
				copy[p.x][p.y] = 0; // 벽 제거
			}
			
			
			Queue<Pos> q = new LinkedList<>();
			q.add(new Pos(0,0,1));
			
			int count = 0;
			boolean chk = false; // 1일때만 -1인게 아니고 nn과 mm에 도달하지않는이상 다 -1
			//bfs
			while(!q.isEmpty()) {
				Pos p = q.poll();
				
				int x = p.x;
				int y = p.y;
				
				count = p.c;
				
				if(x==nn && y==mm) {
					chk = true;
					break;
				}
				
				int dx[] = {0,0,1,-1};
				int dy[] = {1,-1,0,0};
				
				for(int l=0; l<4; l++) {
					int xx = x + dx[l];
					int yy = y + dy[l];
					
					if(xx>=0 && xx<n && yy>=0 && yy<m && copy[xx][yy] == 0) {
						q.add(new Pos(xx, yy, p.c+1));
						copy[xx][yy] = 1;
					}
				}//for
				
			}//while
			
			if(chk == false)
				answer.add(-1);
			else
				answer.add(count);
			
		}
		
		int min = 10000;	int cnt = 0;
		for(int i=0; i<answer.size(); i++) {
			if(answer.get(i) == -1)
				cnt++;
			else
				min = Math.min(min, answer.get(i));		
		}
		
		if(cnt == answer.size())
			System.out.println(-1);
		else
			System.out.println(min);

	}
}

전부다 확인하지않고 drill 이라는 새로운 변수를 통해서 왔다갔다 할 수 있다는 점!

또한, min 값을 구할때, 초기화를 int min = Integer.MAX_VALUE;를 통해 무한대로 초기화 할 수 있다는 점을 배웠다!

if(visited[nx][ny] > p.d) { //현재의 drill이 visited보다 작을때만 수행한다.

어렴풋이는 이해 되는데 누가 명쾌하게 이해시켜주세오….!ㅠㅜ

아!!!!! 이해함!!! 방문하면 무조건 0아니면 1이 되니까

visited()()는 0 아니면 1이고

1) 1>0 이면 방문했던 곳이 1번 뚫었고, 나는 0이니까 갈 수있어서 true

2) 1>1 이면 방문했던 곳이 1번 뚫려있고, 나도 뚫려있으니까 방문불가라 false

3) 0>0 이면 방문했던 곳이고, 내가 다시 방문하는거라 무한루프 돌지않게 false

4) 0>1 이면 방문했던 곳이고, 내가 뚫을수도 없을 뿐더러 방문했기때문에 false

5) visited가 무한대이고 현재 드릴이 0이거나 1이거나면 방문안했던 곳이니까 무조건 방문 가능 true
참고링크

https://kim6394.tistory.com/201

 [백준] 문자열 (java) Greedy [백준] 스티커 (java) Dynamic_programming 