[C++][백준] 알고스팟(1261)

문제 설명

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.

알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.

벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.

현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

 

입력

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

(1, 1)과 (N, M)은 항상 뚫려있다.

 

출력

첫째 줄에 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

 

풀이

(1, 1) 위치에서 (N, M) 위치까지 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 구하는 문제입니다.

저는 BFS를 활용하여 풀이하였습니다.

 

기존 BFS에서는 visited 배열로 방문여부를 체크하고, 이미 방문한 위치는 다시 방문하지 않습니다.

그러나 해당 문제에서는 이미 방문한 위치라도 더 적은 무기 사용 횟수로 해당 위치를 방문할 수 있다면 다시 방문해야합니다. 

 

따라서 visited 배열을 아래와 같이 정의하였습니다.

visited[i][j] : (1, 1) ~ (i, j) 까지 무기를 사용한 최소 횟수

 

그리고 다음 위치가 벽인지, 빈칸인지를 구분하여 BFS를 수행하였습니다.

 

• 다음 위치가 벽인 경우

if (map[nextX][nextY] == 1) { // 벽
    if (visited[nextX][nextY] > visited[curX][curY] + 1) {
        visited[nextX][nextY] = visited[curX][curY] + 1;
        myQueue.push({ nextX, nextY });
    }
}

visited[nextX][nextY] > visited[curX][curY] + 1

: (1, 1) ~ (curX, curY) 로 오기까지 무기를 사용한 최소 횟수 + 1이 (1, 1) ~ (nextX, nextY)로 오기까지 무기를 사용한 최소횟수보다 적은 경우 값을 갱신하고 다시 그 자리에서 BFS를 수행할 수 있도록 Queue에 삽입합니다.

 

 

• 다음 위치가 빈칸인 경우

if (visited[nextX][nextY] > visited[curX][curY]) {
    visited[nextX][nextY] = visited[curX][curY];
    myQueue.push({ nextX, nextY });
}

visited[nextX][nextY] > visited[curX][curY]

: (1, 1) ~ (curX, curY) 로 오기까지 무기를 사용한 최소 횟수가 (1, 1) ~ (nextX, nextY)로 오기까지 무기를 사용한 최소횟수보다 적은 경우 값을 갱신하고 다시 그 자리에서 BFS를 수행할 수 있도록 Queue에 삽입합니다.

 

전체 코드는 아래와 같습니다.

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int N, M;
int map[110][110];
int visited[110][110];

int dirX[4] = {-1, 0, 1, 0};
int dirY[4] = {0, 1, 0, -1};

struct position {
	int x;
	int y;
};

bool IsInRange(int x, int y) {
	if (x >= 0 && x < N && y >= 0 && y < M) return true;
	else return false;
}

void solution() {
	queue<position> myQueue;
	myQueue.push({ 0, 0 });
	visited[0][0] = 0;

	while (!myQueue.empty()) {
		int curX = myQueue.front().x;
		int curY = myQueue.front().y;
		myQueue.pop();

		for (int i = 0; i < 4; i++) {
			int nextX = curX + dirX[i];
			int nextY = curY + dirY[i];

			if (!IsInRange(nextX, nextY)) continue;

			if (map[nextX][nextY] == 1) { // 벽
				if (visited[nextX][nextY] > visited[curX][curY] + 1) {
					visited[nextX][nextY] = visited[curX][curY] + 1;
					myQueue.push({ nextX, nextY });
				}
			}
			else { // 빈칸
				if (visited[nextX][nextY] > visited[curX][curY]) {
					visited[nextX][nextY] = visited[curX][curY];
					myQueue.push({ nextX, nextY });
				}
			}
		}
	}

	cout << visited[N - 1][M - 1];
}

int main() {
	cin >> M >> N;

	for (int i = 0; i < N; i++) {
		string input;
		cin >> input;
		for (int j = 0; j < M; j++) {
			map[i][j] = input[j] - '0';
		}
	}

	for (int i = 0; i < 110; i++) {
		for (int j = 0; j < 110; j++) {
			visited[i][j] = 987654321;
		}
	}
	solution();

	return 0;
}