미로만들기
1.설계(X)
-
문제 해석
- 2차원 배열의 (0,0) 에서 (N-1,N-1) 위치로 가기 위해서 검은방을 흰방으로 바꿔야 할 최소의 수를 구하는 문제입니다.
-
설계
- 처음에 이를 백트래킹으로 검은방을 흰방으로 바꾸면서 탐색을 시도했으나, 해당 방법은 경우의 수가 너무 많아 당연히 시간초과가 났습니다.
- 아이디어를 얻지 못해 REBAS님의 문제풀이를 참조하여 아이디어를 이용하였습니다.(bfs+deque)
- 또한 dfs로도 충분히 구현이 가능한 것을 다른 분들의 풀이를 보고 알았습니다.
- 범위가 그리 크지 않아 dfs탐색 O(N^4)으로 구현해도 충분히 돌아가는 것을 확인하였습니다. 범위가 더 커지면 이분탐색 + dfs(O(N^2*log(N^2))) 로 구현 가능할 것 같습니다.
2.구현(X)
- 코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <deque>
#include <cstring>
using namespace std;
#define MAXN 50
int map[MAXN][MAXN];
int dist[MAXN][MAXN];
deque<pair<int,int> > dq;
int N;
int dx[] = { 0,0,1 ,-1 };
int dy[] = { 1,-1,0,0 };
void bfs() {
dq.push_back({ 0,0 });
dist[0][0] = 0;
while (!dq.empty()) {
int x = dq.back().first;
int y = dq.back().second;
if (x == N - 1 && y == N - 1) {
cout << dist[x][y] << "\n";
return;
}
dq.pop_back();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
if (dist[nx][ny] != -1) continue;
if (map[nx][ny] == 0) {
dist[nx][ny] = dist[x][y] + 1;
dq.push_front({ nx,ny });
}
else {
dist[nx][ny] = dist[x][y];
dq.push_back({ nx,ny });
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
scanf("%d", &N);
memset(dist, -1, sizeof(dist));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
scanf("%1d", &map[i][j]);
}
}
bfs();
return 0;
}
-
디버깅
-
제출결과
3.마무리
- bfs또는 dfs문제가 약간 변형된 것인데 풀지 못하였습니다.