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

🔗 문제

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

2206번: 벽 부수고 이동하기

 

🧩 풀이 및 코드

문제 유형 : 그래프 이론, 그래프 탐색, 너비우선탐색

 

풀이

보통 BFS 문제와 다른 점과 핵심은 x 지점에서 벽을 만났을 때, 벽을 부술지 안부술지 2가지 경우가 있다는 것이다.

 이해해야 할 것 : 특정 지점에 벽을 부숴서 도착하는 경우가 더 빠를지라도, 벽을 안부수고 이동한 경우가 정답일 수 있다.

좀 더 쉽게 이해하기 위해 예시를 들어보자

8 8
01000100
01010100
01010100
01010100
01010100
01010100
01010100
00010100

만약 (0, 1) 인 지점에서 벽을 부쉈다면, 안부수고 돌아가는 경우보다 (0, 5) 에 먼저 도착할 것이다.

하지만 이미 벽을 한 번 부수고 왔기 때문에 더 이상 벽을 부술 수 없어 막히게 된다.

하지만 벽을 부수지 않고 돌아왔다면 벽을 부쉈을 경우보다 느리게 도착했지만 벽을 부술 수 있기 때문에 부수고 도착지에 도착할 수 있다.

따라서 BFS 에서 사용했던 방문 체크 배열을 2개 만들어야 한다. (이미 벽을 부수면서 방문했다고 체크하면 벽을 안부순 경우는 막히게 된다 )

boolean[ ][ ][ ] visited = new boolean [N][M][2]

0 은 벽을 부수지 않을 경우, 1 은 벽을 부쉈을 경우에 사용한다.

• 벽을 만나지 않고 방문도 하지 않았다면 그대로 진행한다.
• 벽을 한 번도 부수지 않고, 벽을 만났다면 [1] 에 체크한다.

느낀 점

이해하기 힘들다.. 내일 벽부수고 이동하기 다른 예제 더 풀어봐야지

 

전체 코드

코드를 2개 작성했다.

가독성이 조금 높고 덜 깔끔한 코드, 가독성은 낮지만 깔끔한 코드

 

가독성 높은 코드

import java.io.*;
import java.util.*;

public class Main {
	
	static int N, M;
	static int[][] map;
	
	public static void main(String[] args) throws Exception {
		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 s = br.readLine();
			for(int j=0; j<M; j++) {
				map[i][j] = s.charAt(j)-'0';
			}
		}
		
		System.out.println(BFS());
		br.close();
	}
	
	static class Loc {
		int x; 
		int y;
		int cnt;
		boolean broken;
		
		Loc(int x, int y, int cnt, boolean broken) {
			this.x = x;
			this.y = y;
			this.cnt = cnt;
			this.broken = broken;
		}
	}
	
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int BFS() {
		boolean[][][] visited = new boolean[N][M][2];	// 0 은 벽을 안 부순 경우, 1 은 벽을 부순 경우
		Queue<Loc> que = new ArrayDeque<>();
		que.add(new Loc(0, 0, 1, false)); 
		
		while(!que.isEmpty()) {
			Loc now = que.poll();
			
			if(now.x == N-1 && now.y == M-1) {
				return now.cnt;
			}
			
			for(int d=0; d<4; d++) {
				int nx = now.x + dx[d];
				int ny = now.y + dy[d];
				
				if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
				
				if(now.broken) {				// 부순 경우
					if(map[nx][ny] ==0 && !visited[nx][ny][1]) {
						visited[nx][ny][1] = true;
						que.add(new Loc(nx, ny, now.cnt+1, true));
					}
				} else {						// 안 부순 경우
					if(map[nx][ny] == 0 && !visited[nx][ny][0]) {
						visited[nx][ny][0] = true;
						que.add(new Loc(nx, ny, now.cnt+1, false));
					}
					if(map[nx][ny] == 1 && !visited[nx][ny][1]) {
						visited[nx][ny][1] = true;
						que.add(new Loc(nx, ny, now.cnt+1, true));
					}
				}
			}
		}
		
		return -1;
	}

}

 

가독성 낮은 코드 but) 깔끔

import java.io.*;
import java.util.*;

public class Main_bj_2206_벽부수고이동하기_sol2 {
	
	static int N, M;
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_bj_2206.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		int[][][] map = new int[N][M][2];		// 0은 안부순 경우, 1은 부순 경우
		for(int i=0; i<N; i++) {
			String s = br.readLine();
			for(int j=0; j<M; j++) {
				map[i][j][0] = s.charAt(j)-'0';
				
				if(map[i][j][0] == 1) {
					map[i][j][0] = -1;		// 최단거리를 저장할 거여서 벽이라면 -1 로 초기화
					map[i][j][1] = -1;
				}
			}
		}
		
		System.out.println(BFS(map));
		br.close();
	}
	
	static class Loc {
		int x;
		int y;
		int broken;
		
		Loc(int x, int y, int broken) {
			this.x = x;
			this.y = y;
			this.broken = broken;
		}
	}
	
	static int BFS(int[][][] map) {
		map[0][0][0] = 1;
		Queue<Loc> que = new ArrayDeque<>();
		que.add(new Loc(0, 0, 0));		// x, y, 벽을 깼는지 여부
		
		while(!que.isEmpty()) {
			Loc now = que.poll();
			
			if(now.x == N-1 && now.y == M-1) {
				return map[now.x][now.y][now.broken];
			}
			
			for(int d=0; d<4; d++) {
				int nx = now.x + dx[d]; 
				int ny = now.y + dy[d];
				
				if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
				if(map[nx][ny][now.broken] == 0) {		// 벽 아님, 방문한 적 없음
					map[nx][ny][now.broken] = map[now.x][now.y][now.broken] + 1;
					que.add(new Loc(nx, ny, now.broken));
				} else if(now.broken == 0 && map[nx][ny][1] == -1) { // 벽 만남, 아직 깬적 없음, 방문한 적 없음
					map[nx][ny][1] = map[now.x][now.y][0] + 1;
					que.add(new Loc(nx, ny, 1));
				}
			}
		}
		
		return -1;
		
	}

}

 

---

Reference

https://velog.io/@yanghl98/%EB%B0%B1%EC%A4%80-2206-%EB%B2%BD-%EB%B6%80%EC%88%98%EA%B3%A0-%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0-JAVA%EC%9E%90%EB%B0%94

[백준] 2206 : 벽 부수고 이동하기 (JAVA/자바)