[C++]백준 - 2206번 문제

2206번: 벽 부수고 이동하기 (acmicpc.net)

2206번: 벽 부수고 이동하기

 

2206번 : 벽 부수고 이동하기

---

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

 

 

출력

---

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

 

 

 

---

 

생각해 볼 점

---

기존 그래프 탐색과 달리 딱 한 번 벽을 부술 수 있으므로,

 

탐색과정에서 벽을 부쉈는지 체크해야합니다.

 

BFS 탐색을 하되, 기존 BFS와 달리 큐에는 다음과 같은 정보가 담겨야 합니다.

 

1. 탐색할 좌표

2. 벽을 부쉈는지의 여부

 

저는 큐에 좌표를 담되, Pair를 사용하였고,

벽을 부쉈으면 X좌표에 10000을 더하여 체크를 하였는데, 직관적이지 않으므로

 

typedef some_type [int, int, bool]

 

등의 방법을 통해서 큐에 정보를 담아두는 것이 낫습니다.

 

그 외의 탐색 방법은 기존 BFS 알고리즘과 동일하되, 한가지 더 주의할 점이 있습니다.

 

예를 들어,

 

 

위와 같은 반례를 조심해야 합니다.

 

(3, 2)좌표를 보시면, 벽을 부수고 지나간 빨간 경로에서 이미 탐색했기 때문에, 파란 경로를 통하면 GOAL에 도착할 수 있음에도 불구하고, 지나가지 못하고 있습니다.

 

따라서, 우리는 Visited를 사용할 때에도, 벽을 부순 후 탐색된 것인지, 벽을 부수지 않고 탐색된 것인지를 체크해야 합니다.

 

저같은 경우는 이진법을 통해 확인하였습니다만, 코드가 직관적이지 않고 지저분하므로 다른 방법을 사용하시기 바랍니다.

 

 

코드

---

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

//Matrix[i][j] = (이진수)111 -> 벽을 부수고 탐색했는가? /벽을 부수지 않고 탐색했는가?/ 벽인가?
//예시 : 6 = 통과할 수 있으며, 벽을 부수지 않은 경로로도, 벽을 부순 경로로도 이미 탐색됨

int **matrix;   
int N, M;       // (y, x)
int count = 0;
queue<pair<int, int>> q;    //(x, y)형태로 저장 단, x좌표에 벽을 부쉇는지 여부를 10000으로 저장함

int mov[5] = {0, -1, 0, 1, 0};


//BFS 알고리즘
void bfs()
{
    vector<pair<int, int>> next_bfs;    //다음BFS 좌표들을 저장
    count++;    //탐색횟수 1 증가
    
    //이번 회차의 좌표들을 모두 탐색
    while(!q.empty())
    {
        pair<int, int> current = q.front();
        if(current.first % 10000 == M && current.second == N) return;
        q.pop();
        bool crashed = current.first / 10000;   //벽을 부쉈는가?
        
        for(int i = 0; i < 4; i++)
        {
            int new_x = current.first % 10000 + mov[i];
            int new_y = current.second + mov[i + 1];
               
            //벽을 부순 적 있음
            if(crashed)
            {
                if(matrix[new_y][new_x] % 2 == 0 && matrix[new_y][new_x] / 4 == 0)
                {
                    matrix[new_y][new_x] += 4;       //visited
                    new_x += 10000;
                    next_bfs.push_back({new_x, new_y});
                }
            }
            //벽을 부순 적 없음
            else
            {
                //벽일 경우 벽을 부숨
                if(matrix[new_y][new_x] == 1 && !crashed) next_bfs.push_back({new_x + 10000, new_y});
                
                //벽이 아니면, 벽을 부수지 않은 채로 탐색했는지 체크
                else if((matrix[new_y][new_x] % 4) / 2 == 0)
                {
                    
                    matrix[new_y][new_x] += 2;       //visited
                    next_bfs.push_back({new_x, new_y});
                }
            }
        }
    }
    for(pair<int, int> p : next_bfs) 
    {
        q.push(p);
    }
    if(!q.empty()) bfs();
}


int main() 
{
	cin >> N >> M;
	
	//동적할당, 초기화
	matrix = new int*[N + 2];
	matrix[0] = new int[M + 2];
	matrix[N + 1] = new int[M + 2];
	fill_n(matrix[0], M + 2, 7);
	fill_n(matrix[N + 1], M + 2, 7);
	
	//입력부
	for(int i = 0; i < N; i++)
	{
	    string input;
	    cin >> input;
	    
	    matrix[i + 1] = new int[M + 2];
	    fill_n(matrix[i + 1], M + 2, 7);
	    for(int j = 0; j < M; j++) matrix[i + 1][j + 1] = input[j] - 48;
	}
	
	q.push({1, 1});
	matrix[1][1] = 2;
	bfs();
	
	if(matrix[N][M] < 2) cout << -1;
	else cout << count;
	
	for(int i = 0; i < N + 2; i++) delete[] matrix[i];
	delete[] matrix;
	return 0;
}

 

그 외

---

몇 번 틀려서 수정하다보니 코드가 좀 지저분할 수 있습니다.