백준 알고리즘/그래프 순회

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

Sun720 2022. 7. 28. 22:42

▶ 문제

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

 

2206번: 벽 부수고 이동하기

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로

www.acmicpc.net

 

▶ 설명

 

3차 배열 사용

미로탐색, 토마토 문제와 같이 BFS로 풀 때 2차 배열을 Queue에 저장/삭제하며 노드를 방문하는 방식을 사용했다.

하지만 이번 문제는 2차 배열로 풀기엔 적합하지 않았다. 벽을 부술 때 체크하는 boolean 체크 배열을 따로 만들기도 해보고, 2차 배열이 아닌 ArrayList를 사용해보기도 했지만 메모리초과가 거듭 발생하기만 했다.

결국 3차 배열로 풀으니 해결이 되었다.

 

다음 노드로 방문할 때마다 전 칸보다 1씩 증가시키는 방문 체크 배열을 만들되, 종이로 치면 두 장을 만드는 것이다.

그래서 한 장은 벽을 부수지 않고 지나가는 방문체크용으로, 다른 한 장은 벽을 1번 부순적이 있을 때 방문체크하는 용으로 두도록 한다.

문제에서 주어진 조건 처럼, 벽은 꼭!! 1번까지만 부술 수 있다는 것에 주의하여야 한다.

 

3차 배열로 하는 이유

2차 배열로 하지 않고 3차 배열로 이렇게까지 하는 이유는 , 단순히 생각했을 때 벽을 부숴야지만 더 빨리 도착할 수 있다고 생각이 들 수 있지만 벽을 부수지 않고 지나갔을 때 더 빨리 도착할 수 있을 때도 있기 때문이다. 그렇기 때문에 벽을 한 번도 부시지 않고 방문할 때와 한번쯤은 부쉈을 때의 방문 체크를 분리하여야 하는 것이다.

 

목적지에 방문했을 때 반환하기

목적지 위치에 도착했으면 그 위치의 벽을 부쉈을 경우의 인덱스와, 벽을 부시지 않았을 경우의 인덱스 를 이용하여 값을 비교한 후, 둘 중 하나는 0일 테니까 Math.max() 메소드를 이용하여 최대값을 구하여 반환하면 된다.

둘 중 하나가 0인 이유는 모든 노드를 방문한 다음에 최종 값을 비교하는 것이 아니라 둘 중 하나라도 먼저 도착하면 값을 비교하는 것이기 때문에 선착순 느낌으로 방문체크가 된 곳이 반환되는 것이다.

 

풀이 2개의 차이점

문제를 두 번 풀어 보았는데

풀이 1은 다음 노드가 벽인지 아닌지에 따른 조건으로 나눈 것이고,

풀이2는 지금 노드가 벽을 부쉈던 적이 있는지 없는지에 따라 크게 조건으로 나누어 풀었다.

 

 

▶ 문제 풀이

🌱 풀이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 {
	static int n, m;
	static int[][] map;

	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());

		// NxM 맵 행렬 생성 (1과 0이 값으로 들어옴)
		map = new int[n][m];
		for (int i = 0; i < map.length; i++) {
			String str = br.readLine();
			for (int j = 0; j < map[i].length; j++) {
				int num = str.charAt(j) - '0';
				if (num == 1) {
					map[i][j] = num;
				}
			}
		}
		// 출발지와 목적지가 같을 경우
		if (n == 1 && m == 1) {
			System.out.println(1);
			System.exit(0);
		}
		System.out.println(bfs());

	}

	private static int bfs() {
		// 방문을 체크하는 3차원 배열
		int[][][] check = new int[2][n][m];
		// [0, n, m] : 벽 안부수고 지나가는 방문노드 경로
		// [1, n, m] : 벽 부수고 지나가는 방문노드 경로

		// 동서남북
		int[] ax = { 0, 0, -1, 1 };
		int[] ay = { -1, 1, 0, 0 };

		Queue<int[]> q = new LinkedList<>();
		// 시작 노드를 q에 담기
		q.offer(new int[] { 0, 0, 0 });
		// 벽 안부쉈으니까 {0, 0, 0}에 지나온 칸의 개수 1을 값으로 넣기.
		check[0][0][0] = 1;

		while (true) {

			int[] node = q.poll();
			int w = node[0];// broken wall or unbroken wall
			int x = node[1];
			int y = node[2];

			for (int i = 0; i < 4; i++) {
				int nx = x + ax[i];
				int ny = y + ay[i];
				// map과 check에 쓰일 인덱스가 배열의 범위를 벗어나면 무시하기.
				if (nx >= n || nx < 0 || ny >= m || ny < 0) {
					continue;
				}

				// 다음 노드가 벽이 아닐 때 -> 다음노드의 w가 0인 자리가 비어있다면 (0이라면) - w가 0이면 0인 자리에, 1이면 1인 자리에 방문 체크할 것.
				if (map[nx][ny] == 0) {
					if (check[w][nx][ny] == 0) {
						q.offer(new int[] { w, nx, ny });
						check[w][nx][ny] = check[w][x][y] + 1;
						if (nx == n - 1 && ny == m - 1) {
							return check[w][nx][ny];
						}

					}
				} 
				// 다음 노드가 벽일 때 -> 1. w가 1보다 큰 범위를 벗어나게 생겼다면 방문체크와 q에 넣는 것을 제외하도록 하고,
				// 						2. 벗어나지 않는다면 w+1 에다가 방문체크하고 q에 넣을 것.
				else {
					if (w == 0) {
						if (check[1][nx][ny] == 0) {
							q.offer(new int[] { 1, nx, ny });
							check[1][nx][ny] = check[0][x][y] + 1;
							if (nx == n - 1 && ny == m - 1) {
								return check[1][nx][ny];
							}
						}
					}
				}

			}

			if (q.isEmpty()) {
				return -1;
			}
		}

	}

}

 

 

 

