백준 2206; Java

 

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

2206번: 벽 부수고 이동하기

import java.util.*;
import java.io.*;

public class Main {
	static int N, M, ans;
	static int[][] accum, map;	//누적 공사 횟수 
	static int[] row= {0,0,1,-1};
	static int[] col= {1,-1,0,0};
	
	static class node{
		int x;
		int y;
		int length;
		int work;	//벽 공사 횟수 
		
		node(int x, int y, int length, int work){
			this.x=x; this.y=y;
			this.length=length;
			this.work=work;
		}
	}
	
	public static void bfs(int r, int c) {
		Queue<node> q=new LinkedList<>();
		q.offer(new node(r, c, 1, 0));
		accum[r][c]=0;
		
		while(!q.isEmpty()) {
			node nd=q.poll();
			
			if(nd.x==N && nd.y==M) {//도착 
				ans=nd.length;
				break;
			}
			
			for(int a=0;a<4;a++) {
				int nr=nd.x+row[a];
				int nc=nd.y+col[a];
				
				if(nr>0&&nr<=N&&nc>0&&nc<=M) {
					if(accum[nr][nc] > nd.work) {////현재 노드까지의 공사 횟수(0 || 1)<가볼 곳의 누적 공사 횟수(0 || 1 || max) 
						if(map[nr][nc]==0) {//벽이 없으면 
							accum[nr][nc]=nd.work;
							q.offer(new node(nr, nc, nd.length+1, nd.work));
						}else {//벽이 있음 
							if(nd.work==0) {//벽 공사를 한 적 없으면 
								accum[nr][nc]=nd.work+1;//갈 곳의 누적 공사 횟수를 늘려줌 
								q.offer(new node(nr, nc, nd.length+1, nd.work+1));
							}
						}
					}	
				}
			}
		}
		
	}
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String str[]=br.readLine().split(" ");
		N=Integer.parseInt(str[0]);
		M=Integer.parseInt(str[1]);
		map=new int[N+1][M+1];
		accum=new int[N+1][M+1];
		
		for(int i=1;i<=N;i++) {
			str=br.readLine().split("");
			for(int j=1;j<=M;j++) {
				map[i][j]=Integer.parseInt(str[j-1]);
				accum[i][j]=Integer.MAX_VALUE;
			}
		}
		ans=Integer.MAX_VALUE;
		bfs(1,1);
		
		if(ans==Integer.MAX_VALUE)	System.out.println(-1);
		else	System.out.println(ans);
		
	}

}

 

최단 경로라서 backtracking && bfs 로 하다가 시간만 날렸네,,,ㅎㅎ 와~

 

https://kim6394.tistory.com/201

[백준 2206] 벽 부수고 이동하기 (Java, BFS)

..천재일까..? (오열)

---

사실 이해가 제대로 되진 않았다.. 대충 이해함.. 

 

accum[i][j]는 (1,1) ->(i, j)까지 누적 공사 횟수

node의 length는 (1,1)부터 현재 노드까지 경로 길이

node의 work는 (1,1)부터 현재 노드까지 공사 횟수

 

큐에서 뺀 노드를 현재 노드라고 한다. 그 노드의 사방위를 한 개씩(갈 노드) 검사한다.

갈 노드의 누적 공사 횟수(accum[nr][nc])는 0, 1, max 중 하나이다. 0 혹은 1이면 갈 노드가 한 번 이상 방문된 적이 있다는 의미이다.

현재 노드의 누적 공사 횟수(nd.work)는 0, 1 중 하나이다.

현재 노드의 누적 공사 횟수는 갈 노드의 누적 공사 횟수보다 작아야만(~방문한 적이 없어야지) 갈 노드로 전진이 가능하다.

 

이때, 현재 노드까지의 공사 횟수가 0, 갈 노드의 누적 공사 횟수가 1 인 경우는 갈 노드가 한 번 이상 방문한 적이 있다는 의미, 즉 다른 경로에 포함된 적이 있다는 것이다. 

 

그리고 도착한 노드의 길이가 왜 최단 거리인지 처음에 이해가 안되었는데, 이 부분은 트리를 그리면서 조금 이해가 됐다.. 

제일 빨리 도착하고 break;를 해서 탐색을 끝내버렸으니 그 노드의 길이가 최단 거리이다..