[C++] 백준 2206 벽 부수고 이동하기

문제 링크

---

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

2206번: 벽 부수고 이동하기

 

접근 방법

---

 문제를 읽어보면 BFS알고리즘으로 풀어야된다는 직감은 확실히 들것이다. 하지만 벽을 부수는 것이 가능한 기회가 단 한번 주어지는대, 이로 인해 풀이에 있어 접근이 쉽지 않을 것이다.

 일단 문제를 보자마자 떠올릴 수 있는 방법이 있는데 map에서 모든 벽들을 한번씩 0으로 바꿔 보고 BFS를 해보는 것이다. 하지만 이렇게 하는 것은 굉장히 비효율적이고 시간안에 해결 할 수 없다. 

 문제 풀이에 있어 핵심은 어떤 특정한 지점에 "벽을 한번 부수고 난 이후에 도착 한 시간" 과 "벽을 한번도 부수지 않은 상태에서 도착한 시간"이 다르다는 것이다. 이것을 이해했다면 문제를 풀어보자.

 

(1) 변수

   isbreak는 벽을 부순적이 없다면 false 부순적이 있다면 true이다.

그렇다면 visited[i][j][ isbreak=true ]는 i, j위치에 벽을 부수고 나서 도착했을때의 시간이고,

visited[i][j][ isbreak=false ]는 벽을 부수지 않고 도착했을때의 시간이 된다. 

 

(2) 풀이

  전반적인 부분이 다른 BFS문제들과 매우 비슷하므로, 가장 핵심이 되는 부분만 설명하겠다.

if (!isbreak && map[next_x][next_y] == 1) {
	//벽을 부순적이 없는데 가로막힌 길이라면
    visited[next_x][next_y][true] = visited[x][y][false] + 1;
    q.push({ next_x, next_y, true });
}
else if (map[next_x][next_y] == 0 && visited[next_x][next_y][isbreak] == 0) { 
    //지나갈 수 있는 길이고, 방문한적이 없다면
    visited[next_x][next_y][isbreak] = visited[x][y][isbreak] + 1;
    q.push({ next_x, next_y, isbreak });
}

  첫 번째 if문은 isbreak = false이고 map[next_x][next_y] = 1 인 조건에서 진입이 가능한데, 이를 쉽게 풀어쓰면

"next_x, next_y의 좌표에 도달할 때 까지 벽을 부순적이 없는데 벽이 있다면" 진입을 한다는 것이다.

진입을 했다면 이제 벽을 부수고 해당지점에 도착했다는 것을 나타내주면 된다.

  두 번째 if문은 "일단 지나갈 수 있는 길이고, 방문한 적이 없다면" 방문을 하여 시간을 기록하고 큐에 push하면 된다. 이는 너무나도 당연한 것이기에 자세한 설명은 하지 않겠다.

 

  bfs( )함수의 while문 안에서 좌표가 n,m이면 도달한 시간을 return하게 된다. 그 말은 즉 while()안에서 return을 하지 못한다면 map[n][m]에 도달하지 못했다는 의미가 되므로 -1을 return한다. 

소스 코드

---

#include <iostream>
#include <queue>

using namespace std;

typedef struct info {
	int x;
	int y;
	bool isbreak;
};

int map[1001][1001];
int visited[1001][1001][2]; //같은 지점이여도 벽을 부수고 도착했을때와 벽을 부수지 않고 도착했을 때 값이 달라지기 때문
int n, m;

int bfs() {

	queue <info> q;
	visited[1][1][false] = 1;
	q.push({ 1,1,false }); //시작 지점 , 벽을 아직 부수지 않았음

	while (!q.empty()) {

		int x = q.front().x;
		int y = q.front().y;
		bool isbreak = q.front().isbreak;
		q.pop();

		if (x == n && y == m) //목표지점에 도착
			return visited[x][y][isbreak];

		pair<int, int> direction[4] = { {1,0}, {-1,0} ,{0,1} ,{0,-1} };

		for (int i = 0; i < 4; i++) {

			int next_x = x + direction[i].first;
			int next_y = y + direction[i].second;

			if (!(next_x < 1 || n < next_x || next_y < 1 || m < next_y)) { //다음 좌표가 map에 포함되어 있다면
				if (!isbreak && map[next_x][next_y] == 1) {
					//벽을 부순적이 없는데 가로막힌 길이라면
					visited[next_x][next_y][true] = visited[x][y][false] + 1;
					q.push({ next_x, next_y, true });
				}
				else if (map[next_x][next_y] == 0 && visited[next_x][next_y][isbreak] == 0) { 
					//지나갈 수 있는 길이고, 방문한적이 없다면
					visited[next_x][next_y][isbreak] = visited[x][y][isbreak] + 1;
					q.push({ next_x, next_y, isbreak });
				}
			}
		}
	}
	return -1;
}

int main() {

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			scanf("%1d", &map[i][j]);

	cout << bfs();
}

개발 환경 : VS 2019

질문, 지적 환영입니다.