백준 1261번 : 알고스팟

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

1261번: 알고스팟

 

 

 

 

 

문제

요약

• 현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하기
• 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다.
• 벽을 부수면, 빈 방과 동일한 방으로 변한다.

 

제한사항

• 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다.
• N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다.
• (1, 1)과 (N, M)은 항상 뚫려있다.

 

 

 

 

 

풀이

 상하좌우 인접한 칸으로 한 칸씩 이동했을 때의 최단 경로를 구하는 문제로, 한 칸씩 이동하며 사방탐색을 통해 모든 경우의 수에 대해 살피고 목표 지점에 도달했을시 탐색을 종료해야 한다. 따라서 BFS 알고리즘을 사용하여 문제를 풀었다.

 

첫번째 풀이 후, 잘못 풀었다는 것을 깨닫고 더 효율적인 방법이 있다는 것을 알게 되었다. 그리고 다른 방법의 풀이를 공부하고 풀어보았다. BFS 알고리즘을 사용한 것은 같지만, 구현 방법이 살짝 다르다.

 

 

 

1. BFS + 3차원 방문 체크 : (515ms 풀이)

2. BFS + 우선순위 큐 : (156ms 풀이)

3. BFS + 덱 (0-1 BFS) : (136ms 풀이)

 

 

 

 

 

 

