백준 2206번, 벽 부수고 이동하기(C, C++)

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

2206번: 벽 부수고 이동하기

#include<iostream>
#include<queue>

using namespace std;

int map[1001][1001];
int visited[1001][1001][2];
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, -1, 1};
int N;
int M;

int bfs(){
  queue<pair<pair<int, int>, pair<int, int>>> q;
  q.push(make_pair(make_pair(0, 0), make_pair(0, 1)));
  visited[0][0][0] = 1;
  while(!q.empty()){
      int x = q.front().first.first;
      int y = q.front().first.second;
      int wall = q.front().second.first;
      int cnt = q.front().second.second;
      q.pop();

      if(x == N-1 && y == M-1){
          return cnt;
      }
      for(int i = 0; i < 4; i++){
          int nx = x + dx[i];
          int ny = y + dy[i];

          if(nx>=0 && nx < N && ny>=0 && ny<M){
              //벽이 있고 아직 벽을 안부순 상태에서, 방문을 안한경우
              if(map[nx][ny] == 1 && wall == 0 && visited[nx][ny][wall+1] == 0){
                  visited[nx][ny][wall+1] == 1;
                  q.push((make_pair(make_pair(nx, ny), make_pair(wall+1, cnt + 1))));
              }
              //벽을 부쉈던 경험이 있거나 안 부순 경험이 유무 상관없이 방문을 안한 경우
              if(map[nx][ny] == 0 && visited[nx][ny][wall] == 0){
                  visited[nx][ny][wall] = 1;
                  q.push((make_pair(make_pair(nx, ny), make_pair(wall, cnt + 1))));                
              }
          }
        }
    }
    return -1;
}

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

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

 

코드를 짜기전에

DFS인지 BFS인지 구분하는게 제일 먼저 우선이다.

최소 경로를 구하려면 BFS 방식으로 풀어야한다.

왜냐하면 DFS가 가는 경로가 무조건 최소 경로가 아니기 때문이다.

3차원 배열은 벽의 존재 유무를 표현하기 위해 3차원 배열을 이용하기로 했다.

visited[x][y][0]은 벽을 아직 부수지 않은 상태에 방문처리

visited[x][y][1]은 벽을 부순 상태에서 방문처리.

 

 

제일 첫번째 칸에서 진행 방향은 오른쪽과 아래쪽이다.

오른 쪽으로 진행했을 경우 아래로 가는 방향과 오른쪽으로 가는 방향의 경우의 수가 2가지 나온다.

벽을 부수고 갔을 경우 아래와 오른쪽 가는 경우의 수가 생긴다.

여기서 visited[x][y][0]이 visited[x][x][1]로 갱신되며 이동거리를 카운트해주는 cnt를 그대로 +1한 상태로 이어 받는다.

 

만약에 가는 도중에 벽을 만나더라도 이미 벽을 부쉈다는 정보를 3차원 배열에서 입력했기 때문에

만약에

다른 벽을 만나더라도 그 벽이 있는 경로가 아닌 다른 경로로 돌아갈 것이다.