백준 2665 - 미로만들기(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2665

2665번: 미로만들기

다익스트라와 bfs를 이용해 푸는 문제입니다.

해당 문제에서 생각해야 할 것이 있습니다.

 

먼저 하나의 구역으로 묶여있는 흰 방을 방문할 때 바꾼 검은 방의 갯수를 바꿔줘야 하나? 입니다.

당연하게도 바꿀 필요가 없습니다. 같은 구역의 흰 방이라면 무조건 같은 갯수의 검은 방 입니다.

따라서 바꾼 검은 방의 갯수가 바뀌는 경우는 흰 방 -> 검은 방 * X -> 흰 방의 경우입니다.

 

따라서 이차원 배열을 통해 바꾸고 온 검은 방의 갯수를 저장한 뒤, 다익스트라 알고리즘을 통해 (N, N)에서의 최소로 바꾼 검은 방의 갯수를 계속 구해주면 됩니다.

 

문제에서는 (1, 1) 에서 시작해 (N, N)으로 가면 되니, (1, 1)을 시작 위치로 잡아줍니다.

시작 지점에서의 바꾼 검은 방의 갯수는 0이니, Distance 배열의 값을 INF가 아닌, 0으로 바꾸고 시작합니다.

 

(1, 1)에서 시작해, 4방향 탐색을 시작합니다. 이때 경우가 2가지가 있습니다.

1. 가야할 곳이 흰 방이라면? -> 해당 Distance의 값과 비교한 뒤, 바꾼 검은 방의 갯수를 유지한 채 탐색을 이어간다.

2. 가야할 곳이 검은 방이라면? -> 해당 Distance의 값과 비교한 뒤, 검은 방의 갯수 + 1을 해주고 탐색을 이어간다.

 

마지막에 탐색이 끝났다면, (N, N)의 Distance 배열 값을 출력해줍니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#define INF 987654321

using namespace std;

priority_queue<pair<int, pair<int,int>>, vector<pair<int, pair<int,int>>>, greater<pair<int, pair<int,int>>>> q;
int N;
int map[51][51];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int Distance[51][51];

void reset_distance(){
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			Distance[i][j] = INF;	
		}
	}
}

void Find_distance(int X, int Y){
	q.push({0,{X,Y}});
	Distance[X][Y] = 0;	
	while(!q.empty()){
		int cnt = q.top().first;
		int x = q.top().second.first;
		int y = q.top().second.second;
		q.pop();
		for(int i = 0; i < 4; i++){
			int xx = x + dx[i];
			int yy = y + dy[i];
			if(xx >= 1 && xx <= N && yy >= 1 && yy <= N){
				if(map[xx][yy] == 1){
					if(Distance[xx][yy] > cnt){
						Distance[xx][yy] = cnt;
						q.push({cnt,{xx,yy}});
					}
				}
				else{
					if(Distance[xx][yy] > cnt + 1){
						Distance[xx][yy] = cnt + 1;
						q.push({cnt+1, {xx,yy}});
					}
				}
			}
		}
	}
}

void solve(){
	reset_distance();
	Find_distance(1,1);
	cout << Distance[N][N];
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			scanf("%01d", &map[i][j]);
		}
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요