쌉쌀한 무화과의 개발로그

[문제]

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을 출력한다.

[예제]

>문제 풀이

 기존에 풀었던 BFS 방식으로는 풀 수 없는 문제였습니다.

"벽을 부술 수 있다"가 이 문제의 중요한 조건으로, 이 조건을 담을 변수가 필요하다고 생각했지만,, 어떻게???

고민하다가 다른 분들의 코드를 봤는데, 처음에는 봐도 잘 이해가 안되었어요.

(저도 나중에 확인한 글이지만, 해당 문제의 질문검색에서 www.acmicpc.net/board/view/27386 글을 먼저 읽어보세요. 이 링크의 글을 먼저 읽어봤더라면 좀 더 깊게 고민할 수 있지 않았을까.. 생각되네요.)

 이 문제를 풀기 위해서는 기존의 생각에서 확장을 해야합니다.

이동할 때, 현재 이동해온 경로에서 벽을 부순적이 있는지 없는지 확인을 하고 이동해야하죠.

부순 적이 있다면 mat[][]==0인 경로로만 갈 수 있고, 부순 적이 없다면 지금 벽을 부수고 이동할 수 도 있으니까요.

1) 벽 && 벽을 부순적 없음 && 방문한적 없음

>>벽을 부수고, 방문확인하고, 카운팅

2) 벽이 아님 && 방문한적 없음

>>방문확인하고, 카운팅

현재 위치를 class Point(int x, int y, int wall, int cnt) 클래스로 나타냈습니다.

int x, y는 행렬에서 좌표 (x, y)를 의미하고, wall은 벽을 부순적 있으면 1 없으면 0, cnt는 현재까지 이동해온 카운팅

(주의할 점은 시작 위치와 마지막 위치도 카운팅 한다는 점)

boolean visited[][][] 3차원 배열을 이용했는데, visited[x][y][0]은 벽을 부순적 없으면서 (x, y)위치에 방문한적 있는지 체크, visited[x][y][1]은 벽을 부순적이 있으면서 (x, y)위치에 방문한적 있는지 체크

(제가 글을 쓰고, 생각을 하면서도 말이 참 어렵다고 느껴지네요... 어쩌면 코드를 한 번 읽고 오시는게 더 이해가 잘 될 것 같습니다.)

* int 를 쓰지 않고, boolean을 쓴 이유는 말이 어렵기 때문에 읽을때 최대한 헷갈리지 않게 하기 위해 해석의 의미가 명확한 boolean을 썼습니다.

+) 11%대 쯤에서 틀리시는 분들은 if(현재x위치==N&&현재y위치==M) 일때 출력 및 종료해주시는 코드를 빼먹지는 않았는지 확인해보시길 바랍니다.

+) 다음의 예제도 확인해보세요

1 1

1

answer: 1

※저는 아래 링크의 블로그를 참고하여 공부했습니다.

참고한 블로그: velog.io/@leeinae/Algorithm-%EB%B0%B1%EC%A4%802206-%EB%B2%BD-%EB%B6%80%EC%88%98%EA%B3%A0-%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0-java

>전체 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int N, M;
	static int mat[][];
	static boolean visited[][][];
	
	public static void main(String [] args) {
		String str;
		Scanner scan= new Scanner(System.in);
		
		N= scan.nextInt();
		M= scan.nextInt();
		visited= new boolean[N][M][2]; //visited[][][0]:안부숨, 1부숨
		mat= new int[N][M];
		
		for(int i=0; i<N; i++) {
			str= scan.next();
			for(int j=0; j<M; j++) {
				mat[i][j]= Integer.parseInt(str.charAt(j)+"");
			}
		}
		
		bfs(0,0);
	}
	
	public static void bfs(int x, int y) {
		int nx, ny, wall, cnt=1;
		int dx[]= {-1, 0, 0, 1};
		int dy[]= {0, -1, 1, 0};
		Point p;
		Queue<Point> que= new LinkedList<Point>();
		
		que.offer(new Point(x, y, 0, 1));
		
		visited[x][y][0]= true;
		visited[x][y][1]= true;
		
		while(!que.isEmpty()) {
			p= que.poll();
			
			if(p.x==N-1&&p.y==M-1) {
				System.out.println(p.cnt);
				return;
			}
			
			for(int i=0; i<4; i++) {
				nx= p.x+dx[i];
				ny= p.y+dy[i];
				wall= p.wall;
				cnt= p.cnt;
				
				if(0<=nx&&nx<N&&0<=ny&&ny<M) {
					if(mat[nx][ny]==1&&wall==0&&visited[nx][ny][1]==false) { //벽&벽을 부순적 없음
						visited[nx][ny][1]=true;
						que.offer(new Point(nx, ny, 1, cnt+1));
					}else if(mat[nx][ny]==0&&!visited[nx][ny][wall]){ //이동 가능(벽없음)
						visited[nx][ny][wall]=true;
						que.offer(new Point(nx, ny, wall, cnt+1));
					}
				}
				
			}
		}//while
		
		System.out.println("-1");
	}//bfs
	
	
	static class Point {
		int x, y, wall, cnt;
		
		public Point(int x, int y, int wall, int cnt) {
			this.x= x;
			this.y= y;
			this.wall= wall;
			this.cnt= cnt;
		}
	}
}

www.acmicpc.net/problem/2206