[BOJ 14442 벽 부수고 이동하기 2]로 알아보는 조건이 있는 BFS

2024. 8. 4. 23:49·Algorithm
목차
  1. 문제 읽기
  2. BFS의 본질
  3. 빨리 도착한다고 다가 아니라면?
  4. '조건이 있는' BFS
  5. 코드
  6.  마치며

문제 원문 링크 바로가기

문제 읽기

 벽이 존재하는 N*M 필드의 (1, 1)에서부터 (N, M)까지 도달할 수 있는 최단 경로의 길이를 구해내는 문제이다. 여기까지만 읽으면 단순한 BFS 문제이지만, 문제는 '벽을 부술 수 있다'는 점에 있다.

 만일 벽을 부수고 지나갈 때 경로가 더 짧아진다면, 벽을 부술 수도 있다. 단, 최대 K회까지 가능하다. 그러니까, 단순히 벽에 가로막히고 말고만을 따지는 단순한 BFS로는 문제를 풀 수 없다는 것이다. 이런 문제는 어떻게 풀어야 할까?

BFS의 본질

 우선, 우리가 최단경로를 구하기 위해 BFS를 수행하는 과정을 생각해보자. BFS를 수행하는 과정을 간단히 서술해보면 다음과 같다.

  • 시작 지점을 큐에 넣고, 방문 표기를 한다.
  • 이후, 큐가 빌 때까지 다음을 반복한다 : 
    •  큐에서 값을 하나 꺼낸 후, 그 값이 목적지인지 확인한다. 목적지라면, 경로를 찾은 것이므로 반복을 종료한다.
    • 목적지가 아닌 경우, 현재 지점으로부터 나아갈 수 있는 모든 지점을 확인한다. 나아갈 수 있는 지점들 중, 아직 들르지 않은 지점이 있다면, 그 지점은 최단경로의 일부가 될 수 있는 후보가 된다! (이때 '특정 지점을 들렀느냐 들르지 않았느냐'는 방문 표기 여부로 판단한다.)
    • 위의 기준으로 적합하다고 판단된 지점을 큐에 넣는다.
  • 큐가 비었다면, 갈 수 있는 모든 지점을 가보았다는 의미이다. 만일 큐가 빌 때까지 목적지에 도달하지 못했다면, 목적지에 도착할 수 없다는 뜻이다.

 위의 BFS를 수행하는 과정을 잘 살펴보면, '이미 방문했다고 표기된 지점을 다시 들른 순간, 최단거리가 되지 않는다'는 전제가 깔려있음을 알 수 있다.

 사실, 그 이유는 아주 간단하다! 정말 단순한 예시로, A라는 지점부터 B라는 지점까지의 최단경로를 구해야한다고 해보겠다. 떠. A와 B 사이에는 많은 지점이 있겠지만, 그 중 C라는 지점이 있다고 해보자. C라는 지점을 30분만에 갈 수 있는 경우와, 1시간만에 갈 수 있는 경우. 둘 중 어느 것이 최단경로가 될 가능성이 있을까? 당연하게도, 30분만에 갈 수 있는 경우이다. 왜냐하면, 중간지점 C로부터 B까지의 걸리는 최소의 시간은 하나로 정해져 있다. C에서 B까지 가는데에 최소 1시간 30분이 걸린다고 가정해보면, 전자의 경우는 A부터 B까지 걸리는 시간이 총 2시간, 후자의 경우는 2시간 30분이다. 즉, 특정한 지점에 도착하는데에 더 오래 걸리는 경우의 수는, 최단거리가 될 가능성이 완전히 없기 때문에 배제하는 것이다.

BFS에서의 방문 표기의 의미

 위처럼 최단이 될 수 없는 경우의 수를 배제하기 위해, BFS를 시행할 때에는 방문표기를 시행한다. BFS를 시행할 때에는 큐라는 자료구조를 사용하는데, 이 때문에 BFS의 대상이 되는 경우의 수는 무조건 시간 순으로 고려하게 된다.

 

 1회 이동하여 갈 수 있는 지점들 → 2회 이동하여 갈 수 있는 지점들 → 3회 이동하여 갈 수 있는 지점들 → ... (이하 반복)

 

 때문에, BFS 과정 중 먼저 고려하게 되는 경우의 수가 더 짧게 이동한 경우이다. 앞에서 도착할 수 있었던 지점을 뒤에서 또 도착한다고 하더라도, 뒤의 경우는 무조건 앞의 경우보다 더 먼 길을 통해 도착하거나, 아무리 빠르더라도 앞의 경우와 같은 길이의 경로를 거친다. 때문에 우리는 BFS를 이용해 최단거리를 구할 때, 한 번 도착해본 지점에 대해서는 고려하지 않아도 되는 것이다. 어차피 앞에서 더 빠르게 도착했으니, 다시 고려할 필요가 없다는 거다.

 

 간단하게 다시 정리하자면 다음과 같다. BFS에서 방문 표기를 하는 이유는, 이전에 이미 도착해 본 지점을 또다시 도착해보았자, 그 경로는 최단경로가 되지 않기 때문이다.