1. BFS + 3차원 방문 체크

 벽 부수고 이동하기 2(https://www.acmicpc.net/problem/14442)와 유사한 문제라고 생각했다. 벽 부수고 이동하기는 벽을 K개 까지 부수고 이동하는 경우 최단 거리를 구하는 문제이다. 알고 스팟은 최단 거리를 구하는 문제는 아니지만 벽을 최소 몇 개 부수어야 하는지 구하는 문제로 비슷하다고 생각했다.

 

*참고 : 벽 부수고 이동하기 2 풀이 (https://programmingiraffe.tistory.com/146)

 

 

 

 

(개선점이 있는 풀이이다)

 

1. 벽을 지금까지 몇 개 부쉈는지 정보 저장

 

 큐에 좌표 정보를 넣을 때, 행렬 좌표값, 지금까지 몇 개의 벽을 부순적이 있는지 정보를 저장할 필요가 있다. 따라서 좌표 정보를 담는 Point라는 객체에 int 형의 변수(hit)을 추가해줬다.

 

 

 

2. 방문체크 : boolean[N][M][K]

 

 방문체크를 할 때, 해당 지점에 대해 지금까지 벽을 몇 번 부수고 방문했는가 안했는가를 표시했다. 해당 지점에 한번도 안부수고 방문할 수도 있고, 1번 부수고 방문할 수도 있고, .. K번 부수고 방문할 수도 있기 때문이다. 먼저 3번 부수고 방문했어도 후에 1번 부수고 방문할 수도 있기 때문에 방문체크를 다르게 해줘야 한다.

 

 

 

3. 벽인지 벽이 아닌지에 따라 탐색을 다르게 하기

 

• 벽이 아니다
  
  • 지금까지 n개 부숴 방문한적이 없음 => n개 그대로 탐색
• 벽이다
  
  • 지금까지 n +1개 부숴 방문한적이 없음 => n+1 부수고 탐색

 

 

 

4. 도착하면 최솟값 갱신

 

최솟값과 Point의 hit 값과 비교하여 최솟값을 갱신해준다.

 

 

 

5. 경우의 수 가지치기

 

 이대로 탐색을 하게 되면 경우의 수가 어마어마해진다. 무한 루프에 빠지게 되고 시간 초과가 날 것이다. 아직 도착하지도 않았는데, 큐에서 나온 어떤 좌표에서의 지금까지 부순 벽 수가 문제에서의 정답인 최솟값보다 큰 경우들도 있을 것이다. 이미 최솟값을 넘어선다면 더이상 탐색할 필요가 없으므로 이 경우의 수를 가지치기를 해줘야 한다. hit이 min 보다 큰 경우에는 탐색을 더이상 하지 않는다.

 

 

 

 

 

1번 풀이 코드

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

public class Main {
	static int N, M;
	static char[][] graph;
	static boolean[][][] visited;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	
	static class Point {
		int x, y, hit;
		
		Point(int x, int y, int hit) {
			this.x = x;
			this.y = y;
			this.hit = hit;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		M = Integer.parseInt(st.nextToken()); //가로 크기
		N = Integer.parseInt(st.nextToken()); //세로 크기
		
		graph = new char[N][M];
		
		for(int i = 0; i < N; i++) {
			String line = br.readLine();
			
			for(int j = 0; j < M; j++) {
				graph[i][j] = line.charAt(j);
			}
		}
		
		visited = new boolean[N][M][10001];
		
		System.out.println(bfs(0, 0));
	}

	public static int bfs(int i, int j) {
		Queue<Point> queue = new LinkedList<>();
		
		queue.add(new Point(i, j, 0));
		visited[i][j][0] = true;
		
		int min = Integer.MAX_VALUE;
		while(!queue.isEmpty()) {
			Point point = queue.poll();
			
			if(point.x == N - 1 && point.y == M - 1) {
				min = Math.min(min, point.hit);
			}
			
			for(int d = 0; d < 4; d++) {
				int nx = point.x + dx[d];
				int ny = point.y + dy[d];
				
				if(0 > nx || nx >= N || 0 > ny || ny >= M) continue; //미로 밖
				
				if(graph[nx][ny] == '0' && !visited[nx][ny][point.hit] && point.hit <= min) { //빈 방
					queue.add(new Point(nx, ny, point.hit));
					visited[nx][ny][point.hit] = true;
				} else if(graph[nx][ny] == '1' && !visited[nx][ny][point.hit + 1] && point.hit + 1 <= min) { //벽
					queue.add(new Point(nx, ny, point.hit + 1));
					visited[nx][ny][point.hit + 1] = true;
				}
			}
		}
		
		return min;
	}

}

 

 

 

 

 

 

1번 풀이 결과

통과는 했는데 시간이 500ms대가 나왔다. 채점 현황에서 다른 Java11의 시간을 보니 100ms대였다..

시간이 많이 나온 것을 보니 가지치기가 덜 된 것 같다. 그래서 콘솔에 프린트로 탐색하는 과정을 찍어보았다.

 

예제 입력 1로 했을 경우, 최솟값이 3인데  hit이 5인 경우까지 다 탐색하고 있다. 그리고 문제점이 방문체크를 3차원으로 하면서 사방탐색을 하다보니, 벽을 부수고 새로운 hit를 가지고 다시 이전 좌표로 돌아오게 된다.

 

위의 코드에서 개선할 점은 다음과 같다.

 

1. hit이 최소인 point부터 탐색하게 하여, 큐에 원소가 남아있더라도 BFS 함수를 종료시키도록 해야 한다.

2. 벽을 부수고 새로운 hit를 가지고 다시 이전 좌표로 돌아오지 않도록 해야 한다.

 

 

 

 

 

2. BFS + 우선순위 큐

1번 풀이의 문제점에서 봤듯이, hit이 최소인 point부터 탐색하게 하여, 큐에 원소가 남아있더라도 BFS 함수를 종료시키도록 해야 한다. 큐를 돌리는 과정에서 hit이 최소인 원소부터 탐색하기 위해서는 큐를 우선순위큐로 바꿔야 한다.

 

 

 

• 우선순위큐 사용

Queue<Point> queue = new PriorityQueue<>((o1, o2) -> o1.hit - o2.hit);

Point 객체에 copareTo 오버라이딩하는 코드를 길게 적기 싫어서 람다식을 썼다..

Point 객체의 hit으로 비교해 hit이 적은 값 순으로 정렬하여, front에 최솟값이 위치하도록 한다.

 

 

 

• 방문체크 : boolean[N][M]

 우선순위큐를 써서 BFS 탐색을 한다면, 먼저 어떤 지점을 탐색을 하게 되는 경우에서 최솟값이 나올 것이다. 이미 최솟값을 구하러 탐색을 한 지점을 나중에 오는 경우에서 다시 탐색할 필요가 없어진다. 그래서 좌표값만 가지고 2차원으로 방문체크를 하는 것이 좋다.

 

 1번 풀이에서 최솟값을 넘어서는 경우를 가지치기 해줬는데, 방문 체크로 최솟값을 넘어서는 경우를 가지치기를 해주기 때문에 필요없어지게 된다.

 

 

 

• 도착하는 경우 BFS 종료하기

 가장 먼저 도착하게 되는 경우가 벽을 최소로 부수고 도착하는 경우이기 때문에 더 이상 다른 경우의 수를 탐색할 필요가 없어지게 된다. 그러므로 바로 BFS를 종료한다.

 

 

 

 

 

2번 풀이 코드

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

public class Main {
	static int N, M;
	static char[][] graph;
	static boolean[][] visited;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	
	static class Point {
		int x, y, hit;
		
		Point(int x, int y, int hit) {
			this.x = x;
			this.y = y;
			this.hit = hit;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		M = Integer.parseInt(st.nextToken()); //가로 크기
		N = Integer.parseInt(st.nextToken()); //세로 크기
		
		graph = new char[N][M];
		
		for(int i = 0; i < N; i++) {
			String line = br.readLine();
			
			for(int j = 0; j < M; j++) {
				graph[i][j] = line.charAt(j);
			}
		}
		
		visited = new boolean[N][M];
		
		System.out.println(bfs(0, 0));
	}

	public static int bfs(int i, int j) {
		Queue<Point> queue = new PriorityQueue<>((o1, o2) -> o1.hit - o2.hit);
		
		queue.add(new Point(i, j, 0));
		visited[i][j] = true;
		
		while(!queue.isEmpty()) {
			Point point = queue.poll();
			
			if(point.x == N - 1 && point.y == M - 1) {
				return point.hit;
			}
			
			for(int d = 0; d < 4; d++) {
				int nx = point.x + dx[d];
				int ny = point.y + dy[d];
				
				if(0 > nx || nx >= N || 0 > ny || ny >= M) continue; //미로 밖
				
				if(graph[nx][ny] == '0' && !visited[nx][ny]) { //빈 방
					queue.add(new Point(nx, ny, point.hit));
					visited[nx][ny] = true;
				} else if(graph[nx][ny] == '1' && !visited[nx][ny]) { //벽
					queue.add(new Point(nx, ny, point.hit + 1));
					visited[nx][ny] = true;
				}
			}
		}
		
		return 0;
	}

}

 

 

 

 

 

2번 풀이 결과

500ms대에서 100ms대로 시간이 확 줄었다.

 

 

 

콘솔에 프린트로 찍어보니 예제 입력 1로 했을 경우, 앞에서는 호출 카운트가 29였는데 이 풀이에서는 8로 탐색 수가 확 줄었다. 

 

 

 

 

 

3. BFS + 덱 (0-1 BFS)

 백준에서 이 문제의 알고리즘 분류를 보니 '0-1 너비 우선 탐색'이라고 적혀있었다. 처음 들어보는 알고리즘이었다. 구글링을 해보니 가중치가 0과 1로만 주어진 그래프에서 최단 경로를 찾을 때 풀 수 있는 알고리즘이라고 한다.

 

• 0-1 BFS

 

보통 최단 경로를 구할 때 다익스트라 알고리즘을 사용하기도 하는데, 그래프가 0과 1로만 이루어져 있는 특수한 환경에서 BFS 과정에서 큐를 사용하는 것 대신에 덱을 사용하여 최단 경로를 구할 수 있다.

 

 

알고리즘 동작 과정

1. 덱의 front에서 원소를 꺼낸다.

2. 연결된 지점을 살펴본다.

3. 지금까지의 비용에 그 지점으로 향하는 가중치를 더해 비용을 갱신한다.

4. 그 지점으로 향하는 가중치가 0이면 덱의 front에 넣고, 가중치가 1이면 덱의 back에 넣는다.

 

 

 

 2번 풀이에서 BFS 내의 우선순위큐를 덱으로 바꿔줬다. 그리고 큐에 넣는 부분에서 0이면 addFirst() 메소드를 쓰고, 1이면 addLast() 메소드를 써서 원소를 삽입했다.

 

 

 

 

 

3번 풀이 코드

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

public class Main {
	static int N, M;
	static char[][] graph;
	static boolean[][] visited;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	
	static class Point {
		int x, y, hit;
		
		Point(int x, int y, int hit) {
			this.x = x;
			this.y = y;
			this.hit = hit;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		M = Integer.parseInt(st.nextToken()); //가로 크기
		N = Integer.parseInt(st.nextToken()); //세로 크기
		
		graph = new char[N][M];
		
		for(int i = 0; i < N; i++) {
			String line = br.readLine();
			
			for(int j = 0; j < M; j++) {
				graph[i][j] = line.charAt(j);
			}
		}
		
		visited = new boolean[N][M];
		
		System.out.println(bfs(0, 0));
	}

	public static int bfs(int i, int j) {
		Deque<Point> queue = new LinkedList<>();
		
		queue.add(new Point(i, j, 0));
		visited[i][j] = true;
		
		while(!queue.isEmpty()) {
			Point point = queue.poll();
			
			if(point.x == N - 1 && point.y == M - 1) {
				return point.hit;
			}
			
			for(int d = 0; d < 4; d++) {
				int nx = point.x + dx[d];
				int ny = point.y + dy[d];
				
				if(0 > nx || nx >= N || 0 > ny || ny >= M) continue; //미로 밖
				
				if(graph[nx][ny] == '0' && !visited[nx][ny]) { //빈 방
					queue.addFirst(new Point(nx, ny, point.hit));;
					visited[nx][ny] = true;
				} else if(graph[nx][ny] == '1' && !visited[nx][ny]) { //벽
					queue.addLast(new Point(nx, ny, point.hit + 1));
					visited[nx][ny] = true;
				}
			}
		}
		
		return 0;
	}

}

 

 

 

 

 

3번 풀이 결과

 

2번 풀이 시간이 156ms이었는데, 136ms로 시간이 줄었다. 로직은 달라진 것이 없고 자료구조만 우선순위큐에서 덱으로 바꿨다. 우선순위큐는 동작과정에서 원소가 삽입될 때마다 정렬이 이루어지는데, 덱은 앞뒤로 삽입만 일어나니 수행 시간에서 차이가 나는 것 같다.

 

 

 

 

 

배운점

• 0-1 BFS
  • 가중치가 0과 1로만 주어진 그래프에서 최단 경로를 찾을 때 풀 수 있는 알고리즘
  • BFS 과정에서 큐를 사용하는 것 대신에 덱을 사용