[백준문제풀이] 1261 알고스팟

 

풀이일시 : 2020-12-25

​

 

문제 :

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 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)은 항상 뚫려있다.

ex)

3 3

011

111

110

​

​

출력 :

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

ex)

3

​

​

풀이 :

최단거리를 찾는게 아닌 최소로 벽을 부순 갯수를 찾는 문제이다.

탐색 알고리즘으로 경로들을 탐색하며 가장 적게 벽을 부순것을 찾아내야 할것이다.

​

1. 우선적으로 생각한 방법은 queue를 이용한 BFS 방법이다. (이렇게 풀어서 틀렸다.)

​

이를 사용했을 때에는 visit배열을 써서 한번 방문한 칸은 다시 반복하지 않도록 해야했는데 (무한루프방지) 벽을 부수지 않고 갈 수 있는 유일한 경로를 벽을 부순 경로가 먹어버린다면 최소로 갈수 있는 길을 잃게 되는 오류가 생겼다.

 

ex)

위와 같은 그림에서 초록색으로 나아간다면 노란색 칸을 지나쳤을 때 벽을 부순 횟수는 1이 되어 finish 되게 되고, 빨간색으로 나아간다면 벽을 부순 횟수가 없이 finish 할 수 있다.

하지만 초록색노선이 먼저 노란색 칸을 visit 해버리면 빨간색 경로는 노란색 칸을 visit 할 수 없어 벽을 부순횟수가 최소가 되지 못한다.

(범위에 맞고 방문하지 않은 점이면 minimum을 갱신해주며 반복한다.)

 

#include <iostream>
#include <queue>

using namespace std;
const int MAX = 100;

int M, N;
int graph[MAX][MAX];
int dx[] = {-1, 1, 0, 0};//열이바뀌는거
int dy[] = {0, 0, -1, 1};//행이바뀌는거
int minimum = 987654321;
int visited[MAX][MAX] = { 0, };

void bfs(int n, int m) { //가로 세로(행 열)
	queue <pair<pair<int,int>,int>> q; //큐에 ((가로, 세로) 벽부신횟수) 넣기
	q.push({ {n,m},0 });
	visited[0][0] = true;
	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int broken = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny >= 0 && ny < N && nx >= 0 && nx < M &&!visited[ny][nx]) { //범위가맞으면
				if (ny==N-1 && nx==M-1) { //끝점에 다다르면 (끝점엔 벽이없다)
					if (minimum >= broken) {
						minimum = broken;
					}
				}
				if (graph[ny][nx]==0) { //벽을 부수지않고 진행했을때
					q.push({ {ny,nx},broken });
				}
				else if (graph[ny][nx]==1) { //부수고 진행했을때
					q.push({ {ny,nx},broken + 1 });
				}
				visited[ny][nx] = true;
			}
		}
	}
}


int main() {
	cin >> M >> N;//M:열의 크기 N:행의크기
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf_s("%1d", &graph[i][j]);
		}
	}
	bfs(0, 0);
	cout << minimum << endl;
	return 0;
}

 

2. deque를 이용한 BFS 방법

​

무작정 큐에 넣는 방식으로는 최적의 해를 구할 수 없을것이라고 생각했다.

최적의 해라 함은 큐에서 나올 때 가장 벽을 깬 횟수가 적은 큐가 나와야 할것이다.

이를 위해서는 반복문을 수행하며 벽을 깨지 않았다면 큐의 앞으로 (우선순위를 준다.),

벽을 깼다면 큐의 back으로 들어가게 해줘야 한다. (후순위로 둔다.)

-> deque 이용

#include <iostream>
#include <deque>

using namespace std;
const int MAX = 100;

int M, N;
int graph[MAX][MAX];
int visited[MAX][MAX];
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
int broken;

//담는 여러가지 방법에 대해 얘기해보자
//덱 - pair로 두개로 묶는방법
//덱 - tuple로 한번에 묶는방법
//덱 - struct로 묶는방법

void bfs() {
	deque<pair<pair<int,int>,int>> deq; //x좌표, y좌표, 부순횟수
	deq.push_back({ {0,0},0 });
	visited[0][0] = 1;
	while (!deq.empty()) {
		int x = deq.front().first.first;
		int y = deq.front().first.second;
		broken = deq.front().second;
		deq.pop_front(); //다뽑고 pop한다.
		if (x == N - 1 && y == M - 1) {
			return;
		}
		for (int i = 0; i < 4; i++) {
			int newx = x + dx[i];
			int newy = y + dy[i];
			if (newx >= N || newx < 0 || newy >= M || newy < 0)
				continue;
			if (visited[newx][newy])
				continue;
			visited[newx][newy] = 1;
			if (graph[newx][newy])
				deq.push_back({ {newx,newy},broken + 1 });
			else
				deq.push_front({ {newx,newy},broken });
		}
	}
	return;
}

int main() {
	cin >> M >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf_s("%1d", &graph[i][j]);
		}
	}
	bfs();
	cout << broken << endl;
	return 0;
}
​

 

추가자료 : deque

dbstndi6316.tistory.com/30

[개념정리] deque container

추가자료 : input 방법들

dbstndi6316.tistory.com/33

[개념정리] C++ 여러 input방법에 대해

추가자료 : BFS 너비우선탐색

dbstndi6316.tistory.com/63

[기본문제풀이] BFS 너비우선탐색