백준 2665 미로만들기 c++ [컴공과고씨]

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

2665번: 미로만들기

 

문제 정리

바둑판 모양이 있음.

각 방 마다 지나갈 수 있는 방과 없는 방으로 나뉨.

갈수 없는 방은 뚫 수 있음. 

(0,0) 에서 (n-1,n-1)까지 가는데 방을 최소한으로 뚫어서 갈 때 몇 개를 뚫어야 하는가?

 

문제 해결 방법

BFS를 사용해서 탐색을 하는데 각 방 마다 뚫고 온 방의 개수를 적어서 BFS 탐색을 해주면 됩니다.

방의 초기 값은 크게 잡아 줍니다. 그 후 시작점은 0으로 해줍니다.

BFS를 시작하면 각 방으로 들어갑니다. 

이 때 다음 방이 막힌 방이라면 이제 까지 뚫고 온 개수에 1을 더하고 저장된 개수와 비교하여 저장된 개수 보다 적을 때만 저장해 줍니다.

다음 방이 빈 방이라면 이제 까지 뚫고 온 개수와 저장된 개수를 비교하여 저장된 개수 보다 뚫고 온 개수가 더 적을 때만 저장해주고 다음 방으로 넘어가도록 합니다.

 

왜냐하면 저장된 개수보다 뚫은 개수가 더 크다면 이미 정답이 될 수 없으므로 더 이상 탐색할 필요가 없습니다. 또한 같은 경우는 중복 탐색이므로 마찬가지로 더 이상 탐색 할 필요가 없습니다.

 

전체 코드

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
int n;
int map[52][52]; // 빈 방, 막힌 방
int visit[52][52]; // 뚫고 온 개수 저장
int dx[] = {0, 0, -1, 1}; // 상하좌우
int dy[] = {1, -1, 0, 0}; // 상하좌우
 
void bfs(){
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    visit[0][0] = 0; // 시작 점은 0으로 세팅
    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]; // 다음 x 좌표
            int ny = y + dy[i]; // 다음 y 좌표
            if(nx >=0 && nx < n && ny>=0 && ny <n){
                if(map[ny][nx] == 1){ // 갈 수 있는 방
                    if(visit[ny][nx] > visit[y][x]){
                        //뚫고 온 방의 개수 비교 
                        visit[ny][nx] = visit[y][x];
                        q.push(make_pair(nx, ny)); // 다음 방으로 이동
                    } 
                }else{ // 비어 있는 방
                    if(visit[ny][nx] > visit[y][x]+1){
                        //뚫고 온 방의 개수 비교
                        visit[ny][nx] = visit[y][x]+1;
                        q.push(make_pair(nx, ny)); // 다음 방으로 이동
                    } 
                }
            }
        }  
    }     
}
 
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    char a;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            cin >> a;
            map[i][j] = a - '0'; // 입력을 int로 바꾸어줌
        }
    }
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            visit[i][j] = 987654321; // 최대 값
        }
    }
    bfs();
    cout << visit[n - 1][n - 1] << endl;
 
    return 0;
}

체감 난이도	걸린 시간	후기	사용 알고리즘
중	1H	간단한 문제 였는데 처음에 백트래킹으로 풀어 시간초과로 푸는데 오래 걸렸음.	BFS