[백준(Baekjoon)][자바(java)] 2206 : 벽 부수고 이동하기 / DFS와 BFS

 

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

1. 각 셀마다 벽을 부순 횟수를 담은 int[][] 배열을 생성하여 풀기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
	
	static int n, m, map[][], breakCnt[][];
	static int dx[] = { 1, 0, -1, 0 }, dy[] = { 0, 1, 0, -1 };
	
	static class Cell {
		int x;
		int y;
		int d; 	// distance;
		int b; 	// break cnt ( 0, 1, 2 = not visited )
		public Cell( int x, int y, int d, int b ) {
			this.x = x;
			this.y = y;
			this.d = d;
			this.b = b;
		}
	}
	
	public static int getShorest_BFS( int x, int y ) {
		Deque<Cell> q = new ArrayDeque<>();
		q.add( new Cell( x, y, 1, 0 ) );
		breakCnt[x][y] = 0;
		while( !q.isEmpty() ) {
			Cell c = q.remove();
			if( c.x == n && c.y == m )
				return c.d;
			int d_p = c.d + 1;
			for( int u = 0; u < 4; u++ ) {  // top,bottom,left,right
        		int x_p = c.x + dx[u];  // path x
        		int y_p = c.y + dy[u];  // path y
        		if( 1 <= x_p && x_p <= n && 1 <= y_p && y_p <= m && breakCnt[x_p][y_p] > c.b ) {
                // 다음 셀이 아직 방문하지 않은 길이거나 / 현재 셀은 그냥 길, 다음 셀은 벽 뚫린 길일 때
        			if( map[x_p][y_p] == 0 ) {
        				q.add( new Cell( x_p, y_p, d_p, c.b ) );
            			breakCnt[x_p][y_p] = c.b;
        			}
        			if( map[x_p][y_p] == 1 && c.b == 0 ) {
        				q.add( new Cell( x_p, y_p, d_p, 1 ) );
            			breakCnt[x_p][y_p] = 1;
        			}
        		}   
			}
		}
		return -1;
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		StringTokenizer st = new StringTokenizer( br.readLine() );
		n = Integer.parseInt( st.nextToken() );
		m = Integer.parseInt( st.nextToken() );
		map = new int[n+1][m+1];
		breakCnt = new int[n+1][m+1];
		for( int i = 1; i <= n; i++ ) {
			String s = br.readLine();
			for( int j = 1; j <= m; j++ ) {
				map[i][j] = s.charAt(j-1) - '0';
				breakCnt[i][j] = 2;
			}
		}
		
		System.out.println( getShorest_BFS( 1, 1 ) );
	}
}

 

2. 이미 입력받은 map int[][] 배열에서 값을 변경해가며 풀기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	
	static int n, m, map[][];
	static int dx[] = { 1, 0, -1, 0 }, dy[] = { 0, 1, 0, -1 };
	static final int wall = 1, path = 0, path_o = 2, path_b = 3;  // ordinary path, broken path
	
	static class Cell {
		int x;
		int y;
		int d;		// distance;
		boolean b;  // is it broken wall ?
		public Cell( int x, int y, int d, boolean b ) {
			this.x = x;
			this.y = y;
			this.d = d;
			this.b = b;
		}
	}
	
	public static int getShorest_BFS( int x, int y ) {
		Deque<Cell> q = new LinkedList<>();
		q.add( new Cell( x, y, 1, false ) );
		map[x][y] = path_o;
		while( !q.isEmpty() ) {
			Cell c = q.remove();
			if( c.x == n && c.y == m )
				return c.d;
			int p_cur = map[c.x][c.y];
			int x_p, y_p, d_p = c.d + 1, p_next;
			for( int u = 0; u < 4; u++ ) {  // top,bottom,left,right
        		x_p = c.x + dx[u];  // path x
        		y_p = c.y + dy[u];  // path y
        		if( 1 <= x_p && x_p <= n && 1 <= y_p && y_p <= m ) {
        			p_next = map[x_p][y_p];
    				if( p_next == path ) {
    					q.add( new Cell( x_p, y_p, d_p, c.b ) );
    					map[x_p][y_p] = c.b ? path_b : path_o;
    				}
    				else if( p_next == wall && !c.b ) {
    					q.add( new Cell( x_p, y_p, d_p, true ) );
    					map[x_p][y_p] = path_b;
    				}
        			else if( p_cur == path_o && p_next == path_b ) {
        				q.add( new Cell( x_p, y_p, d_p, false ) );
        				map[x_p][y_p] = path_o;
        			}
        		}   
			}
		}
		return -1;
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		StringTokenizer st = new StringTokenizer( br.readLine() );
		n = Integer.parseInt( st.nextToken() );
		m = Integer.parseInt( st.nextToken() );
		map = new int[n+1][m+1];
		for( int i = 1; i <= n; i++ ) {
			String s = br.readLine();
			for( int j = 1; j <= m; j++ )
				map[i][j] = s.charAt(j-1)-'0';
		}
		
		System.out.println( getShorest_BFS( 1, 1 ) );	
	}
}