백준] 2206 : 벽 부수고 이동하기

2206번: 벽 부수고 이동하기

입력	출력
6 4 0100 1110 1000 0000 0111 0000	15
4 4 0111 1111 1111 1110	-1

 

 

 

 

✍문제 풀이

✔ 처음엔 굉장히 단순하게 접근한 문제이다.

   백준 - 미로 탐색 문제와 유사하고 생각했고, 이와 같이 풀었다.

   테케는 다 맞았으나 실제 채점 중 11%에서 틀렸습니다가 계속 출력됐다.

 

  1) 노란색은 이동 경로, 빨간색은 벽. 그리고 처음 출발부터 1로 체크한다.

 

✔ 벽 체크 방법은 이 블로그 해석을 참고했다.

위의 그림에 적힌 해석처럼 코드를 짜면 된다.

그러나 한 가지 중요한 것은 벽 부순 뒤(1) 결과 저장 + 벽 부수지 않은 뒤(0) 결과를 따로 check해서 결과를 저장해야 한다는 것이다.

자세한 테케와 설명은 아래를 참고하자.

 

✔ 작성한 코드가 11%에서 틀린다면?

     >> 참고 url

입력 받은 map[n][m]에 계산 결과 저장	- 처음엔 이렇게 구현했다. 걍 초기 입력받은 map 배열에 계산 결과를 때려넣음. 그 결과 벽을 깬 값와 벽을 깨지 않은 값이 같은 노드에 들어갈 때, 문제가 발생했다. 다른 분들의 코드를 봤을 때, 대부분 result[2][x][y]로 구현하셨다. 그 땐 왜 이렇게 구현하지? 라고 생각했는데, 아래 출력 예시를 보면 알 수 있듯이 정확한 답을 도출해낼 수 있었다.
check[2][n][m]에 계산 결과 저장	- check[0][n][m]에 저장된 값	- check[1][n][m]에 저장된 값

 

 

🌱 정답코드

 

 

+ 문제풀이 시행착오

 처음

미로 탈출 문제와 비슷하다고 파악했지만,

'벽을 하나만 부술 수 있다'라는 조건을 충족해서 코드를 구현하지 못했다.

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

int n, m;

int map[1001][1001];
bool check[1001][1001];
queue<pair<int, int>> q;

// 상하좌우 이동
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void bfs(){
	check[0][0] = true;
	int bCheck = 0;
	
	while(!q.empty()){
		int block = 0;
		
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		
		for(int i = 0; i < 4; i++){
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
			
			if(block >= 2) continue;
			
			if(map[nx][ny] == 1 && !check[nx][ny]){
				block++; // 벽 개수 체크
				map[nx][ny] += 1;
				check[nx][ny] = true;
				
				q.push({nx, ny});
			}
			
			if(map[nx][ny] == 0 && !check[nx][ny]){
				map[nx][ny] = map[x][y] + 1;
				check[nx][ny] = true;
				
				q.push({nx, ny});
			}
		}
	}
}

int main() {
	cin >> n >> m;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			scanf("%1d", &map[i][j]);
		}
	}
	
	map[0][0] = 1;
	q.push({0, 0});
	
	bfs();
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cout << map[i][j];
		}
		cout << endl;
	}
	
	cout << map[n - 1][m - 1];
	
	return 0;
}

 

그래서 아래 블로그의 문제해설을 참고했다.

[2206번] 벽 부수고 이동하기

 

2차 코드

//-> 테케는 맞았는데 실제 체점 틀린 코드

 

문제점

1. 1차적으로만 벽을 부수는 것을 체크함.

  그게 아니라 queue에 좌표값을 push할 때, 벽을 부쉈는지까지 push해야 함.

  그래야 추후에 queue에 들어간 값을 꺼내서 확인할 때, 다음 이동지를 정할 수 있음.

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

int n, m;

int map[1001][1001];
bool check[1001][1001];
queue<pair<int, int>> q;

// 상하좌우 이동
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void bfs(){
	check[0][0] = true;
	bool blockCheck = false;
	
	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		
		for(int i = 0; i < 4; i++){
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
			
			if(map[nx][ny] == 1 && !check[nx][ny] && !blockCheck){
				blockCheck = true;
				map[nx][ny] = map[x][y] + 1;
				check[nx][ny] = true;
				
				q.push({nx, ny});
			}
			
			if(map[nx][ny] == 0 && !check[nx][ny] && blockCheck){
				map[nx][ny] = map[x][y] + 1;
				check[nx][ny] = true;
				
				q.push({nx, ny});
			}
		}
	}
}

int main() {
	cin >> n >> m;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			scanf("%1d", &map[i][j]);
		}
	}
	
	map[0][0] = 1;
	q.push({0, 0});
	
	bfs();
	
	/* 확인
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cout << map[i][j] << ' ';
		}
		cout << endl;
	}*/

	if(map[n - 1][m - 1] == 0) cout << -1;
	else cout << map[n - 1][m - 1];

	return 0;
}

 

3차

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

int n, m;

int map[1001][1001];
bool check[1001][1001];
queue<pair<int, int>> q;
queue<bool> blockQ;

// 상하좌우 이동
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void bfs(){
	check[0][0] = true;
	blockQ.push(false);
	
	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		bool blockCheck = blockQ.front();
		//cout << x << ' ' << y << ' ' << blockCheck << endl;
		q.pop();
		blockQ.pop();
		
		for(int i = 0; i < 4; i++){
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
			
			if(map[nx][ny] == 1 && !check[nx][ny] && blockCheck) continue;
			
			if(map[nx][ny] == 1 && !check[nx][ny] && !blockCheck){
				map[nx][ny] = map[x][y] + 1;
				
				q.push({nx, ny});
				blockQ.push(true);
			}
			
			if(map[nx][ny] == 0 && !check[nx][ny]){
				map[nx][ny] = map[x][y] + 1;
				
				q.push({nx, ny});
				blockQ.push(blockCheck);
			}
		}
	}
}

int main() {
	cin >> n >> m;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			scanf("%1d", &map[i][j]);
		}
	}
	
	map[0][0] = 1;
	q.push({0, 0});
	
	bfs();
	
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cout << map[i][j] << ' ';
		}
		cout << endl;
	}
	
	if(map[n - 1][m - 1] == 0) cout << -1;
	else cout << map[n - 1][m - 1];

	return 0;
}

 

 

 

 

---

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

BOJ 2206 · 벽 부수고 이동하기

[2206번] 벽 부수고 이동하기

글 읽기 - 저같은 실수 하시는 분들을 위해 올립니다.