https://www.acmicpc.net/problem/2206
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로
www.acmicpc.net
문제풀이
BFS 문제입니다.
이 문제에서 가장 중요한 로직은,
벽을 한번 부순후에는 그 이후에 움직이는 위치의 표시도 벽을 부순것으로 처리해야한다는 것입니다.
즉, 벽을 한번 부순 후에 벽을 부순 Visited[0][0][1] 로 처리하지 않으면,
벽을 1번 뚫고 진행한 경로와 벽을 뚫지않고 진행한 경로가 겹쳐서 문제가 됩니다.
에러나는 예시 케이스입니다.
5 5 00000 11101 00001 01111 00010
여기서 문제점은 (1,0)의 벽을 뚫고서 이동하였을때 만약 이후의 움직이부터 Visited[0][0][1] 로 처리하지 않는다면,
아직 벽을 뚫지않은 노드가 (2,0) -> (2,1) -> (...) 로 이동하는 경로로 가지못하고, 끝의 (4, 3)의 벽을 뚫지 못하여 -1 이 나옵니다.
이 경우에 출력값이 answer처럼 15가 나와야합니다.
출력: -1 answer: 15
해당 코드로직입니다.
//빈 공간이라면 if(map[nx][ny] =='0') { //벽을 한번도 부순적이 없다면, if(wallbreakflag == false && visited[nx][ny][0] == false) { visited[nx][ny][0] = true; q.offer(new Node(nx, ny, cnt+1, wallbreakflag)); } //벽을 부순적이 있다면 else if(wallbreakflag == true && visited[nx][ny][1] == false){ q.offer(new Node(nx, ny, cnt+1, wallbreakflag)); visited[nx][ny][1] = true; } }
여기서보면, 빈공간일때 벽을 부순적이 없다면, 벽을 부순적이 없는 Visited[][][0] 을 사용하고
벽을 부순적이 있다면 그 이후부터는 벽을 부순적이 있다는 Visited[][][1] 을 사용합니다.
해당 사항을 생각하지 못하여서 어려웠던 문제였습니다.
코드
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static int N,M; public static char[][] map; public static Queue<Node> q = new LinkedList<>(); public static boolean[][][] visited; public static int result=-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 char[N][M]; visited = new boolean[N][M][2]; for(int i=0;i<N;i++) { map[i] = br.readLine().toCharArray(); } simulate(); System.out.println(result); } public static void simulate() { int[] dx = {-1,1,0,0}; int[] dy = {0,0,-1,1}; q.offer(new Node(0,0,0,false)); visited[0][0][0] = true; while(!q.isEmpty()) { Node temp = q.poll(); int x = temp.x; int y = temp.y; int cnt = temp.cnt; boolean wallbreakflag = temp.wallbreakflag; if(x == N -1 && y == M - 1) { result = cnt + 1; return; } for(int dir=0;dir<4;dir++) { int nx = temp.x + dx[dir]; int ny = temp.y + dy[dir]; if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue; //벽이라면 벽을 부술 수 있는지 없는지 확인해야합니다. if(map[nx][ny] =='1' && visited[nx][ny][1] == false) { //벽을 이전에 부순적이 없다면 if(wallbreakflag == false) { q.offer(new Node(nx, ny, cnt+1, true)); visited[nx][ny][1] = true; } //벽을 이전에 부순적이 있다면 false else if(wallbreakflag == true) { continue; } } //빈 공간이라면 if(map[nx][ny] =='0') { //벽을 한번도 부순적이 없다면, if(wallbreakflag == false && visited[nx][ny][0] == false) { visited[nx][ny][0] = true; q.offer(new Node(nx, ny, cnt+1, wallbreakflag)); } //벽을 부순적이 있다면 else if(wallbreakflag == true && visited[nx][ny][1] == false){ q.offer(new Node(nx, ny, cnt+1, wallbreakflag)); visited[nx][ny][1] = true; } } } } } } class Node{ int x; int y; int cnt; boolean wallbreakflag; public Node(int x, int y, int cnt,boolean wallbreakflag) { this.x=x; this.y=y; this.cnt = cnt; this.wallbreakflag = wallbreakflag; } }
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 9466 텀 프로젝트 - DFS + 아이디어 + 시간초과 JAVA (0) | 2023.07.06 |
---|---|
[백준] 16932 모양 만들기 - BFS or DFS + 아이디어 JAVA (0) | 2023.07.05 |
[백준] 16954 움직이는 미로 탈출 - BFS JAVA (0) | 2023.07.03 |
[백준] 1600 말이 되고픈 원숭이 - BFS JAVA (0) | 2023.07.02 |
[백준] 4179 불! - BFS JAVA (0) | 2023.06.28 |