초기 코드
#include <iostream>
#include <queue>
#include <cstdio>
#include <string.h>
using namespace std;
int n, m;
int board[1001][1001];
int dy[4] = { 0, 0, 1 ,-1 };
int dx[4] = { 1, -1, 0, 0 };
int dist[1001][1001];
const int INF = 987654321;
bool isOut(pair<int, int> p) {
int y = p.first, x = p.second;
return (y <= 0 || y > n || x <= 0 || x > m);
}
int bfs() {
memset(dist, -1, sizeof(dist));
queue<pair<int, int>> q;
q.push(make_pair(1, 1));
dist[1][1] = 1;
while (!q.empty()) {
pair<int, int> here = q.front(); q.pop();
for (int direction = 0; direction < 4; direction++) {
pair<int, int> there = make_pair(here.first + dy[direction], here.second + dx[direction]);
if (isOut(there)) continue;
if (board[there.first][there.second] == 1) continue; //벽이면 이동할 수 없다 .
if (dist[there.first][there.second] == -1) {
q.push(there);
dist[there.first][there.second] = dist[here.first][here.second] + 1;
}
}
}
if (dist[n][m] == -1) return INF;
return dist[n][m];
}
int main() {
cin >> n >> m;
vector<string> input(n + 1);
for (int i = 1; i <= n; i++)
for (int j = 0; j < m; j++)
scanf("%1d", &board[i][j]);
int ret = INF;
int cand = bfs(); // 벽을 부수지 않는 경우
if (ret > cand) ret = cand;
for (int y = 1; y <= n; y++)
for (int x = 1; x <= m; x++) {
if (board[y][x] == 1) {
board[y][x] = 0; // 벽 부수기
cand = bfs();
if (ret > cand) ret = cand;
board[y][x] = 1; // 원상복구
}
}
if (ret == INF) cout << -1 << endl;
else cout << ret << endl;
return 0;
}
시간 초과가 나는 코드다. 아무래도 NM = 1000000 에서 하나하나 BFS 를 돌렸는데, 이를 계산하면
100만 * 100만^2 = 100만^3 = 엄청큰 수 .. 가 나오기 때문에 시간초과에 걸렸다.
여기서 NM의 정점을 탐색하다가 벽(1)이 나오면 벽을 부수거나, 부수지 않거나 둘 중 하나만 수행해준다. 참고로, 부수지 않는 다는 것은 지나가지 않는다는 것이니 기저사례 처리는 부수고 지나가는 경우만 해주면 된다. 이때 벽을 부수는 것은 딱 한번만 가능하니, 모든 정점에 벽이 있다고 해도 NM만큼만 탐색해주면 된다.
이를 구현하기 위해서는, y, x 외에도 (y, x)에 있는 벽을 부쉈는지/아닌지 여부를 저장하는 k를 한 개 더 두고, 삼차원 배열로 캐싱한다.
(1) tuple 사용하기
(2) 답이 두 가지 선택지에 의해서 구할 수 있다. 벽을 부수지 않거나, 벽을 부수거나 ! 따라서 dist[n][m][0]에 답이 있을 수도, dist[n][m][1]에 답이 있을 수도 있다. 둘 다 있다면 더 작은 것을 반환해야한다 .
#include <iostream>
#include <queue>
#include <cstring>
#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:4996)
using namespace std;
int n, m;
int board[1001][1001];
int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };
int dist[1001][1001];
bool isOut(int y, int x) {
return (y < 0 || y >= n || x < 0 || x >= m);
}
int bfs(int y, int x) {
memset(dist, -1, sizeof(dist));
queue<pair<int, int>> q;
q.push(make_pair(y, x));
dist[y][x] = 1;
int ret = 1;
while (!q.empty()) {
int y = q.front().first, x = q.front().second;
q.pop();
for (int direction = 0; direction < 4; direction++) {
int ny = y + dy[direction], nx = x + dx[direction];
if (isOut(ny, nx)) continue;
if (dist[ny][nx] == -1 && board[ny][nx] == 0) {
ret++;
q.push(make_pair(ny, nx));
dist[ny][nx] = dist[y][x] + 1;
}
}
}
return ret;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%1d", &board[i][j]);
// 이동할 수 있는 칸의 개수
for(int i = 0;i < n; i++){
for (int j = 0; j < m; j++)
if (board[i][j] == 1){
board[i][j] = bfs(i, j);
cout << board[i][j];
}
else if (board[i][j] == 0)
cout << 0;
cout << endl;
}
return 0;
}
이것도 마찬가지로 시간초과가 난다. 이걸 해결하는 나의 아이디어는 아래와 같다.
(1) dist[y][x][k] : (y, x) 칸이 k번 벽에 대한 검사가 이미 완료되었다면 1, 그렇지 않다면 0
(2) BFS 바로 수행. 빈 칸이면 패스하고, 벽이면 주변의 칸들을 탐색한다. 한 벽에 대해서는 고유한 k값이 붙는다. 따라서 그 벽(k = 1이라고 하자)의 주변에 위치한 빈칸들은 dist[y][x][1] = 1; 이 된다. 그리고 이 과정에서 board[ny][nx] = 0이 발견될 때마다 board[y][x]++; 를 수행해준다.
문제점 : 벽의 개수가 최대 1000000개여서 배열에 저장할 수 없다. ⇒ 꼭 배열에 저장해야하나 ? 한번 사용하면 끝인데 함수에서 변수 정의하면 안되나 ? 안되겠네 .. 그럼 배열을 하나 더 생성해서 현재 칸이 어떤 칸을 위해 세어지고 있는지 저장해보자 !
해설