[알고리즘 PS] 백준 2206번 벽 부수고 이동하기 자바 문제풀이

[알고리즘 PS] 백준 2206번 벽 부수고 이동하기 자바 문제풀이

728x90

문제

해당 포스팅은 백준의 2206번 벽 부수고 이동하기 의 접근과 해결 방법을 설명한 글 입니다.

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

문제 접근

최단 거리라 BFS로 해결할 수 있는 문제이다.

지금까지 해결했던 BFS 에서는 제일 이해가 힘들었던 문제다.

처음은 브루트포스로 벽을 뚫고 bfs 를 수행했는데 계속해서 시간초과가 나와서 결국 블로그의 힘을 빌렸던 문제다.

정답 코드

public class Main { private static int n; private static int m; private static int[][] visited; private static int[][] arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); String[] nm = br.readLine().split(" "); n = Integer.parseInt(nm[0]); m = Integer.parseInt(nm[1]); visited = new int[n][m]; arr = new int[n][m]; for(int i = 0; i < n; i++) { String[] s = br.readLine().split(""); for(int j = 0; j < m; j++) { arr[i][j] = Integer.parseInt(s[j]); visited[i][j] = Integer.MAX_VALUE; } } bw.write(String.valueOf(bfs())); bw.flush(); bw.close(); } private static int bfs() { int[] xPos = {1, -1, 0, 0}; int[] yPos = {0, 0, 1, -1}; Queue queue = new LinkedList<>(); queue.add(new Position(0, 0, 1, 0)); visited[0][0] = 0; while(!queue.isEmpty()) { Position front = queue.remove(); if(front.x == m - 1 && front.y == n - 1) return front.depth; for(int i = 0; i < 4; i++) { int xx = front.x + xPos[i]; int yy = front.y + yPos[i]; if(!(0 <= xx && xx < m && 0 <= yy && yy < n)) continue; if(visited[yy][xx] > front.breakWall) { // 방문하지 않는 노드만 if(arr[yy][xx] == 0) { queue.add(new Position(xx, yy, front.depth + 1, front.breakWall)); visited[yy][xx] = front.breakWall; }else { if(front.breakWall == 0) { queue.add(new Position(xx, yy, front.depth + 1, front.breakWall + 1)); visited[yy][xx] = front.breakWall + 1; } } } } } return -1; } private static class Position { int x, y, depth, breakWall; Position(int x, int y, int depth, int breakWall) { this.x = x; this.y = y; this.depth = depth; this.breakWall = breakWall; } } }

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

728x90

from http://wonit.tistory.com/573 by ccl(S) rewrite - 2021-08-15 04:00:31