[알고리즘] Java / 백준 / 벽 부수고 이동하기 / 2206
[알고리즘] Java / 백준 / 벽 부수고 이동하기 / 2206
문제
접근 방식
기존 2차원 배열을 탐색하는 2차원 방문에, 벽을 부순 후 이동과 벽을 부수지 않고 이동하는 두 가지의 방문이 추가로 필요하기 때문에 3차원 visited배열로 방문을 처리한다
주의할 점
- 시작 칸도 거리를 센다
// 틀렸던 반례
1 1
0
-> 정답 : 1
코드
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 Main_2206_정현명 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] map = new int[N][M];
for(int i=0;i<N;i++) {
String line = br.readLine();
for(int j=0;j<M;j++) {
map[i][j] = line.charAt(j) - '0';
}
}
boolean[][][] visited = new boolean[N][M][2];
int[][] deltas = {{-1,0},{0,1},{0,-1},{1,0}};
Queue<int[]> queue = new LinkedList<int[]>();
queue.add(new int[] {0,0,0,1});
while(!queue.isEmpty()) {
int[] info = queue.poll();
int r = info[0];
int c = info[1];
int chance = info[2];
int distance = info[3];
if(r == N-1 && c == M-1) {
System.out.println(distance);
return;
}
for(int i=0;i<4;i++) {
int nextR = r + deltas[i][0];
int nextC = c + deltas[i][1];
if(nextR < 0 || nextR >= N || nextC < 0 || nextC >= M) continue;
if(!visited[nextR][nextC][chance]) {
if(map[nextR][nextC] == 0) {
visited[nextR][nextC][chance] = true;
queue.add(new int[] {nextR,nextC,chance,distance+1});
}
}
if(chance<1 && map[nextR][nextC] == 1 && !visited[nextR][nextC][chance+1]) {
visited[nextR][nextC][chance+1] = true;
queue.add(new int[] {nextR,nextC,chance+1,distance+1});
}
}
}
System.out.println(-1);
}
}
Author And Source
이 문제에 관하여([알고리즘] Java / 백준 / 벽 부수고 이동하기 / 2206), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gandi0330/알고리즘-Java-백준-벽-부수고-이동하기-2206저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)