🌱 풀이2. 

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 {
	static int n, m;
	static int[][] map;

	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());
		//출발지와 목적지가 같을 경우
		if(n==1&&m==1) {
			System.out.println(1);
			System.exit(0);
		}
		// NxM 맵 행렬 생성 (1과 0이 값으로 들어옴)
		map = new int[n][m];
		for (int i = 0; i < map.length; i++) {
			String str = br.readLine();
			for (int j = 0; j < map[i].length; j++) {
				int num = str.charAt(j) - '0';
				if (num == 1) {
					map[i][j] = num;
				}
			}
		}
		System.out.println(bfs());

	}

	private static int bfs() {
		// 방문을 체크하는 3차원 배열
		int[][][] check = new int[2][n][m];
		// [0, n, m] : 벽 안부수고 지나가는 방문노드 경로
		// [1, n, m] : 벽 부수고 지나가는 방문노드 경로

		// 동서남북
		int[] ax = { 0, 0, -1, 1 };
		int[] ay = { -1, 1, 0, 0 };

		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] { 0, 0, 0 });
		check[0][0][0] = 1;

		while (true) {

			int[] node = q.poll();
			if (node == null) {
				return -1;
			}
			int w = node[0];// broken wall or unbroken wall
			int x = node[1];
			int y = node[2];

			for (int i = 0; i < 4; i++) {
				int nx = x + ax[i];
				int ny = y + ay[i];
				if (nx >= n || nx < 0 || ny >= m || ny < 0) {
					continue;
				}

				if (w == 0) {// 지금 노드가 벽이 아닐 때
					if (map[nx][ny] == 0 && check[0][nx][ny]==0) { // 다음 노드가 벽이 아닐 때
						
						q.offer(new int[] { 0, nx, ny });
						check[0][nx][ny] = check[0][x][y] + 1;
					} else if(map[nx][ny] == 1 && check[0][nx][ny]==0){ // 다음 노드가 벽일 때
						if (check[1][nx][ny] == 0) {// 다음 노드가 이전에 방문한 적이 있다면 pass

							q.offer(new int[] { 1, nx, ny });
							check[1][nx][ny] = check[0][x][y] + 1;
						}
					}
				} else {
					if (map[nx][ny] == 0) { // 다음 노드가 벽이 아닐 때
						if (check[1][nx][ny] == 0) {

							q.offer(new int[] { 1, nx, ny });
							check[1][nx][ny] = check[1][x][y] + 1;
						}
					}
				}
				if (nx == n - 1 && ny == m - 1) {
					return Math.max(check[0][nx][ny], check[1][nx][ny]);
				}

			}

		}

	}

}

 

 

 

 

 

▶ Log

  • 풀이 1과 풀이 2는 메소드 안에서 조건 분기만 다르게 했다. 성능은 풀이 1이 더 좋게 나왔다.

 

(위: 풀이1, 아래: 풀이2)

 

  • 3차원 배열로 처음에 만들려고 할 때 머리속으로 그려내기가 어려웠다. BFS 최단경로 구하는 문제나 다익스트라 알고리즘에 적용하면 좋을 아이디어를 유튜브 강의를 통해 학습을 하였고,  다행히도 영상을 통해 설명을 보고 들으니 한층 더 이해가 잘 되었다. 벽을 부순 적이 있을 때와 한 번도 부수지 않고 지나갈 때를 분리하여 방문처리한다는 아이디어는 정말이지 멋진 것 같다. BFS의 세계는 어디까지 확장되어 있을지 문제를 풀고풀고 풀어도 새로운 것이 자꾸만 나오는 것이, 아직은 나에게 우주같은 느낌이다.  참고 동영상 사이트 

 

 

 

 

 

728x90
반응형

'백준 알고리즘 > 그래프 순회' 카테고리의 다른 글

[JAVA 자바] 백준 16928번 : 뱀과 사다리 게임  (0) 2022.07.27
[JAVA 자바] 백준 7569번 : 토마토  (0) 2022.07.25
[JAVA 자바] 백준 7576번 : 토마토  (0) 2022.07.24
[JAVA 자바] 백준 2179번 : 미로 탐색  (0) 2022.07.23
[JAVA 자바] 백준 1012번 : 유기농 배추  (0) 2022.07.22

'백준 알고리즘/그래프 순회'의 다른글

  • 현재글[JAVA 자바] 백준 2206번 : 벽 부수고 이동하기

관련글

댓글

티스토리툴바