백준_2206 벽 부수고 이동하기(자바) / BFS

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

 

잘못된 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N,M,arrSize,ans=Integer.MAX_VALUE;
	static boolean visited[][][];
	static int map[][];
	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,-1,1};
	static ArrayList<point> arr = new ArrayList<>();

	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][M];
		
		for (int i = 0; i < N; i++) {
			String tmp = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j]= tmp.charAt(j)-'0';
				if(map[i][j]==1) {
					arr.add(new point(i, j,0));
				}
			}
		}
		
		visited = new boolean[N][M][arr.size()];
		
		for (int i = 0; i < arr.size(); i++) {
			arrSize=i;
			map[arr.get(i).x][arr.get(i).y]=0;
			bfs();
			map[arr.get(i).x][arr.get(i).y]=1;
		}
		if(ans==Integer.MAX_VALUE) {
			System.out.println("-1");
		}else {			
			System.out.println(ans);
		}
	}

	private static void bfs() {
		Queue<point> q = new LinkedList<>();
		visited[0][0][arrSize] = true;
		q.add(new point(0,0,1));
		while(!q.isEmpty()) {
			point p = q.poll();
			if(p.x==N-1&&p.y==M-1) {
				ans=Math.min(ans, p.cnt);
				break;
			}
			
			for(int k = 0;k<4;k++) {
				int xx = dx[k]+p.x;
				int yy = dy[k]+p.y;
				if(xx<0||xx>=N||yy<0||yy>=M)continue;
				if(map[xx][yy]==0&&!visited[xx][yy][arrSize]) {
					q.add(new point(xx,yy,p.cnt+1));
				}
					
			}
		}
	}

	static class point{
		int x;
		int y;
		int cnt;
		public point(int x, int y,int cnt) {
			super();
			this.x = x;
			this.y = y;
			this.cnt=cnt;
		}
		
	}
}

 

- 정답은 맞게 출력이 되지만, 메모리 초과가 발생합니다.

처음에 진행했던 아이디어는 모든 벽을 돌면서 값이 1이면 0으로 바꾸고, BFS를 돌려 확인을 해주는 방식으로 진행을 했습니다.

package com.back;

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

public class Back_2206 {
	static int N,M,ans=Integer.MAX_VALUE;
	static int[][] map;
	static int visited[][];
	static int dx[]= {-1,1,0,0};
	static int dy[]= {0,0,-1,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][M];
		visited = new int[N][M];
		
		String tmp;
		for (int i = 0; i < N; i++) {
			tmp = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j]= tmp.charAt(j)-'0';
				visited[i][j] = Integer.MAX_VALUE;
			}
		}
		
		bfs();
		if(ans == Integer.MAX_VALUE) System.out.println(-1);
		else System.out.println(ans);
	}
	private static void bfs() {
		Queue<Point> q = new LinkedList<>();
		q.add(new Point(0, 0, 1, 0));
		visited[0][0] = 0;
		
		while(!q.isEmpty()) {
			
			Point p = q.poll();
			
			if(p.x == N-1 && p.y == M-1) {
				ans = p.move;
				break;
			}
			
			for (int i = 0; i < 4; i++) {
				int xx = p.x + dx[i];
				int yy = p.y + dy[i];
				
				if(xx<0 || xx>=N || yy<0 || yy>=M) continue;
				
				if(visited[xx][yy]<=p.des) continue;
				
				if(map[xx][yy]==0) {
					visited[xx][yy] = p.des;
					q.add(new Point(xx, yy, p.move+1, p.des));
				}else {
					if(p.des==0) {
						visited[xx][yy]=p.des+1;
						q.add(new Point(xx, yy, p.move+1, p.des+1));
					}
				}
			}
		}
	}
	static class Point{
		int x;
		int y;
		int move;
		int des;
		public Point(int x, int y, int move, int des) {
			super();
			this.x = x;
			this.y = y;
			this.move = move;
			this.des = des;
		}
	}
}

※ 내 생각

이 문제는 BFS로 해결을 했습니다.

처음에 했던 풀이 역시 BFS로 풀었는데 메모리 초과가 발생했고,
다른 사람의 풀이를 보고 다시 진행했습니다.

방문 여부 처리를 조금은 다르게 처리를 진행했습니다.