빨리 도착한다고 다가 아니라면?

 이번 문제처럼, 최단경로를 구할 때 또다른 조건이 추가되는 경우가 있다. 이렇게 되면, 단순히 먼저 도착하는 경우만이 최단의 가능성을 지니게 되는 게 아니게 될 수 있다.

 

 아까처럼 간단한 예시를 들어보자. A부터 B까지 최단경로를 구하는 게 목적이고, C라는 중간지점이 있다. 이번에는 [벽 부수고 이동하기] 문제와 비슷하게, 길을 가다가 방해물이 있는 경우, 그걸 딱 한 번 부수고 지나갈 수 있다고 해 보겠다. 고려해볼 첫 번째 경우는, C에 30분만에 도착하는 경우이다. 다만, 이 경우는 C까지 빠르게 도착하기 위해, 오는 길에 이미 방해물을 부수고 왔다. 두 번째 경우는, C에 1시간만에 도착하는 경우이다. 이 경우는 길을 조금 돌아온 대신, 방해물을 부수지 않았다. 두 경우 중 어떤 경우가 최단의 가능성을 지니고 있을까?

 

 정답은, 둘 다 가지고 있다. 왜냐하면, 두 경우는 장애물을 부순 횟수가 다르기 때문이다. 첫 번째 경우는, C까지 도착하는 과정 중에 방해물을 한 번 부쉈다. 즉, C부터 B까지 향할 동안은 방해물을 부술 수 없다는 뜻이다. 반대로, 두 번째 경우는, C까지 오는동안 방해물을 하나도 부수지 않았다. C부터 B까지 향할 동안, 방해물을 부술 수도 있다는 뜻이다.

 C에서 B까지 걸리는 시간이, 방해물을 부쉈을 때에는 15분, 부수지 못할 때에는 1시간이라고 해보자. 그렇게 되면 첫 번째 경우의 A →B 소요시간은 총 1시간 30분, 두 번째 경우의 A →B 소요시간은 총 1시간 15분이다. C까지 도착하는데에 걸리는 시간이 더 길었음에도, 두 번째 경우가 최단의 경우가 된다는 거다!

 이처럼, 경로를 지날 때 특수한 조건이 추가되면, 더 오래 걸려 도착하는 경우를 완전히 배제할 수 없는 일이 생기기도 한다. 나는 이런 문제를 개인적으로 조건이 있는 BFS, 혹은 특수 BFS라고 부르고 있다.

'조건이 있는' BFS

 위의 장황한 내용을 통해 내가 설명하고자 했던 내용을 요약하면 다음과 같다. [벽 부수고 이동하기] 처럼, 단순히 더 빨리 도착한 경로만이 최단의 가능성을 지니게 되는 게 아닌 문제가 있다. 즉, 단순한 방문여부 표기만으로는 최단 경로를 구할 수 없다. 이런 문제를 풀 때에는, 어떤 요인이 최단이 될 가능성에 영향을 미치는가에 대해 고민해볼 필요가 있다.

 이번 문제에서 최단의 가능성에 영향을 주는 요인은, 벽을 부순 횟수이다. 경로를 설계할 때, 최대 K회까지 벽을 부술 수 있다는 것이 이 문제의 조건이었다. 벽을 부수면 돌아가야 할 길을 생략할 수 있기 때문에, 벽을 부술 수 있는 횟수가 많을수록, 현재 탐색하고 있는 경로가 앞으로 더 짧은 경로를 찾을 가능성이 올라간다. 이런 점을 고려하여 BFS를 설계하려면 어떻게 해야할까? 말이 좀 거창한데, 단순하게 정리하자면 이런 질문이다 : 어떤 경우에, 더 늦게 도착해도 최단의 가능성이 있다고 쳐줄 것인가?

