[JAVA] 2206 벽 부수고 이동하기

 

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

2206번: 벽 부수고 이동하기

 

---

접근방법

1. 기본적으로 최단거리 찾기 문제라 바로 BFS가 떠올랐다.

2. BFS 돌릴때 모든 맵의 벽을 모두 한번씩 지워보며 가면 정답이 나오겠네 시간초과 (맞왜틀?)

3. 그럼 가는길에 부술수있으면 부수고 아니면 그냥 갈길 가면서 BFS 타보자 시간초과,메모리 (맞왜틀?)

4. 갈때 부순경우 안부순경우 모두 체크해서 큐에 넣자 (이게맞네?)

 

 

느낀점

고정관념을 버려야 할것같다. 

부순 경우 안부순 경우 한가지경우로만 계속 생각하려고해서 많이 틀렸다.

넓은 시야가 필요한대 이미 뇌가 더럽혀졌다.

import java.io.*;
import java.util.*;
public class Main {
	static int row,col;
	static int[][] map;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine()," ");
		row = Integer.parseInt(stz.nextToken());
		col = Integer.parseInt(stz.nextToken());
		map = new int[row][col];
		String comp;
		for(int i=0;i<row;i++) {
			comp = br.readLine();
			for(int j=0;j<col;j++) {
				if(comp.charAt(j)=='1') map[i][j] = -1;
			}
		}
		bfs();
	}
	static int dxdy[][] = {{0,0,1,-1},{-1,1,0,0}};
	private static void bfs() {
		boolean visited[][][] = new boolean[row][col][2];
		Queue<Data> q = new LinkedList<>();
		q.offer(new Data(0, 0,1,false));
		Data temp;
		while(!q.isEmpty()) {
			temp = q.poll();
			if(row-1 == temp.x && col-1 == temp.y) {
				System.out.println(temp.dist);
				return;
			}
			int nx,ny;
			for(int i=0;i<4;i++) {
				nx = temp.x +dxdy[0][i];
				ny = temp.y +dxdy[1][i];
				if(0<= nx && nx <row && 0<=ny && ny<col) {
					int val = temp.dist + 1;
					if(map[nx][ny]==0) {
						if(!temp.check && !visited[nx][ny][0]) {
							visited[nx][ny][0] = true;
							q.offer(new Data(nx, ny, val, false));
						}else if(temp.check && !visited[nx][ny][1]){
							visited[nx][ny][1] = true;
							q.offer(new Data(nx, ny, val, true));
						}
					}else if(map[nx][ny]== -1) {
						if(!temp.check) {
							visited[nx][ny][1] = true;
							q.offer(new Data(nx, ny, val, true));
						}
					}
				}
			}
		}
		System.out.println(-1);
	}
	static class Data{
		int x;
		int y;
		int dist;
		boolean check;
		public Data(int x, int y,int dist,boolean check) {
			super();
			this.x = x;
			this.y = y;
			this.dist = dist;
			this.check = check;
		}
	}
}

 

그때의 참혹한 기억

이걸 버티네..

고구마 먹은듯이 너무 답답해 죽고싶었다.. 

정답을 맟추고 내려가서 다행인데 이거 못풀었으면 진짜...