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

1. problem :

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

 

2. solution 1 :

#include <bits/stdc++.h> 
using namespace std; 
int row, col;
string board[1002];
int dist[1002][1002][2]; //벽을 부셨을때와 그렇지 않았을때의 case를 고려 --> 3차원;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
queue<tuple<int, int, int>> Q; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> row >> col;
	for (int i = 0; i < row; i++) {
		cin >> board[i];
	}
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			dist[i][j][0] = dist[i][j][1] = -1;
		}
	}
	Q.push({ 0,0,0 });
	dist[0][0][0] = 1; 

	while (!Q.empty()) {
		int x, y, break_br;
		tie(x, y, break_br) = Q.front(); Q.pop(); 
		
		for (int dir = 0; dir < 4; dir++) {
			int nx = x + dx[dir];
			int ny = y + dy[dir]; 

			if (nx < 0 || nx >= row || ny < 0 || ny >= col) continue;
			if (board[nx][ny] == '1' && break_br == 0 && dist[nx][ny][1] == -1) {
				dist[nx][ny][1] = 1 + dist[x][y][0];
				Q.push({ nx,ny,1 });
			}
			if (board[nx][ny] == '0' && dist[nx][ny][break_br] == -1) {
				dist[nx][ny][break_br] = 1 + dist[x][y][break_br];
				Q.push({ nx,ny,break_br });
			}
		}
	}
	int result = -1;
	if (dist[row - 1][col - 1][0] != -1) result = dist[row - 1][col - 1][0];
	if (dist[row - 1][col - 1][1] != -1) {
		if (result == -1) result = dist[row - 1][col - 1][1];
		else {
			result = min(dist[row - 1][col - 1][0], dist[row - 1][col - 1][1]);
		}
	}
	cout << result << '\n';
	return 0;
}

완벽히 이해는 안된다. 외우자. 일단 넘어가자. 

 

3. solution 2 :

// Authored by : windowdong11
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/234d6a92de444d5c8d78bfae0286be7d
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

char board[1000][1000];
int dist[1000][1000][2];
// dist[x][y][0] : 벽을 하나도 부수지 않고 (x,y)까지 오는데 걸리는 비용
// dist[x][y][1] : 벽을 하나만 부수고 (x,y)까지 오는데 걸리는 비용, (x,y)가 벽이라서 부수는 경우 포함
int n, m;

bool OOB(int x, int y){
  return x < 0 || x >= n || y < 0 || y >= m;
}

int bfs() {
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
      dist[i][j][0] = dist[i][j][1] = -1;
  dist[0][0][0] = dist[0][0][1] = 1;
  queue<tuple<int, int, int>> q;
  q.push({0,0,0});
  while (!q.empty()) {
    int x, y, broken;
    tie(x, y, broken) = q.front();
    if(x == n-1 && y == m-1) return dist[x][y][broken];
    q.pop();
    int nextdist = dist[x][y][broken] + 1;
    for (int dir = 0; dir < 4; ++dir) {
      int nx = x + dx[dir];
      int ny = y + dy[dir];
      if(OOB(nx, ny)) continue;      
      if (board[nx][ny] == '0' && dist[nx][ny][broken] == -1) {
        dist[nx][ny][broken] = nextdist;
        q.push({nx, ny, broken});
      }      
      // (nx, ny)를 부수는 경우
      if (!broken && board[nx][ny] == '1' && dist[nx][ny][1] == -1) {
        dist[nx][ny][1] = nextdist;
        q.push({nx, ny, 1});
      }      
    }
  }
  return -1;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
      cin >> board[i][j];
  cout << bfs();
  return 0;
}

< source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x09/solutions/2206.cpp >

basic-algo-lecture/0x09/solutions/2206.cpp at master · encrypted-def/basic-algo-lecture