방문 표기 체계 구성

 최단이 될 가능성에 영향을 미치는 요인은 다음 두 가지이다 : 도착할때까지 거친 경로의 길이, 앞으로 벽을 부술 수 있는 횟수. 전자를 위해서, 우리는 항상 각 지점에 대응되는 boolean값을 기록했었다. 하지만, 이번에는 더 늦게 도착했더라도, 앞으로 벽을 더 많이 부술 수 있다면 그 경우도 고려해줘야 한다. 그렇다면 방문 배열에 방문여부만 기록하지 말고, 방문했을 당시 지금까지 벽을 부순 횟수를 기록하는 건 어떨까?

 

 A→B의 최단경로를 구해야하며, 그 중간에 C라는 지점이 있다는 예시를 다시 들어보자. 이번에는 장애물을 최대 K회 부술 수 있다고 해보자. 처음에 C라는 지점에, K+1이라는 숫자를 기록해둔다. 가장 첫번째로 C라는 지점에 도착한 경우는, 장애물을 전부 부수고 온 지라 장애물을 K회 부쉈다. 이 K라는 숫자를 C 지점에 기록해 둔 K+1과 비교해보면, 당연하게도 K가 더 작은 숫자이다. C라는 지점에 더 적게 벽을 부수고 도착했으니, 통과시킨다. 그리고, C 지점에 기록해둔 숫자를 K로 변경한다.

 그 다음의 경우는, C라는 지점에 도착하는 동안 장애물을 K-3회 부쉈다. C 지점에 기록된 K와 비교해봤을 때, K-3이 더 작은 숫자이다. 이전의 경우보다 좀 더 돌아서 도착했지만, 앞으로 벽을 부술 수 있는 기회가 3번이 남은 것이다. 때문에 이 경우도 최단이 될 가능성이 있다. C 지점에 기록한 숫자를 K-3로 변경시킨 후, 통과시킨다.

 또 다음의 경우는, 도착할동안 장애물을 K-1회나 부쉈다. C 지점에 기록된 K-3와 비교해보면... 이번 경우가 벽을 더 많이 부쉈다. 더 늦게 도착했는데, 앞으로 벽을 부술 수 있는 횟수가 적기까지? 이런 경우는 도착할 때까지 거친 경로의 길이도 더 길고, 앞으로 벽을 부술 기회도 모자라므로, 최단의 가능성이 없다. 때문에 이 경우는 더 고려하지 않고 폐기한다.

 

 위의 과정을 이해할 수 있었을까? 최단의 가능성에 해당하는 경로의 길이, 그리고 벽을 부술 수 있는 횟수를 동시에 고려하며, 각각의 경우가 최단의 가능성이 있는지 아닌지를 고려하고 있다. 이 문제의 경우, 위의 방식대로 구성하면 2차원 int형 배열을 이용해 모든 가능성을 따질 수 있다.

코드

 아래는 실제로 문제 풀이에 제출한 코드이며, Java 8로 작성되어있다.

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

