백준 1261. 알고스팟

게시 2024/08/02

https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/images/boj-og.png

By Dukgukim

알고리즘 기초 문제 중 610 - BFS

알고스팟

1. 간단 설명

(1,1)에서 (N,M)으로 이동하는데 벽을 부수지 않으면 이동할 수 없는 경우가 존재함

벽을 최소로 부시면서 최단경로로 이동할 때,

벽을 최소 몇개 부숴야하는지 구하는 문제

2. 예시

예제 1)

최소 3개는 부셔야 도달 가능

예제 2)

하나도 부시지 않고 도달 가능

예제 3)

하나도 부시지 않고 도달 가능

3. 알고리즘

벽 부수고 이동하기2 와 유사하게 visited 배열을 3차원으로 사용한다

필요 변수

가로 세로 크기 int N, M (1 ≤ N, M ≤ 100)
맵 정보 int map[101][101]
방향 정보 int direct[4] = { 오른쪽, 아래, 왼쪽, 위 }
맵 방문 여부 int visited[y좌표][x좌표][부신 벽의 개수]
- 벽을 최대로 부실 수 있는 경우의 수는 100 100 에서 모든 맵이 벽으로 막힌 경우 197개 부셔야함
부신 벽의 최소 개수 int answer

알고리즘

1. N, M 입력받기
2. BFS 초기 세팅 
	- 큐에 시작지점 넣기
	- 해당 노드 방문처리
3. BFS 시작
	3-1. 큐에서 하나 꺼내기
	3-2. 해당 노드가 도착지인지 체크
	3-3. 다음 방문할 노드 4방향 선택
		3-3-1. 맵 경계 벗어났는지 체크
		3-3-2. 방문한적 있는지 체크
		3-3-3. 벽이 아니라면
			- 기존 BFS처럼 처리한다 (같은 층을 이동)
		3-3-4. 벽이라면
			- 이 벽을 부순적이 있는지 체크,
			- 벽을 부수고, 큐에 이를 등록함 

주의사항

벽 부시기2와는 다른 문제다

벽을 k개 부신다고 visited[101][101][101] 이렇게 설정하면

벽을 몇개 부시던간 최단거리만 계산하기 때문에

와 같은 경우 최단거리를 벽 하나 부시고 도달하는 8로 계산해버린다

이 문제에서는 벽을 최소로 부시는 회수를 구하라고 했으므로 이는 명백히 다르다

또한, N, M까지 도달하는 경로가 여러개 있을 수 있으므로, N,M에 도달했을 때 기존의 값과 비교 후 갱신해준다
문제 입력에서 N과 M이 바뀌어서 제공됨

4. 소스코드

  
#include <iostream>
#include <queue>

using namespace std;

int N, M;
int map[101][101];
int visited[101][101][200];

int direct[4][2] = {0,1,1,0,0,-1,-1,0};
int answer = 21e8;

struct node {
	int y;
	int x;
	int level;
};

void Input() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> M >> N;
	for (int y = 0; y < N; y++) {
		string input; cin >> input;
		for (int x = 0; x < input.length(); x++) {
			map[y][x] = input[x] - '0';
		}
	}
}

void BFS() {
	queue<node> qu;
	qu.push({ 0, 0, 0 });
	visited[0][0][0] = 1;

	while (!qu.empty()) {
		node now = qu.front();
		qu.pop();

		if (now.y == N - 1 && now.x == M - 1) {
			answer = min(answer, now.level);
		}

		for (int t = 0; t < 4; t++) {
			int dy = direct[t][0] + now.y;
			int dx = direct[t][1] + now.x;

			if (dy < 0 || dx < 0 || dy >= N || dx >= M) continue; // 경계처리
			if (visited[dy][dx][now.level] != 0) continue; // 현재 레벨에서 해당 노드 방문여부 체크

			// 벽인경우
			if (map[dy][dx] == 1) {
				if (visited[dy][dx][now.level + 1] != 0) continue; // 이미 한번 부신 경우
				visited[dy][dx][now.level + 1] = visited[now.y][now.x][now.level] + 1;
				qu.push({ dy, dx, now.level + 1 });
			}
			// 벽이 아닌경우
			else {
				visited[dy][dx][now.level] = visited[now.y][now.x][now.level] + 1;;
				qu.push({ dy, dx, now.level });
			}
		}
	}
	return; 
}

int main() {
	Input();

	BFS();

	cout << answer;

	return 0;
}

배운점

BFS 함수에서

  
for (int t = 0; t < 4; t++) {
	int dy = direct[t][0] + now.y;
	int dx = direct[t][1] + now.x;

	if (dy < 0 || dx < 0 || dy >= N || dx >= M) continue; // 경계처리
	if (visited[dy][dx][now.level] != 0) continue; // 현재 레벨에서 해당 노드 방문여부 체크

	// 벽인경우
	if (map[dy][dx] == 1) {
		if (visited[dy][dx][now.level + 1] != 0) continue; // 이미 한번 부신 경우
		visited[dy][dx][now.level + 1] = visited[now.y][now.x][now.level] + 1;
		qu.push({ dy, dx, now.level + 1 });
	}
	// 벽이 아닌경우
	else {
		visited[dy][dx][now.level] = visited[now.y][now.x][now.level] + 1;;
		qu.push({ dy, dx, now.level });
	}
}	

BFS 문제에서 관련 탐색 문제는 이 부분을 어떻게 구현하느냐에 따라 다양하게 갈리는 것 같다

각 노드를 탐색하는 방식과, 방문 체크 방법을 통해 알고리즘의 성능과 정확도에 크게 영향을 준다

  
 for (int i = 0; i < 4; ++i) {
        int nextX = current.x + dx[i];
        int nextY = current.y + dy[i];

        if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) continue;
        if (visited[nextX][nextY]) continue;

        visited[nextX][nextY] = true;
        queue.push({nextX, nextY});
    }

이처럼 방문체크하고, 방문처리 후 큐에 넣는게 기본형이라면

  
for (int i = 0; i < 4; ++i) {
	int nextX = current.x + dx[i];
	int nextY = current.y + dy[i];

	if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) continue;
	if (visited[nextX][nextY]) continue;

	if (map[nextX][nextY] == 0) {
		deq.push_front({nextX, nextY, current.cost});
	} else {
		deq.push_back({nextX, nextY, current.cost + 1});
	}

	visited[nextX][nextY] = true;
}

덱을 이용한 0-1 BFS 구현

  
for (int i = 0; i < 4; ++i) {
	int nextX = current.x + dx[i];
	int nextY = current.y + dy[i];
	int nextLevel = current.level;

	if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) continue;
	if (visited[nextX][nextY][nextLevel]) continue;

	if (map[nextX][nextY] == 1) {
		if (!visited[nextX][nextY][nextLevel + 1]) {
			visited[nextX][nextY][nextLevel + 1] = true;
			queue.push({nextX, nextY, nextLevel + 1});
		}
	} else {
		visited[nextX][nextY][nextLevel] = true;
		queue.push({nextX, nextY, nextLevel});
	}
}

이 문제나 벽부시기 2 와 같이 추가 정보를 고려하여 방문 체크를 해야하는 경우

  
for (auto start : startPoints) {
    queue.push(start);
    visited[start.x][start.y] = true;
}

또는 여러 출발지점을 동시에 시뮬레이션 해야하는 경우도 존재한다

최대한 다양한 문제들을 다루어볼 것!

Algorithm, Problem Solving