[백준_2206번] 벽 부수고 이동하기

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

2206번: 벽 부수고 이동하기

[문제]

 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이라고 가정하자.

 

[코드]

import java.util.*;

class Position_2206 {
	public int x;
	public int y;
	public int distance;
	public int drill; // 공사 횟수
	
	public Position_2206(int x, int y, int distance, int drill) {
		this.x=x;
		this.y=y;
		this.distance=distance;
		this.drill=drill; 
	}
}

public class BaekJoon_2206 {
	public static int[][] map,visited;
	public static int[] dx= {0,0,-1,1};
	public static int[] dy= {-1,1,0,0};
	public static int n,m,answer=Integer.MAX_VALUE;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		
		map=new int[n][m];
		visited=new int[n][m]; // 해당 좌표의 공사 횟수를 저장하는 배열
		
		for(int i=0;i<n;i++) {
			String str=sc.next();
			for(int j=0;j<m;j++) {
				map[i][j]=str.charAt(j)-'0';
				visited[i][j]=Integer.MAX_VALUE;
			}
		}
		
		bfs(0,0);

		if(answer==Integer.MAX_VALUE)
			System.out.println(-1);
		else
			System.out.println(answer);
	}
	
	public static void bfs(int x,int y) {
		Queue<Position_2206> q=new LinkedList<>();
		
		q.offer(new Position_2206(x,y,1,0)); // 시작 지점을 포함한 거리 1로 시작
		visited[x][y]=0; // 처음 공사 횟수
		
		while(!q.isEmpty()) {
			Position_2206 position=q.poll();
			
			// 도착지점을 만났다면 이동 거리를 저장하고 종료
			if(position.y==m-1&&position.x==n-1) {
				answer=position.distance;
				break;
			}
			
			for(int i=0;i<4;i++) {
				int nx=dx[i]+position.x;
				int ny=dy[i]+position.y;
				
				// 범위를 벗어난다면 넘어간다.
				if(ny>=m||nx>=n||nx<0||ny<0)
					continue;
				
				// 이동한 좌표의 공사 횟수가 기존에 갖고있던 값보다 작을 경우 넘어간다.
				if(visited[nx][ny]<=position.drill)
					continue;
				
				if(map[nx][ny]==0) { // 벽이 아닐 경우
					visited[nx][ny]=position.drill; // 부순 횟수 유지
					// 이동한 좌표와, 이동 거리를 1 증가한 값을 큐에 삽입한다.
					q.add(new Position_2206(nx,ny,position.distance+1,position.drill));
				}
				else { // 벽일 경우
					if(position.drill==0) { // 지금까지 벽을 부순 횟수가 0일 경우
						visited[nx][ny]=position.drill+1; // 부순 횟수를 1 높여주고
						// 이동한 좌표와, 거리와 부순 횟수를 1씩 증가한 값을 큐에 삽입한다.
						q.add(new Position_2206(nx,ny,position.distance+1,position.drill+1));
					}
				}
				
			}
		}
	}
}

 

[고찰]

 이번 문제는 스스로 풀어봤지만 오답 처리를 받아 다른 사람의 코드를 참고했다. 이번 문제에서 실수한 점은 좌표를 저장할 클래스를 만들때 해당 좌표에서 이동 거리와, 공사 횟수도 함께 저장해야 한다는 것과, 방문 배열 visited를 boolean 형식이 아닌 int형으로 선언해 해당 좌표에서 방문 여부와 함께 공사 횟수를 체크해야 한다는 것이었다. 

 DFS와 BFS 유형의 문제들은 형태만 바꿔 다양하게 출제되기 때문에 꼭 익혀둬야 할 것 같다.

 

1. Class 선언 시에는 필요한 값들을 변수로 만들기

2. 방문 배열은 boolean형이 아닌 int형으로 만들어 무한대로 초기화 해두기

3. BFS안에서 for문으로 상,하,좌,우 체크하며 이동하게 되면, 결국 똑같은 위치를 여러번 탐색하게 되기 때문에 방문 배열의 최소 값을 계속 가져가며 조건 걸어주기

 

다른 사람의 포스팅을 보고 적은 팁 3가지이다. DFS와 BFS의 문제 유형은 비슷하지만 말만 바꿔 다양하게 출제되기 때문에 위의 팁들은 익혀두는 것이 좋다고 느꼈다.