public class Main {
	
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	
	public static void main(String[] args) throws Exception{
		/* 입출력 관련 객체 작성 */
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		/* [풀이 전략]
		 * 마찬가지로 특수 BFS인데, 이번에는 벽을 K회까지 부술 수 있다. 이때 K는 1보다 크거나 같고 10보다 작거나 같다.
		 * 규모가 조금 커졌을 뿐, 기존 문제와 마찬가지로 벽을 부순 횟수를 방문배열 대신에 사용하면 될듯하다.
		 * N과 M이 좀 커서 시간이 오래 걸릴듯함.
		 * */
		
		// 첫번째 줄 : N, M, K
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		// 이후 N개의 줄동안 맵 정보가 주어진다
		// 지나갈 수 있음 : true / 지나갈 수 없음 : false
		boolean[][] map = new boolean[N][M];
		for(int n = 0 ; n < N ; ++n) {
			char[] input = br.readLine().trim().toCharArray();
			for(int m = 0 ; m < M ; ++m) {
				if(input[m] == '0') { // 지나갈 수 있는 공간이라면 true로 표기
					map[n][m] = true;
				}
			}
		}
		// 입력받기 종료
		// 방문배열은 벽을 부순 횟수를 기록하는 2차원 int 배열로 한다.
		int[][] visited = new int[N][M];
		for(int n = 0 ; n < N ; ++n) {
			Arrays.fill(visited[n], 11); // 방문한 적 없음을 최대 부술 수 있는 벽의 횟수보다 높은 숫자로 표기
		}
		
		// BFS 준비
		ArrayDeque<int[]> q = new ArrayDeque<>();
		// 출발점은 (0, 0)
		q.offer(new int[] {0, 0, 0}); // 인덱스 2 : 지금까지 벽을 부순 횟수
		visited[0][0] = 0;
		// 시작하는 칸을 포함하여 센다는 점에 주의
		int count = 0;
		
		// BFS 시작
		boolean found = false;
		while(!found && !q.isEmpty()) {
			count++;
			int size = q.size();
			for(int s = 0 ; s < size ; ++s) {
				int[] info = q.poll();
				int x = info[0];
				int y = info[1];
				int broken = info[2];
				// 도착지점에 도착했다면 루프를 탈출한다.
				if(x == N-1 && y == M-1) {
					found = true;
					break;
				}
				// 도착하지 않았다면, 가능한 경우의 수를 탐색
				for(int d = 0 ; d < 4 ; ++d) {
					int nextX = x+dx[d];
					int nextY = y+dy[d];
					if(nextX < N && nextX >= 0 && nextY < M && nextY >= 0) {
						// 유효한 인덱스 범위 내이면 이동을 시도할 수 있다.
						// [1] 이동할 공간이 벽이 아닌 경우
						// 현재의 broken과 지점에 기록된 broken을 비교한다.
						if(map[nextX][nextY] && visited[nextX][nextY] > broken) {
							visited[nextX][nextY] = broken;
							q.offer(new int[] {nextX, nextY, broken});
						}
						// [2] 이동할 공간이 벽인 경우
						// 벽을 부술 기회가 남아있다면, 진행을 시도
						else if(!map[nextX][nextY] && broken < K) {
							int nextBroken = broken+1;
							if(visited[nextX][nextY] > nextBroken) {
								visited[nextX][nextY] = nextBroken;
								q.offer(new int[] {nextX, nextY, nextBroken});
							}
						}
					}
				}
			}
		}
		// 반복 종료
		// 결과를 출력한다.
		if(!found) {
			System.out.println(-1);
		} else System.out.println(count);

	}

}

 마치며

 조건이 있는 BFS는 최단 가능성을 어떻게 따질 것인가에 대한 고민을 충분히 한다면, 일반 BFS와 크게 다르지 않게 풀 수 있는 문제이다. 이 문제의 경우 2차원 배열만을 이용해 모든 가능성을 따질 수 있었지만, 사실 대부분의 특수 BFS는 3차원 이상의 배열을 사용한다. 2차원 배열만으로 특수 BFS를 풀기 전에는, 정말로 최단의 가능성을 모두 고려했는지를 꼼꼼히 생각하도록 하자. 나도 다 생각 못 하고 2차원 배열로 밀다가 많이 틀렸다...

 아는 사람들과 스터디를 진행하다가, 이 문제를 2차원 배열로 푸는 방식이 특이하다는 말을 들어서 한 번 정리해보았다. 누군가에게 이 글이 도움이 되었다면... 정말 영광이다! 앞으로의 문제 풀이에 참고해주면 고맙겠다.

'Algorithm' 카테고리의 다른 글

븟츠의 계수 정렬(Count Sort)!  (0) 2024.09.22
[알고리즘] 🤪 이죵과 병합정렬(Merge Sort)에 대해서 알아보자  (0) 2024.08.25
[알고리즘] 🤪이죵과 다익스트라(Dijkstra) 알고리즘을 알아보자  (3) 2024.07.22
[알고리즘] 이분 탐색  (2) 2024.07.21
[BOJ 18222 투에-모스 문자열]을 이진법을 이용해 풀어보자  (0) 2024.07.21
  1. 문제 읽기
  2. BFS의 본질
  3. 빨리 도착한다고 다가 아니라면?
  4. '조건이 있는' BFS
  5. 코드
  6.  마치며
'Algorithm' 카테고리의 다른 글
  • 븟츠의 계수 정렬(Count Sort)!
  • [알고리즘] 🤪 이죵과 병합정렬(Merge Sort)에 대해서 알아보자
  • [알고리즘] 🤪이죵과 다익스트라(Dijkstra) 알고리즘을 알아보자
  • [알고리즘] 이분 탐색
월월월월2
월월월월2
백엔드로 살아남기 입니다.
월월월월2
백엔드로 살아남기
월월월월2
전체
오늘
어제
  • 분류 전체보기 (64)
    • Spring (15)
    • TroubleShooting (2)
    • Infra (7)
    • Java (9)
    • Docker (7)
    • Database (1)
    • Algorithm (9)
    • React (8)
    • CS (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

링크

공지사항

인기 글

태그

사가 패턴
countingsort
dind
비관적 락
낙관적 락
JPA
Java
자바빈즈패턴
Algorithm
MSA
react testing library
Docker in Docker
자바
트러블슈팅
Docker
23288
스프링스케줄러
Spring Security
스프링
연관 관계
YAML
도커
다중 usersdetail
spring
springboot
Docker Out of Docker
#security
점층적생성자패턴
application.properties
DevOps

최근 댓글

최근 글

hELLO· Designed By정상우.v4.6.1
월월월월2
[BOJ 14442 벽 부수고 이동하기 2]로 알아보는 조건이 있는 BFS

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.